Cryptology ePrint Archive: Report 2008/053
Breaking One-Round Key-Agreement Protocols in the Random Oracle Model
Miroslava Sotakova
Abstract: In this work we deal with one-round key-agreement protocols, called Merkle's Puzzles, in the random oracle model, where the players Alice and Bob are allowed to query a random permutation oracle $n$ times. We prove that Eve can always break the protocol by querying the oracle $O(n^2)$ times. The long-time unproven optimality of the quadratic bound in the fully general, multi-round scenario has been proven recently by Barak and Mahmoody-Ghidary. The results in this paper have been found independently of their work.
Category / Keywords: public-key cryptography / Merkle's puzzles, key-agreement, random oracle model
Publication Info: arxiv, cs.CC
Date: received 30 Jan 2008
Contact author: mirka at daimi au dk
Available format(s): PDF | BibTeX Citation
Version: 20080131:120227 (All versions of this report)
Short URL: ia.cr/2008/053
[ Cryptology ePrint archive ]