From: sommerfeld@orchard.medford.ma.us (Bill Sommerfeld)
Date: Tue, 17 May 94 08:42:29 PDT
To: cypherpunks@toad.com
Subject: visual cryptography (talk by Shamir yesterday at MIT).
Message-ID: <199405171533.LAA00402@orchard.medford.ma.us>
MIME-Version: 1.0
Content-Type: text/plain


Here's a brief summary of Shamir's talk at MIT yesterday, which was
well attended.

The problem he solved was to create a cryptosystem which is as secure
as possible, but can be decoded (with some care) using only the human
visual system.

Shamir described two applications of this system:
	- sending encrypted faxes where you don't have control over
the receiving fax machine.
	- demostrating cryptography to a lay audience..

The cryptosystem in its simplest form encrypts a (bitmap) image as a
similar image but with half the resolution.

for each pixel in the plaintext, you expand it to four pixels in the
cyphertext and key.

The key (a "one time pad") is printed on a transparent material
(overhead projector transparancies).

each 2x2 grid in the key has a random selection of two pixels darkened:

There are six different ways to do this:

	|  | |##|   |# |   | #|  | #|  |# |  
	|##| |  |   | #|   |# |  | #|  |# |   

You then produce the plaintext as follows:

	- for each "black" spot on the plaintext image, color in the
two pixels not colored in on the ciphertext.
	- for each "white" spot on the plaintext image, color in the
same two pixels as the key.

Line the key up with the cyphertext (registration is somewhat tricky
particularly as the pixel size gets really small), and you get an
image which ranges in density from 50% gray to 100% gray.

as a practical matter, it works better if you use alternating vertical
and horizontal bars in a chessboard pattern because the image starts
to appear when you get the registration within just under 2 pixels.

Shamir also described extensions of this system to:
	- k of k secret sharing schemes
	- k of n secret sharing schemes
		these work best when `k' is small, though `n' can get large
		without messing up the scheme (he claimed that 3 of
		1000 was practical).
	- grey scale images
	- steganography
		 Both key and ciphertext contain an image of your choice;
		 when overlaid, their images disappear and the plaintext
	         appears.

	This is done by encoding both cipher and key images using a
		"white=50%, black=75%" method; the
		resulting plaintext is encoded using a
		"white=75%, black=100%" method.

					- Bill