**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.

**Category / Keywords: **ke exchange, random oracle

**Date: **received 23 Jan 2008, last revised 19 Apr 2009

**Contact author: **mohammad at cs princeton edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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

**Version: **20090419:235455 (All versions of this report)

**Short URL: **ia.cr/2008/032

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]