Cryptology ePrint Archive: Report 2008/032

Merkle's Key Agreement Protocol is Optimal: An $O(n^2)$ Attack on any Key Agreement from Random Oracles

Boaz Barak and Mohammad Mahmoody

Abstract: We prove that every key agreement 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 who makes $O(n^2)$ queries to the oracle. This improves on the previous $\Omega(n^6)$ query attack given by Impagliazzo and Rudich (STOC '89) and resolves an open question posed by them.

Our bound is optimal up to a constant factor since Merkle proposed a key agreement protocol in 1974 that can be easily implemented with $n$ queries to a random oracle and cannot be broken by any adversary who asks $o(n^2)$ queries.

Category / Keywords: Merkle Puzzles, Random Oracle, Key Agreement

Original Publication (with major differences): IACR-CRYPTO-2009

Date: received 23 Jan 2008, last revised 15 Jun 2016

Contact author: mohammad at cs virginia edu

Available format(s): PDF | BibTeX Citation

Note: This is the full version.

Version: 20160615:184949 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]