## CryptoDB

### Paper: Merkle Puzzles are Optimal

Authors: Boaz Barak Mohammad Mahmoody-Ghidary URL: http://eprint.iacr.org/2008/032 Search ePrint Search Google 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},