International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Merkle Puzzles are Optimal

Authors:
Boaz Barak
Mohammad Mahmoody-Ghidary
Download:
URL: http://eprint.iacr.org/2008/032
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-17709,
  title={Merkle Puzzles are Optimal},
  booktitle={IACR Eprint archive},
  keywords={ke exchange, random oracle},
  url={http://eprint.iacr.org/2008/032},
  note={ mohammad@cs.princeton.edu 14070 received 23 Jan 2008, last revised 10 Jul 2008},
  author={Boaz Barak and Mohammad Mahmoody-Ghidary},
  year=2008
}