Merkle's Puzzles

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

Description[edit]

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 sent 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.

High Level Description[edit]

  1. Bob generates 2N messages containing, "This is message X. This is the symmetrical key, Y", where X is an identifier, and Y is a secret key meant for symmetrical encryption. Both X and Y are unique to each message. All the messages are encrypted in a way such that a user may conduct a brute force attack on each message with some difficulty. Bob sends all the encrypted messages to Alice.
  2. Alice receives all the encrypted messages, and randomly chooses a single message to brute force. After Alice discovers both the identifier X and the secret key Y inside that message, she encrypts her clear text with the secret key Y, and sends that identifier (in cleartext) with her cipher text to Bob.
  3. Bob finds the secret key paired with that identifier, and deciphers Alice's cipher text with that secret key.

Complexity[edit]

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(mn) of time. If mn, 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.

Quadratic complexity is typically not considered secure enough against an attacker (or on the other extreme, for large m,n, convenient enough for the participants) for practical real-world cryptographic applications. However, this scheme has the distinction of being one of the first examples of public-key cryptography, and was an inspiration for the Diffie-Hellman key exchange protocol, which has much higher complexity, relying on the discrete logarithm problem.

In 2008 Boaz Barak and Mohammad Mahmoody-Ghidary showed ("Merkle Puzzles Are Optimal") that this quadratic bound cannot be improved upon.

References[edit]

  • Merkle, R. C. (April 1978). "Secure Communications over Insecure Channels". Communications of the ACM. 21 (4): 294–299. doi:10.1145/359460.359473.  [pdf]

External links[edit]