International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Breaking One-Round Key-Agreement Protocols in the Random Oracle Model

Authors:
Miroslava Sotakova
Download:
URL: http://eprint.iacr.org/2008/053
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-17730,
  title={Breaking One-Round Key-Agreement Protocols in the Random Oracle Model},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Merkle's puzzles, key-agreement, random oracle model},
  url={http://eprint.iacr.org/2008/053},
  note={arxiv, cs.CC mirka@daimi.au.dk 13908 received 30 Jan 2008},
  author={Miroslava Sotakova},
  year=2008
}