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.
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(n2) 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.
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 MahmoodyGhidary. The results in this paper have been found independently of their work. In this work we prove the tight upper-bound on the number of queries needed to break a keyagreement protocol in the random oracle model. The key-agreement protocol called Merkle’s puzzles, developed by Merkle in 1974 a published in 1978 [3] is one of the earliest example of public-key encryption. Following the protocol, two parties can agree on a secret-key by exchanging messages, assuming that they share no secrets beforehand. Informally, Alice creates a message for Bob in the following way - she constructs a large number of puzzles of moderate difficulty, each of them being possible to solve with Bob’s computational resources. All of them are in the form of an encrypted message with an unknown key that is short enough to allow the brute force attack. After receiving the message from Alice, Bob chooses one puzzle uniformly at random and solves it. The solution contains an identifier and a key. Bob encrypts the identifier with the key, and announces it back to Alice. The solution of the puzzle solved by Bob becomes Alice’s and Bob’s secret-key. Since the puzzle’s identifier is sent to Alice as a message encrypted with a key that is unknown to Eve, the eavesdropper’s best strategy to attack the key-agreement protocol is to solve as many puzzles as possible. To achieve constant probability of success, she has to solve a constant fraction of them, which might require much more computational power than Alice and Bob have. In a similar way we construct a key-agreement protocol in the random oracle scenario, where the computational difficulty of key-agreement is expressed by the number of oracle queries that
This paper proves that it is impossible to construct perfectly complete quantum key agreement protocols (QKA) from quantumly secure one-way functions (OWFs) in a black-box manner.
Specifically, consider any protocol in which Alice and Bob exchange only classical messages, make at most qA and qB quantum queries, respectively, to a Boolean-valued random oracle, and agree on a shared key with certainty. This paper shows that there exists an eavesdropper, given the classical messages, that can recover the shared key with certainty using O((qA+qB)5) classical oracle queries. The bound is independent of the number of rounds, transcript length, key length, and oracle-domain size. Previous results only applies to two-round key agreement (Li et al. CRYPTO 26) or relies on unproven conjectures (Austrin et al. CRYPTO 22).
GPT-5.6 Sol Ultra found this proof in a one-shot conversation and drafted a preliminary version of this paper. The authors are fully responsible for the correctness, writing and discussions of this paper.
Key-agreement protocols whose security is proven in the random oracle model are an important alternative to protocols based on public-key cryptography. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but the parties are limited in the number of queries they can make to the oracle. The random oracle serves as an abstraction for black-box access to a symmetric cryptographic primitive, such as a collision resistant hash. Unfortunately, as shown by Impagliazzo and Rudich [STOC '89] and Barak and Mahmoody [Crypto '09], such protocols can only guarantee limited secrecy: the key of any l-query protocol can be revealed by an O(l^2)-query adversary. This quadratic gap between the query complexity of the honest parties and the eavesdropper matches the gap obtained by the Merkle's Puzzles protocol of Merkle [CACM '78]. In this work we tackle a new aspect of key-agreement protocols in the random oracle model: their communication complexity. In Merkle's Puzzles, to obtain secrecy against an eavesdropper that makes roughly l^2 queries, the honest parties need to exchange Omega(l) bits. We show that for protocols with certain natural properties, ones that Merkle's Puzzle has, such high communication is unavoidable. Specifically, this is the case if the honest parties' queries are uniformly random, or alternatively if the protocol uses non-adaptive queries and has only two rounds. Our proof for the first setting uses a novel reduction from the set-disjointness problem in two-party communication complexity. For the second setting we prove the lower bound directly, using information-theoretic arguments. Understanding the communication complexity of protocols whose security is proven (in the random-oracle model) is an important question in the study of practical protocols. Our results and proof techniques are a first step in this direction.
We make progress towards the impossibility of quantum-computation, classical-communication (QCCC) key agreement by giving the first unconditional polynomial-query attacks that tolerate imperfect completeness in the following settings. First, we give a quantum attack on protocols with arbitrarily many rounds in which both parties' oracle queries and communication are classical before the final round, while local computation may be quantum throughout, and the final round may involve quantum oracle queries and one quantum message. Second, we give a classical attack on constant-round QCCC protocols in which Alice has classical oracle access and Bob may make quantum queries throughout. In both settings, the attacker is computationally unbounded and makes poly(λ) queries to recover the key with nonnegligible probability whenever each party's total honest query bound is at most poly(λ) and the valid agreement probability is inverse-polynomial.
As consequences, we rule out query-bounded IND-CPA security for quantum public-key encryption with classical public and secret keys and classical messages of polynomially bounded length in the QROM in either of two settings: (i) key generation has classical oracle access, while encryption, decryption, and the ciphertext may be quantum; or (ii) encryption has classical oracle access and ciphertexts are classical, while key generation and decryption may have quantum oracle access. Both results assume negligible correctness error and polynomial honest query complexity. Combining the constant-round attack with the constructions of Bartusek and Khurana (CRYPTO 2025), we also rule out constant-round oblivious state preparation with polynomial honest query complexity and negligible correctness error in the QROM against computationally unbounded quantum receivers making polynomially many oracle queries.
A time-lock puzzle allows a sender to hide a message in a puzzle such that recovering the message requires substantially more sequential computation than the time required to generate the puzzle, even when parallel computation is allowed. Applications of time-lock puzzles include timed-release encryption, sealed-bid auctions, electronic voting, fair contract signing, coin flipping, and Byzantine consensus. However, time-lock puzzles are known to be impossible in the classical random oracle model.
To overcome the classical barrier, in this work we consider quantum time-lock puzzles, in which the puzzle itself is a quantum state. Our construction in the quantum random oracle model achieves generation in one oracle round, solving in at most T oracle rounds, and security against polynomial-width quantum adversaries of depth o(T) for every polynomially bounded delay T=T(λ), resolving an open problem posed by Mahmoody, Moran, and Vadhan (2011).
In the random oracle model, the parties are given oracle access to a random member of a (typically huge) function family, and are assumed to have unbounded computational power (though they can only make a bounded number of oracle queries). This model provides powerful properties that allow proving the security of many protocols, even such that cannot be proved secure in the standard model (under any hardness assumption). The random oracle model is also used to show that a given cryptographic primitive cannot be used in a black-box way to construct another primitive; in their seminal work, Impagliazzo and Rudich [STOC ’89] showed that in the random function model – when the function family is the set of all functions – it is impossible to construct (secure) key-agreement protocols, yielding that key-agreement cannot be black-box reduced to one-way functions. Their work has a long line of followup works (Simon [EC ’98], Gertner et al. [STOC ’00] and Gennaro et al. [SICOMP ’05], to name a few), showing that given oracle access to a certain type of function family (e.g., the family that “implements ” public-key encryption) is not sufficient for building a given cryptographic primitive (e.g., oblivious transfer). Yet, in the more general sense, the following fundamental question remained open: What is the exact power of the random oracle model, and more specifically, of the random function model? We make progress towards answering the above question, showing that any (no private input) semi-honest two-party functionality that can be securely implemented in the random function model, can be securely implemented information theoretically (where parties are assumed to be all powerful, and no oracle is given). We further generalize the above result to function families that provide some natural combinatorial property. To exhibit the power of our result, we use the recent information theoretic impossibility result of McGregor et al. [FOCS ’10], to show the existence of functionalities (e.g., inner product) that cannot be computed both accurately and in a differentially private manner in the random function model; yielding that protocols for computing these functionalities cannot be black-box reduced to the existence of one-way functions.