Visual cryptography

Last updated

Visual cryptography is a 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.

Contents

One of the best-known techniques has been credited to Moni Naor and Adi Shamir, who developed it in 1994. [1] 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. There are several generalizations of the basic scheme including k-out-of-n visual cryptography, [2] [3] and using opaque sheets but illuminating them by multiple sets of identical illumination patterns under the recording of only one single-pixel detector. [4]

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%. [5]

Some antecedents of visual cryptography are in patents from the 1960s. [6] [7] Other antecedents are in the work on perception and secure communication. [8] [9]

Visual cryptography can be used to protect biometric templates in which decryption does not require any complex computations. [10]

Example

A demonstration of visual cryptography. When two same-sized images of apparently random black-and-white pixels are superimposed, the Wikipedia logo appears. Visual crypto animation demo.gif
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 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

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} :

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

{all permutations of the columns of} :

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 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. [11]

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.

See also

Related Research Articles

<span class="mw-page-title-main">JPEG</span> Lossy compression method for reducing the size of digital images

JPEG is a commonly used method of lossy compression for digital images, particularly for those images produced by digital photography. The degree of compression can be adjusted, allowing a selectable tradeoff between storage size and image quality. JPEG typically achieves 10:1 compression with little perceptible loss in image quality. Since its introduction in 1992, JPEG has been the most widely used image compression standard in the world, and the most widely used digital image format, with several billion JPEG images produced every day as of 2015.

<span class="mw-page-title-main">Pixel</span> Physical point in a raster image

In digital imaging, a pixel, pel, or picture element is the smallest addressable element in a raster image, or the smallest addressable element in a dot matrix display device. In most digital display devices, pixels are the smallest element that can be manipulated through software.

A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key can be different sizes and varieties, but in all cases, the strength of the encryption relies on the security of the key being maintained. A key's security strength is dependent on its algorithm, the size of the key, the generation of the key, and the process of key exchange.

Digital image processing is the use of a digital computer to process digital images through an algorithm. As a subcategory or field of digital signal processing, digital image processing has many advantages over analog image processing. It allows a much wider range of algorithms to be applied to the input data and can avoid problems such as the build-up of noise and distortion during processing. Since images are defined over two dimensions digital image processing may be modeled in the form of multidimensional systems. The generation and development of digital image processing are mainly affected by three factors: first, the development of computers; second, the development of mathematics ; third, the demand for a wide range of applications in environment, agriculture, military, industry and medical science has increased.

<span class="mw-page-title-main">Chroma subsampling</span> Practice of encoding images

Chroma subsampling is the practice of encoding images by implementing less resolution for chroma information than for luma information, taking advantage of the human visual system's lower acuity for color differences than for luminance.

An adaptive chosen-ciphertext attack is an interactive form of chosen-ciphertext attack in which an attacker first sends a number of ciphertexts to be decrypted chosen adaptively, and then uses the results to distinguish a target ciphertext without consulting the oracle on the challenge ciphertext. In an adaptive attack, the attacker is further allowed adaptive queries to be asked after the target is revealed. It is extending the indifferent (non-adaptive) chosen-ciphertext attack (CCA1) where the second stage of adaptive queries is not allowed. Charles Rackoff and Dan Simon defined CCA2 and suggested a system building on the non-adaptive CCA1 definition and system of Moni Naor and Moti Yung.

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding. Commitment schemes have important applications in a number of cryptographic protocols including secure coin flipping, zero-knowledge proofs, and secure computation.

Secret sharing refers to methods for distributing a secret among a group, in such a way that no individual holds any intelligible information about the secret, but when a sufficient number of individuals combine their 'shares', the secret may be reconstructed. Whereas insecure secret sharing allows an attacker to gain more information with each share, secure secret sharing is 'all or nothing'.

In cryptography, an oblivious transfer (OT) protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece has been transferred.

Secure multi-party computation is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their inputs while keeping those inputs private. Unlike traditional cryptographic tasks, where cryptography assures security and integrity of communication or storage and the adversary is outside the system of participants, the cryptography in this model protects participants' privacy from each other.

In cryptography, a secret sharing scheme is verifiable if auxiliary information is included that allows players to verify their shares as consistent. More formally, verifiable secret sharing ensures that even if the dealer is malicious there is a well-defined secret that the players can later reconstruct. The concept of verifiable secret sharing (VSS) was first introduced in 1985 by Benny Chor, Shafi Goldwasser, Silvio Micali and Baruch Awerbuch.

In cryptography the standard model is the model of computation in which the adversary is only limited by the amount of time and computational power available. Other names used are bare model and plain model.

MUSE, commercially known as Hi-Vision was a Japanese analog high-definition television system, with design efforts going back to 1979.

<span class="mw-page-title-main">Moni Naor</span> Israeli computer scientist (born 1961)

Moni Naor is an Israeli computer scientist, currently a professor at the Weizmann Institute of Science. Naor received his Ph.D. in 1989 at the University of California, Berkeley. His advisor was Manuel Blum.

<span class="mw-page-title-main">Progressive Graphics File</span> File format

PGF is a wavelet-based bitmapped image format that employs lossless and lossy data compression. PGF was created to improve upon and replace the JPEG format. It was developed at the same time as JPEG 2000 but with a focus on speed over compression ratio.

In cryptography, the dining cryptographers problem studies how to perform a secure multi-party computation of the boolean-XOR function. David Chaum first proposed this problem in the early 1980s and used it as an illustrative example to show that it was possible to send anonymous messages with unconditional sender and recipient untraceability. Anonymous communication networks based on this problem are often referred to as DC-nets.

PenTile matrix is a family of patented subpixel matrix schemes used in electronic device displays. PenTile is a trademark of Samsung. PenTile matrices are used in AMOLED and LCD displays.

Amos Fiat is an Israeli computer scientist, a professor of computer science at Tel Aviv University. He is known for his work in cryptography, online algorithms, and algorithmic game theory.

The notion of non-malleable codes was introduced in 2010 by Dziembowski, Pietrzak, and Wichs, for relaxing the notion of error-correction and error-detection. Informally, a code is non-malleable if the message contained in a modified code-word is either the original message, or a completely unrelated value. Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction and error-detection is impossible; for example, when the attacker can completely overwrite the encoded message. Although such codes do not exist if the family of "tampering functions" F is completely unrestricted, they are known to exist for many broad tampering families F.

Quantum secret sharing (QSS) is a quantum cryptographic scheme for secure communication that extends beyond simple quantum key distribution. It modifies the classical secret sharing (CSS) scheme by using quantum information and the no-cloning theorem to attain the ultimate security for communications.

References

  1. ↑ Naor, Moni; Shamir, Adi (1995). "Visual cryptography". Advances in Cryptology – EUROCRYPT'94. Lecture Notes in Computer Science. Vol. 950. pp. 1–12. doi:10.1007/BFb0053419. ISBN   978-3-540-60176-0.
  2. ↑ Verheul, Eric R.; Van Tilborg, Henk C. A. (1997). "Constructions and Properties of k out of n Visual Secret Sharing Schemes". Designs, Codes and Cryptography. 11 (2): 179–196. doi:10.1023/A:1008280705142. S2CID   479227.
  3. ↑ Ateniese, Giuseppe; Blundo, Carlo; Santis, Alfredo De; Stinson, Douglas R. (2001). "Extended capabilities for visual cryptography". Theoretical Computer Science. 250 (1–2): 143–161. doi:10.1016/S0304-3975(99)00127-9.
  4. ↑ Jiao, Shuming; Feng, Jun; Gao, Yang; Lei, Ting; Yuan, Xiaocong (2020). "Visual cryptography in single-pixel imaging". Optics Express. 28 (5): 7301–7313. arXiv: 1911.05033 . doi:10.1364/OE.383240. PMID   32225961. S2CID   207863416.
  5. ↑ Gnanaguruparan, Meenakshi; Kak, Subhash (2002). "Recursive Hiding of Secrets in Visual Cryptography". Cryptologia. 26: 68–76. doi:10.1080/0161-110291890768. S2CID   7995141.
  6. ↑ Cook, Richard C. (1960) Cryptographic process and enciphered product, United States patent 4,682,954.
  7. ↑ Carlson, Carl O. (1961) Information encoding and decoding method, United States patent 3,279,095.
  8. ↑ Kafri, O.; Keren, E. (1987). "Encryption of pictures and shapes by random grids". Optics Letters. 12 (6): 377–9. Bibcode:1987OptL...12..377K. doi:10.1364/OL.12.000377. PMID   19741737.
  9. ↑ Arazi, B.; Dinstein, I.; Kafri, O. (1989). "Intuition, perception, and secure communication". IEEE Transactions on Systems, Man, and Cybernetics. 19 (5): 1016–1020. doi:10.1109/21.44016.
  10. ↑ Askari, Nazanin; Moloney, Cecilia; Heys, Howard M. (November 2011). Application of Visual Cryptography to Biometric Authentication. NECEC 2011. Retrieved 12 February 2015.
  11. ↑ Horng, Gwoboa; Chen, Tzungher; Tsai, Du-Shiau (2006). "Cheating in Visual Cryptography". Designs, Codes and Cryptography. 38 (2): 219–236. doi:10.1007/s10623-005-6342-0. S2CID   2109660.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.