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 $\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.
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 PuzzlesRandom OracleKey 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}
}
