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

Boaz Barak; Mohammad Mahmoody

Paper 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 $Ω (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 queries to a random oracle and cannot be broken by any adversary who asks queries.

Note: This is the full version.

Metadata

Available format(s): PDF
Publication info: A major revision of an IACR publication in CRYPTO 2009
Keywords: Merkle Puzzles Random Oracle Key Agreement
Contact author(s): mohammad @ cs virginia edu
History: 2016-06-15: last of 6 revisions; 2008-01-28: received; See all versions
Short URL: https://ia.cr/2008/032
License: CC BY

BibTeX

@misc{cryptoeprint:2008/032,
      author = {Boaz Barak and Mohammad Mahmoody},
      title = {Merkle's Key Agreement Protocol is Optimal: An $O(n^2)$ Attack on any Key Agreement from Random Oracles},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/032},
      year = {2008},
      url = {https://eprint.iacr.org/2008/032}
}

Paper 2008/032

Merkle's Key Agreement Protocol is Optimal: An O(n2) Attack on any Key Agreement from Random Oracles

Abstract

Metadata

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