Paper 2023/1265
Key-Agreement with Perfect Completeness from Random Oracles
Abstract
In the Random Oracle Model (ROM) all parties have oracle access to a common random function, and the parties are limited in the number of queries they can make to the oracle. The Merkle’s Puzzles protocol, introduced by Merkle [CACM ’78], is a key-agreement protocol in the ROM with a quadratic gap between the query complexity of the honest parties and the eavesdropper. This quadratic gap is known to be optimal, by the works of Impagliazzo and Rudich [STOC ’89] and Barak and Mahmoody [Crypto ’09]. When the oracle function is injective or a permutation, Merkle’s Puzzles has perfect completeness. That is, it is certain that the protocol results in agreement between the parties. However, without such an assumption on the random function, there is a small error probability, and the parties may end up holding different keys. This fact raises the question: Is there a key-agreement protocol with perfect completeness and super-linear security in the ROM? In this paper we give a positive answer to the above question, showing that changes to the query distribution of the parties in Merkle’s Puzzles, yield a protocol with perfect completeness and roughly the same security.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Key-AgreementRandom OracleMerkle’s PuzzlesPerfect Completeness
- Contact author(s)
- noammaz @ gmail com
- History
- 2023-09-16: revised
- 2023-08-21: received
- See all versions
- Short URL
- https://ia.cr/2023/1265
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1265,
author = {Noam Mazor},
title = {Key-Agreement with Perfect Completeness from Random Oracles},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1265},
year = {2023},
url = {https://eprint.iacr.org/2023/1265}
}
