In cryptography, Merkle's Puzzles is an early construction for a public-key cryptosystem, devised by Ralph Merkle in 1974 and published in 1978. The protocol allows two parties to agree on a shared secret by exchanging messages, even if they share no secret beforehand. The scheme provides a quadratic security gap between legitimate parties and an eavesdropper, and is recognized as a precursor to public-key cryptography in the modern sense.

Description

Suppose Alice and Bob wish to communicate. Bob first creates a large number of puzzles, each of moderate difficulty: it must be possible for Alice to solve a puzzle with a moderate amount of computing effort. The puzzles take the form of encrypted messages with unknown keys short enough to allow a brute force attack. Bob sends all the puzzles to Alice, who chooses one at random and solves it. The decrypted solution contains an identifier and a session key, so Alice can tell Bob which puzzle she solved. Both parties now share a common key. An eavesdropper, who does not know which puzzle Alice chose, must solve every puzzle on average in order to find the key.

In 2009, Boaz Barak and Mohammad Mahmoody-Ghidary showed that the quadratic bound is optimal: no key-agreement protocol built from a random oracle can do better than O(n<sup>2</sup>) against an O(n)-query attacker.

See also

  • Diffie–Hellman key exchange
  • Public-key cryptography
  • Key-agreement protocol

References

  • Ralph Merkle, "Secure Communications over Insecure Channels (1974)" — a history of the idea and its publication, with a 1995 interview; edited by Arnd Weber
  • Ralph Merkle, 1974 project proposal for CS 244 at UC Berkeley
  • Ralph Merkle, "Secure Communication Over Insecure Channels" (December 7, 1975)