Editing Visual cryptography

{{Short description|Cryptographic technique}}
[[File:visual_cryptography_development.svg|thumb|Development of masks to let overlaying ''n'' transparencies A, B,... printed with black rectangles reveal a secret image &mdash; ''n'' = 4 requires 16 (2<sup>4</sup>) sets of codes each with 8 (2<sup>4-1</sup>) subpixels, which can be laid out as 3×3 with the extra bit always black]]
'''Visual cryptography''' is a [[cryptography|cryptographic]] technique  which allows visual information (pictures, text, etc.) to be encrypted in such a way that the decrypted information appears as a visual image.

One of the best-known techniques has been credited to [[Moni Naor]] and [[Adi Shamir]], who developed it in 1994.<ref>{{Cite book |doi = 10.1007/BFb0053419|chapter = Visual cryptography|title = Advances in Cryptology – EUROCRYPT'94|volume = 950|pages = 1–12|series = Lecture Notes in Computer Science|year = 1995|last1 = Naor|first1 = Moni|last2 = Shamir|first2 = Adi|isbn = 978-3-540-60176-0}}</ref> They demonstrated a visual [[secret sharing]] scheme, where a [[binary image]] was broken up into ''n'' shares so that only someone with all ''n'' shares could decrypt the image, while any {{nowrap|''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. There are several generalizations of the basic scheme including ''k''-out-of-''n'' visual cryptography,<ref>{{cite journal |doi=10.1023/A:1008280705142|year=1997|last1=Verheul|first1=Eric R.|title=Constructions and Properties of k out of n Visual Secret Sharing Schemes|journal=Designs, Codes and Cryptography|volume=11|issue=2|pages=179–196|last2=Van Tilborg|first2=Henk C. A.|s2cid=479227}}</ref><ref>{{Cite journal |doi = 10.1016/S0304-3975(99)00127-9|title = Extended capabilities for visual cryptography|journal = Theoretical Computer Science|volume = 250|issue = 1–2|pages = 143–161|year = 2001|last1 = Ateniese|first1 = Giuseppe|last2 = Blundo|first2 = Carlo|last3 = Santis|first3 = Alfredo De|last4 = Stinson|first4 = Douglas R.|doi-access = }}</ref> and using opaque sheets but illuminating them by multiple sets of identical illumination patterns under the recording of only one single-pixel detector.<ref>{{cite journal|last1=Jiao|first1=Shuming|last2=Feng|first2=Jun|last3=Gao|first3=Yang|last4=Lei|first4=Ting|last5=Yuan|first5=Xiaocong|title=Visual cryptography in single-pixel imaging|journal=Optics Express|year=2020|volume=28|issue=5|pages=7301–7313|doi=10.1364/OE.383240|pmid=32225961|arxiv=1911.05033|bibcode=2020OExpr..28.7301J |s2cid=207863416}}</ref>

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. Normally, there is an expansion of space requirement in visual cryptography. But if one of the two shares is structured recursively, the efficiency of visual cryptography can be increased to 100%.<ref>{{Cite journal |doi = 10.1080/0161-110291890768|title = Recursive Hiding of Secrets in Visual Cryptography|journal = Cryptologia|volume = 26|pages = 68–76|year = 2002|last1 = Gnanaguruparan|first1 = Meenakshi|last2 = Kak|first2 = Subhash|s2cid = 7995141}}</ref>

Some antecedents of visual cryptography are in patents from the 1960s.<ref>Cook, Richard C. (1960) [https://patents.google.com/patent/US4682954 Cryptographic process and enciphered product], United States patent 4,682,954.</ref><ref>Carlson, Carl O. (1961) [https://patents.google.com/patent/US3279095 Information encoding and decoding method], United States patent 3,279,095.</ref> Other antecedents are in the work on perception and secure communication.<ref>{{Cite journal |doi = 10.1364/OL.12.000377|pmid = 19741737|title = Encryption of pictures and shapes by random grids|journal = Optics Letters|volume = 12|issue = 6|pages = 377–9|year = 1987|last1 = Kafri|first1 = O.|last2 = Keren|first2 = E.|bibcode = 1987OptL...12..377K}}</ref><ref>{{Cite journal |doi = 10.1109/21.44016|title = Intuition, perception, and secure communication|journal = IEEE Transactions on Systems, Man, and Cybernetics|volume = 19|issue = 5|pages = 1016–1020|year = 1989|last1 = Arazi|first1 = B.|last2 = Dinstein|first2 = I.|last3 = Kafri|first3 = O.}}</ref>

Visual cryptography can be used to protect biometric templates in which decryption does not require any complex computations.<ref>{{cite conference |last1=Askari|first1=Nazanin|last2=Moloney|first2=Cecilia|last3=Heys|first3=Howard M.|title=Application of Visual Cryptography to Biometric Authentication|conference=NECEC 2011|date=November 2011|url=http://necec.engr.mun.ca/ocs2011/viewpaper.php?id=60&print=1|access-date=12 February 2015}}</ref>

== Example ==
[[Image:Visual crypto animation demo.gif|frame|right|A demonstration of visual cryptography. When two same-sized images of apparently random black-and-white pixels are superimposed, the [[Wikipedia]] logo appears.]]

In this example, the [[binary image]] has been split into two component images. Each component image has a ''pair'' of pixels for every pixel in the original image. These pixel pairs are shaded black or white according to the following rule: if the original image pixel was black, the pixel pairs in the component images must be complementary; randomly shade one ■□, and the other □■. When these complementary pairs are overlapped, they will appear dark gray. On the other hand, if the original image pixel was white, the pixel pairs in the component images must match: both ■□ or both □■. When these matching pairs are overlapped, they will appear light gray.

So, when the two component images are superimposed, the original image appears. However, without the other component, a component image reveals no information about the original image; it is indistinguishable from a random pattern of ■□ / □■ pairs. Moreover, if you have one component image, you can use the shading rules above to produce a ''counterfeit'' component image that combines with it to produce any image at all.

== (2, ''n'') visual cryptography sharing case ==
[[File:visual_cryptography_3_choose_2.svg|thumb|upright=1.25|Any two transparencies printed with black rectangles, when overlaid reveals the message, here, a letter A (gridlines added for clarity)]]
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, where each row gives the subpixel pattern for one of the components:

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

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

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

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 ==
Horng et al. proposed a method that allows {{nowrap|''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.<ref>{{Cite journal |doi = 10.1007/s10623-005-6342-0|title = Cheating in Visual Cryptography|journal = Designs, Codes and Cryptography|volume = 38|issue = 2|pages = 219–236|year = 2006|last1 = Horng|first1 = Gwoboa|last2 = Chen|first2 = Tzungher|last3 = Tsai|first3 = Du-Shiau|s2cid = 2109660}}</ref>

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.

== Visual steganography ==
[[File:visual_cryptography_stenography.svg|thumb|Overlaying component images with letters A and B to reveal the letter S]]
2×2 subpixels can also encode a binary image in each component image, as in the scheme on the right. Each white pixel of each component image is represented by two black subpixels, while each black pixel is represented by three black subpixels.

When overlaid, each white pixel of the secret image is represented by three black subpixels, while each black pixel is represented by all four subpixels black. Each corresponding pixel in the component images is randomly rotated to avoid orientation leaking information about the secret image.<ref>M. Pramanik, Kalpana Sharma, [http://semanticscholar.org/paper/d724f43a2f8ae4ace27f66997579b7871e0a2f75 ''Analysis of Visual Cryptography, Steganography Schemes and its Hybrid Approach for Security of Images''], Computer Science, 2014</ref>

== In popular culture ==
* In "[[Do Not Forsake Me Oh My Darling]]", a 1967 episode of TV series ''[[The Prisoner]]'', the protagonist uses a visual cryptography overlay of multiple transparencies to reveal a secret message – the location of a scientist friend who had gone into hiding.

== See also ==
* [[Grille (cryptography)]]
* [[Steganography]]

== References ==
{{reflist}}

== External links ==
* [https://github.com/kartoffelquadrat/VisuCrypt Java implementation and illustrations of Visual Cryptography]
* [https://github.com/LessonStudio/VisualCryptography Python implementation of Visual Cryptography]
* [http://users.telenet.be/d.rijmenants/en/visualcrypto.htm Visual Cryptography on Cipher Machines & Cryptology]
* [https://cs.uwaterloo.ca/~dstinson/visual.html Doug Stinson's visual cryptography page]
* [https://link.springer.com/book/10.1007/978-3-319-09644-5 Liu, Feng; Yan, Wei Qi (2014) Visual Cryptography for Image Processing and Security: Theory, Methods, and Applications, Springer]
* {{cite journal |doi=10.3390/jimaging4110126|title=Personalized Shares in Visual Cryptography|journal=Journal of Imaging|volume=4|issue=11|pages=126|year=2018|last1=Hammoudi|first1=Karim|last2=Melkemi|first2=Mahmoud|doi-access=free}}

{{Cryptography navbox}}
{{Hidden messages}}

[[Category:Cryptography]]