Alice and Bob wish to communicate secretly. However, they are apart from each other, and they have only one messenger they can use, who is untrustworthy. In fact, they are certain that any message they send to each other will be delivered, but will first pass through the hands of Eve. Alice and Bob want to avoid Eve reading any of their messages. They have a metal box to hold their messages, equipped with a large clasp that can fit multiple padlocks, and they each have several padlocks and corresponding keys. No one, including Eve, would be able to open the box when it is locked with a padlock. However, Alice and Bob do not have the keys to each other’s padlocks, and the only way of sending copies of the keys to each other would be through the same messenger, who would also allow Eve to copy the keys. Nevertheless, there is a way they can use the box to transmit messages without Eve being able to read them. What can they do?
Answer and Explanation
This problem inspired real-world cryptographers to solve what is known as the key distribution problem. People sending encoded messages have the same problem as Alice and Bob: in order to decode the message, the recipient must have the key, but the key itself must also be kept secret. The modern solution to this problem is public key cryptography. The solution for Alice and Bob is much simpler.
First, Alice places her secret message in the box and locks it with one of her padlocks. She then has it sent to Bob via their untrustworthy messenger. Although the box passes through Eve’s hands, she cannot open it, as she does not have the key to Alice’s padlock. Bob does not have the key either, so he cannot read the message. Instead, he adds his own padlock and sends the box back to Alice. In transit, Eve has no access to the message, as the box is doubly locked. When Alice receives the box, she removes her padlock and sends the box back to Bob. Eve again has no access, as the box is still secured with Bob’s padlock. When Bob receives it, however, he has only to remove his own padlock in order to read Alice’s message.
This problem — along with many other interesting secret code problems — is discussed in Simon Singh’s The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography.