Breaking One-Round Key-Agreement Protocols in the Random Oracle Model
| dc.creator | Sotakova, Miroslava | |
| dc.date | 2008-01-30 | |
| dc.date | 2009-03-24 | |
| dc.date.accessioned | 2026-07-07T12:55:02Z | |
| dc.date.available | 2026-07-07T12:55:02Z | |
| dc.description | In this paper we study one-round key-agreement protocols analogous to Merkle's puzzles in the random oracle model. The players Alice and Bob are allowed to query a random permutation oracle $n$ times and upon their queries and communication, they both output the same key with high probability. We prove that Eve can always break such a 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 shown recently by Barak and Mahmoody-Ghidary. The results in this paper have been found independently of their work. | |
| dc.description | 6 pages | |
| dc.identifier | https://arxiv.org/abs/0801.4714 | |
| dc.identifier | http://arxiv.org/abs/0801.4714 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/224141 | |
| dc.subject | Computational Complexity | |
| dc.subject | Cryptography and Security | |
| dc.title | Breaking One-Round Key-Agreement Protocols in the Random Oracle Model | |
| dc.type | text |