Cryptology ePrint Archive: Report 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.

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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]