2026-08-17T09:43:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24362 2025-12-12T14:53:43Z ddc:004 open_access

Key-Agreement with Perfect Completeness from Random Oracles Mazor, Noam Key-Agreement Random Oracle Merkle’s Puzzles Perfect Completeness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noam Mazor 2025 Is Part Of LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2025.12 urn:nbn:de:0030-drops-243628 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.12 eng https://creativecommons.org/licenses/by/4.0/legalcode