sent back (in cleartext) from Alice to Bob, but has no way to map that to the secret key Y that Bob and Alice are now using for their ongoing communication, because the value of X within each message was randomly generated. Complexity and security analysis The parameters of the puzzle game can be chosen to make it considerably harder to for an eavesdropper to break the code than for the parties to communicate, but Merkle puzzles do not provide the enormous qualitative differences in difficulty that are required for (and define) security in modern cryptography. 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 m ≈ n, the effort for Eve has roughly quadratic complexity compared to Alice and Bob, i.e., her computation time is on the order of the square of theirs. n should thus be selected large enough 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 [pdf] External links Ralph Merkle, Secure Communications over Insecure Channels (1974): A history of the idea and its publication, with an interview from the year 1995, Edited by Arnd Weber Ralph Merkle, 1974 project proposal for CS 244 at U.C. Berkeley. Ralph Merkle, Dec. 7, 1975, "Secure Communication Over Insecure Channels" Key-agreement protocols