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