You are looking at a specific version 20090419:235455 of this paper. See the latest version.

Paper 2008/032

Merkle Puzzles are Optimal

Boaz Barak, Mohammad Mahmoody-Ghidary

Abstract

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 Omega(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.

Note: This version fixes a bug in the proof of the previous version of this paper, see "Correction of Error" paragraph and Appendix A

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Unknown where it was published
Keywords
ke exchangerandom oracle
Contact author(s)
mohammad @ cs princeton edu
History
2016-06-15: last of 6 revisions
2008-01-28: received
See all versions
Short URL
https://ia.cr/2008/032
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.