Science Fair Project Encyclopedia
In cryptography, Merkle's Puzzles is an early construction for a public-key cryptosystem, a protocol devised by Ralph Merkle in 1974 and published in 1978. It allows two parties to agree on a shared secret by exchanging messages, even if they have no secrets in common beforehand.
Suppose Alice and Bob wish to communicate. Bob can send a message to Alice as follows: first he creates a large number of puzzles, each of a moderate amount of difficulty — it must be possible for Alice to solve the puzzle with a moderate amount of computing effort. The puzzles are in the form of an encrypted message with an unknown key; the key must be short enough to allow a brute force attack. Bob sends all of the puzzles to Alice, who chooses one randomly, and solves it. The encrypted solution contains an identifier, as well as a session key, so Alice can communicate back to Bob which puzzle she has solved. Both parties now have a common key; Alice, because she solved a puzzle, and Bob, because he set the puzzle. Any eavesdropper (Eve, say) has a harder task — she does not know which puzzle was solved by Alice. Her best strategy is to solve all the puzzles, but since there are so many, this is a great deal more computationally costly for Eve than it is for Alice.
- R. C. Merkle, "Secure Communications over Insecure Channels" Communications of the ACM 21(4), pp294–299 (April 1978).
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details