In cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, Merkle's Puzzles is an early construction for a public-key cryptosystem, a protocol devised by Ralph Merkle

Ralph Merkle

Ralph C. Merkle is a researcher in public key cryptography, and more recently a researcher and speaker on molecular nanotechnology and cryonics...

 in 1974 and published in 1978. It allows two parties to agree on a shared secret

Shared secret

In cryptography, a shared secret is a piece of data, known only to the parties involved, in a secure communication. The shared secret can be a password, a passphrase, a big number or an array of randomly chosen bytes....

 by exchanging messages, even if they have no secrets in common beforehand.

Description

Suppose Alice and Bob

Alice and Bob

The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...

 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

Key (cryptography)

In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...

; the key must be short enough to allow a brute force attack

Brute force attack

In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...

. 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 more computationally expensive for Eve than it is for Alice.

Complexity

Suppose that the number of puzzles sent by Bob is m, and it takes both Bob and Alice n steps of computation to solve one puzzle. Then both can deduce a common session key within a time complexity of O(m+n). Eve, in contrast, is required to solve all puzzles, which takes her O(m*n) of time. If m ≈ n, the effort for Eve has roughly quadratic complexity compared to Alice and Bob. n should thus be selected such that computation is still feasible for Alice and Bob while it surmounts the capabilities of Eve.

External links

• Ralph Merkle, Secure Communications over Insecure Channels (1974): A history of the idea and its publication

• Ralph Merkle, 1974 project proposal for CS 244 at U.C. Berkeley.