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
-
CC BY