[BM09] Merkle Puzzles Are Optimal — An O(n²)-Query Attack on Any Key Exchange from a Random Oracle

Authors: Boaz Barak, Mohammad Mahmoody-Ghidary | Venue: CRYPTO 2009 | Source

Abstract

We show that every key exchange protocol in the random oracle model in which the honest parties make at most $n$ queries to the oracle can be broken by an eavesdropper making $O(n^2)$ oracle queries. This matches the quadratic gap achieved by Merkle’s Puzzles Mer78, showing that protocol is optimal up to constants. Our result improves on the $\Omega (n^6)$-query lower bound of Impagliazzo and Rudich IR89, settling the complexity of key agreement in the random oracle model.