Visual Cryptography

Slideshow Transcript

1. Slide 1: Visual Cryptography (OR) Reading Between the Lines Ecaterina Valică http://students.info.uaic.ro/~evalica/
2. Slide 2: Agenda  Introduction  k out of n sharing problem  Model  General k out of k Scheme  2 out of n Scheme  2 out of 2 Scheme (2 subpixels)  2 out of 2 Scheme (4 subpixels)  3 out of 3 Scheme  2 out of 6 Scheme  Extensions  Applications  References
3. Slide 3: Introduction  Visual cryptography (VC) was introduced by Moni Naor and Adi Shamir at EUROCRYPT 1994.  It is used to encrypt written material (printed text, handwritten notes, pictures, etc) in a perfectly secure way.  The decoding is done by the human visual system directly, without any computation cost.
4. Slide 4: Introduction  Divide image into two Simple example parts:  Key: a transparency  Cipher: a printed page  Separately, they are random noise  Combination reveals an image
5. Slide 5: k out of n sharing problem  Extended to k out of n sharing problem  For a set P of n participants, a secret image S is encoded into n shadow images called shares (shadows), where each participant in P receives one share.  The original message is visible if any k or more of them are stacked together, but totally invisible if fewer than k transparencies are stacked together (or analysed by any other method)
6. Slide 6: Model  Assume the message consists of a collection of black and white pixels and each pixel is handled separately.  Each share is a collection of m black and white subpixels.  The resulting picture can be thought as a [nxm] Boolean matrix S = [si,j]  si,j = 1 if the j-th subpixel in the i-th share is black.  si,j = 0 if the j-th subpixel in the i-th share is white.
7. Slide 7: Model m  Pixels are split: Pixel Subpixels  n shares per pixel: m si,j Share 1 Share 2 n Share n
8. Slide 8: Model  The grey level of the combined share is interpreted by the visual system:  as black if H (V )  d  as white if H (V )  d  am .  1  d  m is some fixed threshold and a  0 is the relative difference.  H(V) is the hamming weight of the “OR” combined share vector of rows i1,…in in S vector.
9. Slide 9: Model: Stacking & Contrast m Stacking m : V H(V) H(V)  mB contrast = (mB-mW)/m H(V)  mW mW < mB
10. Slide 10: Model
11. Slide 11: General k out of k Scheme  Matrix size = k x 2k-1  S0 : handles the white pixels  All 2k-1 columns have an even number of 1’s  No two k rows are the same  S1 : handles the black pixels  All 2k-1 columns have an odd number of 1’s  No two k rows are the same  C0/C1 : all the permutation of columns in S0/S1
12. Slide 12: 2 out of n Scheme  m=n  White pixel - a random column-permutation of: 1 0 0  0 1 0 0  0   1 0 0  0        1  0 0  0   Black pixel - a random column-permutation of: 1 0 0  0 0 1 0  0   0 0 1  0        0  0 0  1 
13. Slide 13: 2 out of 2 Scheme (2 subpixels)  Black and white image: each pixel divided in 2 sub-pixels  Randomly choose between black and white.  If white, then randomly choose one of the two rows for white.
14. Slide 14: 2 out of 2 Scheme (2 subpixels)  If black, then randomly choose between one of the two rows for black.
15. Slide 15: 2 out of 2 Scheme (2 subpixels)
16. Slide 16: 2 out of 2 Scheme (2 subpixels)  Example:
17. Slide 17: 2 out of 2 Scheme (2 subpixels)  The two subpixels per pixel variant can distort the aspect ratio of the original image +
18. Slide 18: 2 out of 2 Scheme (4 subpixels)  Each pixel encoded as a 2x2 cell  in two shares (key and cipher)  Each share has 2 black, 2 transparent subpixels  When stacked, shares combine to  Solid black  Half black (seen as gray)
19. Slide 19: 2 out of 2 Scheme (4 subpixels)  6 ways to place two black subpixels in the 2 x 2 square  White pixel: two identical arrays  Black pixel: two complementary arrays 0101 1010  0011 1100  0110  1001 C 0  {  1010  0011 1100  0110  1001} 0101       0101 1010  0011 1100  0110  1001  C 1  {  0101 1100  0011 1001  0110 } 1010       
20. Slide 20: 2 out of 2 Scheme (4 subpixels) Horizontal shares Vertical shares Diagonal shares
21. Slide 21: 2 out of 2 Scheme (4 subpixels)
22. Slide 22: pixel 0 1 2 3 4 5 0 1 2 3 4 5 share1 share2 stack 4 0 1 5 random
23. Slide 23: 3 out of 3 Scheme (4 subpixels)  With same 2 x 2 array (4 subpixel) layout  0011 C0={ 24 matrices obtained by permuting the columns of  0101 }   0110    1100  C1={ 24 matrices obtained by permuting the columns of 1010  }   1001   0011 1100 0101 1010 0110 1001 horizontal shares vertical shares diagonal shares
24. Slide 24: 3 out of 3 Scheme (4 subpixels) Original Share #1 Share #2 Share #3 Share Share #1+#2 Share #2+#3 Share #1+ #3 #1+#2+#3
25. Slide 25: 2 out of 6 Scheme  Any 2 or more shares out of the 6 produced 1100  1100    1100  C0={ 24 matrices obtained by permuting the columns of   } 1100  1100    1100  1100  1010    1001  C1={ 24 matrices obtained by permuting the columns of    0101 }  0011   0110 
26. Slide 26: 2 out of 6 Scheme Share#1 Share#2 Share#3 Share#4 Share#5 Share#6 2 shares 3 shares 4 shares 5 shares 6 shares
27. Slide 27: Extensions - Four Gray Levels  Each pixel encoded as A 3x3 cell 3 black, 6 transparent  Combine to 3, 4, 5, or 6 black
28. Slide 28: Extensions - Grey Scale Encryption  Pixel range from 0 (white) to 255 (black)  Encode pixel with a half-circle Share #1 Share #2 Stacked Color White Gray Black
29. Slide 29: Extensions - Continuous Gray level  Each pixel encoded as 33% black circle  Combine for any gray from 33% to 67% black
30. Slide 30: Extensions - Extended VC  Ateniese et al., 2001  Send innocent looking transparencies, e.g. Send images a dog, a house, and get a spy message with no trace.  
31. Slide 31: Extensions - Color VC  Verheul and van Tilborg’s method  For a C-color image, we expand each pixel to C subpixels on two images.  For each subpixel, we divide it to C regions. One fixed region for one color.  If the subpixel is assigned color C1 , only the region belonged to C1will have the color. Other regions are left black.
32. Slide 32: Extensions - Color VC  Verheul and van Tilborg’s method Four Four subpixels regions One pixel on Combined four- color image
33. Slide 33: Extensions - Color VC  Rijmen and Preneel’s method  Each pixel is divided into 4 subpixels, with the color red, green, blue and white.  In any order, we can get 24 different combination of colors. We average the combination to present the color.  To encode, choose the closest combination, select a random order on the first share. According to the combination, we can get the second share.
34. Slide 34: Extensions - Color VC  Rijmen and Preneel’s method Combined Combined Pattern1 Pattern2 Pattern1 Pattern2 Result Result
35. Slide 35: Extensions - Color VC
36. Slide 36: Applications  Remote Electronic Voting  Anti-Spam Bot Safeguard  Banking Customer Identification  Message Concealment  Key Management
37. Slide 37: References  Naor and Shamir, Visual Cryptography, in Advances in Cryptology - Eurocrypt ‘94  www.cacr.math.uwaterloo.ca/~dstinson/visual.html  http://homes.esat.kuleuven.be/~fvercaut/talks  http:// www.cse.psu.edu/~rsharris/visualcryptograph
38. Slide 38: References  http://netlab.mgt.ncu.edu.tw/computersecurity/  http://163.17.135.4/imgra /PPT/200500022.ppt