Merkle Puzzles

The first public-key encryption proposed by an academic researcher was Ralph Merkle’s “puzzle-based” scheme which he submitted to the Communications of the ACM in 1975

R. C. Merkle. Secure communications over insecure channels. Commun. ACM, 21(4):294-299, 1978. Originally submitted in August 1975 .

• Assumptions: is an "ideal" 1 -to- 1 one-way function, that requires almost times as much time to invert as it does to compute. Let

• Private Key:   that are chosen independently at random in
• Public Key:  
• Encrypt:   Pick at random in , and if appears in the public-key then output where is a "hardcore bit function" that can be obtained, e.g., by the method of Goldreich-Levin. If is not in the public-key then try again.
• Decrypt: : Output where is such that .

In Merkle's puzzle-based public-key encryption, the honest parties make invocation to an ideal one-way function, while an adversary making invocations would not be able to break it

Merkle’s scheme can yield up to a quadratic gap between the work required to run the scheme and work required to break it, in an idealized (and not fully specified) model. Biham, Goren and Ishai showed that this model can be instantiated using exponentially strong one way functions.

E. Biham, Y. J. Goren, and Y. Ishai. Basing weak public-key cryptography on strong one-way functions. In Theory of Cryptography, Fifth Theory of Cryptography Conference, TCC 2008, pages 55-72, 2008.

Merkle conjectured that it should be possible to obtain a public-key scheme with an exponential gap between the work of the honest parties and the adversary but was unable to come up with a concrete candidate. (The first to do so would be Diffie–Hellman key exchange.) It showed that Merkle’s original protocol is optimal in the setting where we model the one-way function as a random oracle and measure running time in terms of the number of queries to this function.

B. Barak and M. Mahmoody-Ghidary. Merkle puzzles are optimal - an -query attack on any key exchange from a random oracle. In Advances in Cryptology - CRYPTO 2009, Springer (LNCS 5677), pages 374-390, 2009 .

We should note that, although security is extremely far from what we could hope for, it is not completely unacceptable. As pointed out by Biham et al., any superlinear security guarantee only becomes better with technological advances, since, as the honest parties can afford more computation, the ratio between their work and the adversary's grows.

E. Biham, Y. J. Goren, and Y. Ishai. Basing weak public-key cryptography on strong one-way functions. In Theory of Cryptography, Fifth Theory of Cryptography Conference, TCC 2008, pages 55-72, 2008 .