Merkle Puzzles are Optimal
| COMPUTER SCIENCE/DISCRETE MATH I | |
| Topic: | Merkle Puzzles are Optimal |
| Speaker: | Mohammad Mohmoody Ghidary |
| Affiliation: | Princeton University |
| Date: | Monday, April 7 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
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 $\Tilde{O}(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 $\Tilde{O}(n^{12})$ attack of Impagliazzo and Rudich. This bound again optimal up to a constant factor since Merkle's protocol can be adapted to this model as well.
Joint work with Boaz Barak