Visual cryptography

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Visual cryptography is a cryptographic technique which allows visual information (pictures, text, etc.) to be encrypted in such a way that decryption becomes a mechanical operation that does not require a computer.

One of the best-known techniques has been credited to Moni Naor and Adi Shamir, who developed it in 1994. They demonstrated a visual secret sharing scheme, where an image was broken up into n shares so that only someone with all n shares could decrypt the image, while any n − 1 shares revealed no information about the original image. Each share was printed on a separate transparency, and decryption was performed by overlaying the shares. When all n shares were overlaid, the original image would appear.

Using a similar idea, transparencies can be used to implement a one-time pad encryption, where one transparency is a shared random pad, and another transparency acts as the ciphertext.


A demonstration of visual cryptography

In this example, the Wikipedia logo has been split into two shares. Each white pixel in the original logo is split into two of the same small blocks that have full black and white pixels. When these two blocks are overlaid, they align exactly, and so the result is a light-colored block (with half black and half white pixels). Each black pixel in the original logo is split into two complementary small blocks. When these two blocks are overlaid, the result is a completely black block.

If each pixel in the original image is split randomly into two shares as described above, the shares are correlated together and reveal the original image. Still, when each individual share is considered alone (i.e., when the other share is unknown), it is indistinguishable from a random pattern. Given only one share, a second share can be crafted to reveal any possible image; therefore, individual shares reveal no information about the original image.

(2, N) Visual Cryptography Sharing Case[edit]

Sharing a secret with an arbitrary number of people N such that at least 2 of them are required to decode the secret is one form of the visual secret sharing scheme presented by Moni Naor and Adi Shamir in 1994. In this scheme we have a secret image which is encoded into N shares printed on transparencies. The shares appear random and contain no decipherable information about the underlying secret image, however if any 2 of the shares are stacked on top of one another the secret image becomes decipherable by the human eye.

Every pixel from the secret image is encoded into multiple subpixels in each share image using a matrix to determine the color of the pixels. In the (2,N) case a white pixel in the secret image is encoded using a matrix from the following set:

{all permutations of the columns of} : \mathbf{C_0 = }  \begin{bmatrix}
1 & 0 & ... &0 \\
1 & 0 & ... & 0 \\
1 & 0 & ... &0 \end{bmatrix}.

While a black pixel in the secret image is encoded using a matrix from the following set:

{all permutations of the columns of} :  \mathbf{C_1 =}\begin{bmatrix}
1 & 0 & ...& 0 \\
0 & 1 & ... & 0 \\
... \\
0 & 0 & ...& 1 \end{bmatrix}.

For instance in the (2,2) sharing case (the secret is split into 2 shares and both shares are required to decode the secret) we use complementary matrices to share a black pixel and identical matrices to share a white pixel. Stacking the shares we have all the subpixels associated with the black pixel now black while 50% of the subpixels associated with the white pixel remain white.

Cheating the (2,N) Visual Secret Sharing Scheme[edit]

Horng et al. proposed a method that allows N-1 colluding parties to cheat an honest party in visual cryptography. They take advantage of knowing the underlying distribution of the pixels in the shares to create new shares that combine with existing shares to form a new secret message of the cheaters choosing.

We know that 2 shares are enough to decode the secret image using the human visual system. But examining two shares also gives some information about the 3rd share. For instance colluding participants may examine their shares to determine when they both have black pixels and use that information to determine that another participant will also have a black pixel in that location. Knowing where black pixels exist in another party's share allows them to create a new share that will combine with the predicted share to form a new secret message.

In this way a set of colluding parties that have enough shares to access the secret code can cheat other honest parties.

Simple Algorithm[edit]

There is a simple algorithm for binary (black and white) visual cryptography that makes 2 images of one main image, the algorithm is explained as follows: let's take first image a completely random image in size of main image, and the second one will be as same as the first one, but when a pixel of main image the second one will change value to exclusive or (XOR) of the first one. Now we have two images, that lonely they don't make any sense, but when XOR these two pictures, the main picture will be shown.