Merkle Puzzles are Optimal
Boaz Barak, Mohammad Mahmoody · arXiv (Cornell University) · 2008
We prove that every key exchange protocol in the random oracle model in which the honest users make at most n queries to the oracle can be broken by an adversary making O(n 2) queries to the oracle. This improves on the previous ˜ Ω(n 6) query attack given by Impagliazzo and Rudich (STOC ’ 89). Our bound is optimal up to a constant factor since Merkle (CACM ’78) gave an n query key exchange protocol in this model that cannot be broken by an adversary making o(n 2) queries. Our result extends to an O(n 2) query attack in the random permutation model, improving on the pervious ˜ Ω(n 12) attack of Impagliazzo and Rudich. This bound again is optimal up to a constant factor since Merkle’s protocol can be adapted to this model as well. 1