CryptoDB
Merkle Puzzles are Optimal
Authors: | |
---|---|
Download: | |
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 }