Visual Secret Sharing

Six thieves share a numbered bank account, and none of them trusts another alone with the number. Any two together may withdraw. That puzzle, as Moni Naor tells it, has a twist: the pair will arrive at the bank without a computer, so whatever each thief carries must be combined by hand and read by eye.

The answer he and Adi Shamir presented at Eurocrypt in 1994 was a transparency for each thief. Each sheet is a field of black and clear dots that looks like static. Lay two on top of each other, line them up, and the number appears, darker than its background. Nobody does any arithmetic. The decoding is performed by the human visual system.

What lifts the idea above a parlor trick is the claim attached to it. A single sheet does not merely resist analysis. It holds no information about the picture at all, in a sense that can be written down and checked by counting. That claim, what it costs, and how easily a careless hand gives it away, are the whole subject.

Splitting a secret so the pieces say nothing

The older idea is secret sharing. In November 1979 Shamir described how to divide a piece of data into n pieces so that any k of them make it easy to compute, while k - 1 or fewer leave it completely undetermined, with all of its possible values still equally likely. He called this a (k, n) threshold scheme, and he had cryptographic keys in mind. A key kept in one well-guarded place is lost to a single misfortune. A key copied to many places is exposed by a single breach.

A threshold scheme escapes that trade. A report from the National Institute of Standards and Technology calls secret sharing a fundamental technique. A key is split into shares held by several parties. It can be rebuilt from a threshold number of them but not from fewer, so the leak of one or a few shares does not reveal it.

Visual cryptography keeps the definition and changes the machinery. Shamir’s 1979 pieces are numbers, and putting them together takes interpolation. Naor and Shamir’s pieces are pictures, and putting them together takes a steady hand. The dealer who prepares the sheets still needs a trusted computer. The people who hold them do not.

One pixel, four squares, a coin

The construction works one pixel at a time. Each pixel of the secret becomes a small block of subpixels on every sheet. In the square form of the two-sheet scheme the block is two by two, and every block on every sheet has exactly two black subpixels and two clear ones. Six arrangements do that: two horizontal, two vertical and two diagonal.

For a white pixel the dealer picks one arrangement at random and prints the same block on both sheets. For a black pixel the dealer picks at random again, prints that block on one sheet and its complement on the other. Stacked, a white pixel still shows two black subpixels out of four. A black pixel shows four out of four. The eye reads medium grey as white and solid black as black.

Now look at one sheet alone. Whatever the secret pixel was, its block is a random choice of two black subpixels among four. A white pixel and a black pixel produce the same possible blocks with the same frequencies. Since every pixel gets a fresh, independent choice, looking at groups of blocks helps no more than looking at one.

Here is an example to try. Type a short message and render it at 160 by 96 pixels. Each share comes out at 320 x 192, because every pixel became four. Measure the black on either share: 50.0 percent over the letters and 50.0 percent over the background. Stack the two and the background stays at 50 percent while the letters go to 100. Print each subpixel as 6 printer dots at 600 dots per inch and a subpixel is 0.254 mm wide, so the whole share is about 81 by 49 mm.

What provably means here

The standard for this kind of claim was set by Claude Shannon in 1949. He defined perfect secrecy by requiring that, after an enemy intercepts a cryptogram, the probabilities of the various messages are identically what they were before the interception. Seeing the ciphertext changes nothing about what the enemy should believe. Shannon showed that this is possible, that the Vernam system realizes it, and that it needs as many possible keys as there are possible messages.

Naor and Shamir’s security condition is the same idea stated for sheets. A scheme is two collections of small matrices, one used for white pixels and one for black. The condition is that for any group of fewer than k sheets the two collections, restricted to those sheets, contain the same matrices with the same frequencies. They conclude that even an infinitely powerful cryptanalyst gains no advantage in deciding whether a shared pixel was white or black.

Because the collections are finite, the condition can be verified by exhaustion and not merely argued. List every group of sheets too small to qualify. For each, tabulate the subpixel patterns it would see for a white pixel and for a black one, and compare the two tallies entry by entry. If they are identical, that group learns nothing. Change a single entry of a matrix and the tallies part company.

The paper draws the family resemblance itself: the system is similar to a one-time pad, in the sense that each page of ciphertext is decrypted with a different transparency. The pad’s oldest rule carries over. In the two-sheet scheme, reuse one sheet with two secrets and its two partners give the game away, because laid on each other they go fully black exactly where the secrets differ. Naor and Benny Pinkas make the same point about their own visual methods, in which each transparency can be used only once.

One qualification belongs beside the proof. It assumes the dealer’s coin is truly random. A browser’s secure generator, by its own documentation, is a pseudo-random generator seeded with enough entropy and suitable for cryptographic purposes. That is strong, but it is not the coin of the theorem. An ordinary seeded generator is far worse, even a fast one that passes tests of randomness as Marsaglia’s xorshift generators do, because its whole output follows from its seed. The Internet’s guidance on randomness warns that pseudo-random processes used for secret quantities can result in pseudo-security, since an attacker may find it easier to reproduce the generator’s environment and search a small set of possibilities.

The price: size, contrast and a steady hand

Perfect secrecy on plastic is not free. The first cost is resolution. Every pixel becomes several subpixels, so a share is several times larger than the secret, or the secret must be several times coarser than the printer. A photograph has to be reduced to pure black and white first, by a threshold or by an error-diffusion method such as the one Floyd and Steinberg published in 1976.

The second cost is contrast. White never comes back as white. In the two-sheet scheme it returns half black, which Doug Stinson’s introduction describes as a 50 percent loss of contrast in an image that should still be visible.

Both costs grow with the number of sheets that must agree. For a scheme in which all k of k sheets are needed, Naor and Shamir build one with 2 to the power k - 1 subpixels per pixel and prove that no such scheme can use fewer. The gap between black and white shrinks to a single subpixel in that many. Four sheets therefore need 8 subpixels a pixel, and a stacked white pixel already has seven of the eight black. The picture is there, as a faint darkening of a dark field.

Schemes in which any k of n sheets suffice exist in general, and the small ones are simple. For any two of n, each block has one black subpixel among n. Two sheets of a white pixel put it in the same place, and two sheets of a black pixel put it in different places. Blundo, De Santis and Stinson later characterized the two-of-n schemes with the best contrast and bounded what larger thresholds can achieve.

The third cost is mechanical, and it defeats most first attempts. The sheets must coincide to a fraction of a subpixel across their whole area. In the example above, sliding one share sideways by a single subpixel takes the measured contrast from one half to about zero, and the message is gone. A printer that scales the page to fit does the same damage everywhere at once, and so does an image editor that resamples a share. Shares belong in a lossless format such as PNG, not in ordinary JPEG, whose transform-based processes are lossy.

Where it earns its keep

Stacking is not the only way to combine sheets. Tuyls, Hollmann, van Lint and Tolhuizen described a system based on the polarisation of light and showed that very efficient schemes exist there when all n sheets are required. On an ordinary screen the simplest relative is exclusive-or: all sheets but one are pure random bits, and the last is the secret combined with every one of them. A device returns the secret exactly, with no enlargement. Transparencies cannot do this, because a black subpixel on one sheet cannot be undone by another laid over it.

So what is the visual version for? Its inventors pictured a page of ciphertext that could be mailed or faxed, with a transparency as the key. Shamir also patented a related use, filed in April 1994 and granted in January 1996: a printed watermark that stays invisible until a transparent developer sheet is laid on the document. Naor and Pinkas proposed visual methods for a person who must check a message with no trusted computing device in hand, as when using a smartcard.

Those uses share a shape: a human reader, no trusted computer at the moment of reading, and a secret small enough to survive low resolution. Outside that shape the method is a poor substitute for ordinary encryption. It carries a picture of a few thousand pixels. It needs fresh sheets for every message. It says nothing about who made a sheet or whether one was swapped. And anyone who gathers enough sheets reads the secret with no further effort.

What it offers instead is rare: a security proof anyone can test by hand. Print two sheets, hold one to the light, and look for the message. The failure is the demonstration. There is nothing there to find.