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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. arxiv, cs.CC
Keywords
Merkle's puzzleskey-agreementrandom oracle model
Contact author(s)
mirka @ daimi au dk
History
2008-01-31: received
Short URL
https://ia.cr/2008/053
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/053,
      author = {Miroslava Sotakova},
      title = {Breaking One-Round Key-Agreement Protocols in the Random Oracle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2008/053},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/053}},
      url = {https://eprint.iacr.org/2008/053}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.