Visual Cryptography

Suppose that 6 thieves have deposited their loot in a numbered Swiss bank account. Being thieves, they do not trust each other not to withdraw the money and take the next plane to Brazil. However, being sentimental, they do not assume a conspiracy of two or more thieves that will try to take out the money without "authorization" and they want any two of them to able to withdraw the money. They therefore want to divide the secret number into shares so that from each share you cannot learn anything about the secret number, but from any two shares you can reconstruct the secret number.

This problem is the by now classical secret sharing problem (see Doug Stinson's bibliography on secret sharing schemes ). The twist here is that the thieves's representatives will not have a computer with them when they come to withdraw the money, so they want to be to it visually: each thief gets a transparency. The transparency should yield no information about the secret number (even implicitly). However, by taking any two transparencies, stacking them together and aligning them, the secret number should "pop out". The transparencies themselves will be prepared by a (trusted) computer. How can this be done?

For starters, can you think of a method that will let two thieves split a secret between them? Solution

Back to the Puzzler page