Sharing Keys: Sharing Puzzles

At the time, the accepted wisdom was that you had to share a digital key to communicate in secret and you had to keep everything about that key secret. Ralph Merkle's brilliant insight was that you could pass the secret under the snooper's nose even though he could read every word of it.

His original idea was this. Suppose Alice wants to talk to Bob. She uses her computer to create millions of puzzles for which she, having created them, knows the answers. Each takes some time to solve, but it's fairly easy to do so. All are sent to Bob. The Snooper sees them all too. Bob picks one of them at random and solves it. The answer includes a key and an identifier - a number that says which puzzle was chosen. He sends the puzzle identifier back to Alice. The Snooper sees this identifier too, but without solving all the puzzles, which takes millions of times longer, the Snooper can't tell which key goes with it. Alice can as she created the puzzles - she just looks up which key is hidden in that puzzle in a table. Alice and Bob now know which key they share and can communicate using it. As long as enough puzzles were sent at the start it will take the Snooper far too long to solve them to get the key.

There are still problems with this as a workable method - what if the Snooper has a computer thousands of times faster than Alice and Bob, so can solve the puzzles faster than they can, for example. However, Merkle went on to work on the idea with two other computer scientists, Whit Diffie and Marty Hellman, who had been thinking about the same problem in a slightly different way. Together they fixed the problems and came up with the essence of the idea that is now widespread: Public Key Encryption. All because Ralph Merkle was inspired by a computer science class.

Back