Key-Agreement with Perfect Completeness from Random Oracles

Mazor, Noam

doi:10.4230/LIPIcs.ITC.2025.12

Key-Agreement with Perfect Completeness from Random Oracles

Noam Mazor Simons Institute, UC Berkeley, CA, USA

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.

Keywords and phrases:

Key-Agreement, Random Oracle, Merkle’s Puzzles, Perfect Completeness

Copyright and License:

2012 ACM Subject Classification:

Security and privacy

\rightarrow

Information-theoretic techniques

Related Version:

Full Version: https://eprint.iacr.org/2023/1265.pdf

Acknowledgements:

We thank Tal Yankovitz and Jad Silbak for very useful discussions.

Funding:

Supported in part by NSF CNS-2149305 and NSF CNS-2128519. This work was done while being at Cornell Tech.

DOI:

10.4230/LIPIcs.ITC.2025.12

Event:

6th Conference on Information-Theoretic Cryptography (ITC 2025)

Editor:

Niv Gilboa

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Key-Agreement ([9]) is a fundamental primitive in modern cryptography. Key-Agreement protocols allow two parties, Alice and Bob, to agree on a secret key that is hidden from any eavesdropper, just by publicly communicating with each other. While the above is one of the most important tasks in cryptography, still there are a respectively small number of assumptions from which we know how to construct such protocols ([26, 24, 9, 11, 21, 1, 25, 6, 2, 3, 27]). Moreover, these assumptions are more structured compared to the assumptions which are used to base private-key cryptography, making them more vulnerable to attacks, and arguably less reliable.

The Random Oracle Model

An important alternative to such assumptions is the use of key-agreement protocols with proven security in the Random Oracle Model (ROM). In this model we assume that the parties (and the eavesdropper) have oracle access to an idealized hash function – a perfectly random function $F\colon[N]\to[M]$ . Then, the efficiency of the eavesdropper is measured with respect to the number of oracle calls it needs to make in order to break the security.

Unfortunately, while we usually want the gap between the running time of the honest parties in the protocol and the running time of the adversary to be exponential (or at least super-polynomial), this cannot be achieved in the random oracle model. Indeed, as shown by [18, 4], any protocol in which the honest parties make $\ell$ queries can be broken by an adversary that makes $O(\ell^{2})$ queries. Yet, while this quadratic gap is not ideal, in the lack of other reliable protocols it may be sufficient (see for example [14]).

Merkle’s Puzzles

The above quadratic gap is achievable, using a very elegant and simple protocol, called Merkle’s Puzzles [22]. In this protocol, Alice and Bob each choose $\ell$ random queries, $(x_{1},\dots,x_{\ell})$ and $(y_{1},\dots,y_{\ell})$ respectively, from a domain of size $O(\ell^{2})$ . Then, Alice and Bob use the images of the queries to find an intersecting query (which exists with high probability due to the birthday paradox). Specifically, Alice sends $F(x_{1}),\dots,F(x_{\ell})$ ; Bob then search for indexes $j$ and $k$ such that $F(x_{j})=F(y_{k})$ , and sends $j$ to Alice; Lastly, Alice outputs $x_{j}$ and Bob outputs $y_{k}$ as as their keys.

For security, it is not hard to see that an eavesdropper that wants to learn Alice’s output needs to invert the function $F$ on a random image $F(x_{j})$ , and thus essentially needs to query all the $O(\ell^{2})$ elements in the domain of the function.

When the function $F$ is a random function with a large enough range, the probability that the protocol succeeds, that is, results in an agreement between Alice and Bob, is approaching to $1$ . Indeed, an error can occur only when two distinct queries have the same image. Moreover, when using a more structured function, such as a permutation or any injective function, it follows that Merkle’s Puzzles has perfect agreement probability. Yet, it is an interesting question whether there exists such a key-agreement protocol without assuming any structure on the oracle function. That is:

Is there a key-agreement protocol with perfect agreement and super-linear security in the ROM?

1.1 Our Results

In this paper, we give a positive answer to the above question. More specifically, by changing the distribution of queries in the Merkle’s Puzzles protocol, we get a protocol with perfect agreement and roughly the same security.

Theorem 1 (Main theorem, informal).

There exists a $\ell$ -query key-agreement protocol with perfect agreement in the random oracle model, secure against all $o(\ell^{2})$ -query adversaries.¹¹1In fact, like Merkle’s puzzles, our protocol is a two-message protocol. Therefore, it can be used as a public-key encryption.

See Theorem 3 for the formal statement. As mentioned above, we get this result by changing the query distribution of Merkle’s Puzzles. The main observation is that in our distribution, the parties always have a single query in common. Then, by verifying that the sets of images of the parties only intersect in (exactly) one point, the parties can be sure that the outputs are equal.²²2Choosing a distribution such that Alice and Bob always have an intersection is not hard. Indeed, for $F\colon[\ell]\times[\ell]\to[M]$ , consider the distribution in which Alice samples a random index $i\leftarrow[\ell]$ , and query $F(i,1),\dots,F(i,\ell)$ , while Bob queries $F(1,j),\dots,F(\ell,j)$ for a random $j\leftarrow[\ell]$ . It is not hard to see that $F(i,j)$ is always in the intersection. However, if the parties continue as in Merkle’s Puzzles (namely, Alice sends $F(i,1),\dots,F(i,\ell)$ , and Bob finds the intersection), an eavesdropper can learn all the queries made by Alice, just by simulating Bob.

The protocol

We next describe the query distribution we consider. For simplicity, we think of $F$ as a function over the domain $[\ell]\times[\ell]$ . To choose her queries, Alice samples $\ell$ uniformly random points $x_{1},\dots,x_{\ell}\in[\ell]$ . Then, Alice queries $(1,x_{1}),\dots,(\ell,x_{\ell})$ . On the other side, Bob chooses a random index $j\in[\ell]$ , and queries $(j,1),\dots,(j,\ell)$ . This distribution guarantees that $(j,x_{j})$ is a (unique) intersection between Alice’s and Bob’s queries.

The protocol proceeds similarly to Merkle’s Puzzles: Alice sends $F(1,x_{1}),\dots,F(\ell,x_{\ell})$ to Bob, but in a random order. Bob then searches for an intersection between $F(1,x_{1}),\dots,F(\ell,x_{\ell})$ and his own images, $F(j,1),\dots,F(j,\ell)$ . Crucially, if Bob finds more than one intersection, he notifies Alice and they both output $0$ . Otherwise, he sends the intersection and both parties output its preimage, $(j,x_{j})$ .

The above protocol can be seen as an alternative implementation of Merkle’s original “puzzles” concept in the random oracle setting (a protocol with a query distribution similar to the one considered here was also mentioned in [4] as part of such implementation). In more detail, Merkle considers the notions of puzzles, in which Alice encrypts using $N$ puzzles pairs $\mathopen{}\mathclose{{\left\{(i,s_{i})}}\right\}_{i\in[N]}$ of id $i$ and secret $s_{i}$ , and sends the encryptions to Bob in a random order. Bob then chooses one random encryption and tries to learn the underline pair $(i,s_{i})$ . It then sends the ID $i$ to Alice, and both Alice and Bob output its related secret $s_{i}$ . The idea is that while Bob only needs to solve one such challenge, Eve needs to solve roughly $N$ to learn the secret. In the above protocol, the encryption of a pair $(i,s_{i})$ is done by simply computing $F(i,s_{i})$ .

Security

While the agreement of this protocol follows immediately by the fact that there is always an intersection, the security is a bit less obvious. Indeed, an adversary that tries to invert $z=F(j,x_{j})$ can learn some information on $j$ by observing the other images sent by Alice. Specifically, if the adversary finds a query $(a,b)$ such that $F(a,b)\neq z$ appears in the communication from Alice to Bob, she learns that $j\neq a$ . This can potentially rule out $\ell$ possible preimages. Nevertheless, we are able to show by a simple reduction that this cannot help too much.

To prove the above we consider a balls and boxes game, defined as follows. There are $\ell^{2}$ boxes ordered in $\ell$ rows and $\ell$ columns. In each row, we chose a box uniformly at random and place one ball in it (all other boxes are left empty). All the balls are blue, except exactly one random ball which is red. The goal of the player is to find the red ball, by opening as few boxes as possible.

The security of Merkle’s Puzzles corresponds to a similar game, in which there is only one red ball within a single random row, and there are no other (blue) balls. In this case, it is not hard to see (by the union bound) that any player that opens $q$ boxes, succeeds in probability at most $q/\ell^{2}$ in finding the red ball. To prove that our protocol is secure we first show that the security of the protocol is equivalent to the hardness of the above box and balls game. Then, we show that the presence of the blue balls cannot help the player too much. This is done by observing a simple reduction between the games with and without the blue balls. Specifically, we show that any player that opens $q$ boxes, cannot win with probability larger than $2q/\ell^{2}$ .

Comparison with Merkle’s Puzzles

Similarly to Merkle’s Puzzles, the above protocol is a two-message protocol, and has non-adaptive queries. Both protocols also have near-optimal communication complexity for protocols with these properties [14] (and can be generalized to get other possible tradeoffs between communication and security). The communication complexity of the protocol presented here is also tight with the recent lower bound of [17] for protocols with perfect completeness and non-adaptive queries.

To compare the security of Merkle’s Puzzles and the protocol given in this work, recall that to have an intersection with $1-o(1)$ probability, the parties in Merkle’s Puzzles should query $\ell$ queries each from a domain ${\cal D}$ of size at most $o(\ell^{2})$ . Thus, an $q$ -query adversary can learn the key with probability $q/\mathopen{}\mathclose{{\left|{\cal D}}}\right|=\omega(q/\ell^{2})$ . In this case, we are able to get a slightly better security due to the fact that, in the protocol presented here, there is an intersection with probability $1$ , when the domain of the function is of size (exactly) $\ell^{2}$ .

One advantage of Merkle’s Puzzles is that it is non-interactive, meaning that both Alice and Bob can send their message simultaneously, without waiting to the other message to arrive. The protocol presented here does not have this property, and it is intersting question if such non-interactive protocol with perfect completness exists.

Perspective and Additional Related Work

Perfect primitives in the ROM

Being an idealized hash function, the random oracle model is used to prove black-box separation between cryptographic primitives. Notably, [19] prove a black-box separation between one-way permutations and one-way functions, showing that it is impossible to construct a one-way permutation from random oracles alone.

As mentioned above, [18] prove that there is no key-agreement with super-polynomial security in the ROM, and [4] prove a tight quadratic bound on the security of key-agreement protocols in the ROM. The latter result was generalized by [15] to hold for any semi-honest, no-input, two-party task. Prior to the work of [4], [8] proved a similar quadratic bound on the security of any key-agreement protocol with perfect completeness in the ROM. However, as mentioned by [4], before the work presented here, it was conceivable that every key-agreement protocol with perfect completeness in the ROM can be broken with a linear number of queries to the oracle.

Public-key encryption with perfect completeness

A long line of work is dedicated to the task of eliminating errors in public-key encryption schemes (or, equivalently, two-message key-agreement) and in other cryptographic primitives [12, 10, 16, 20, 5]. As mentioned in [10, 5], even a small decryption error in a public-key encryption scheme can be problematic for some uses. Moreover, as demonstrated by [23, 7], such decryption error can be used by an adversary to attack the cryptographic system.

2 Preliminaries

2.1 Notations

We use calligraphic letters to denote sets and distributions, uppercase for random variables, and lowercase for values and functions. When unambiguous, we will naturally view a random variable as its marginal distribution. For a set ${\cal S}$ , let $x\leftarrow{\cal S}$ denote that $x$ is drawn uniformly from ${\cal S}$ . For $n\in{\mathbb{N}}$ , let $[n]=\mathopen{}\mathclose{{\left\{1,\dots,n}}\right\}$ . For two sets ${\cal A},{\cal B}$ , let ${\cal A}\times{\cal B}=\mathopen{}\mathclose{{\left\{(a,b)\colon a\in{\cal A},% b\in{\cal B}}}\right\}$ .

2.2 Interactive Protocols and Oracle-Aided Protocols

A no-input, two-party protocol $\Pi=(\mathsf{A},\mathsf{B})$ is simply a pair of probabilistic interactive algorithms. The interaction between the parties $\mathsf{A}$ and $\mathsf{B}$ is carried out in rounds, where in each round one party is active and the other is idle. In the $j$ -th round of the protocol, the active party sends a message to the other party, according to its partial view (its randomness and the messages sent in the protocol so far). The transcript of a given execution of the protocol is the list of messages exchanged between the parties in the execution of the protocol.

For a protocol $\Pi$ , we use $({\sf trans},{\rm out}_{\mathsf{A}},{\rm out}_{\mathsf{B}})\leftarrow\Pi$ to denote that $({\sf trans},{\rm out}_{\mathsf{A}},{\rm out}_{\mathsf{B}})$ is a triplet sampled according to the joint distribution induced by $\Pi$ , which contains a transcript of the protocol, an output of party $\mathsf{A}$ , and an output of party $\mathsf{B}$ in a random execution of $\Pi$ .

An oracle-aided no-input two-party protocol $\Pi=(\mathsf{A},\mathsf{B})$ is a pair of interactive oracle-aided algorithms. For a function $f$ , we use $\Pi^{f}=(\mathsf{A}^{f},\mathsf{B}^{f})$ to denote the protocol $\Pi$ when using $f$ as the oracle function. Such a protocol $\Pi=(\mathsf{A},\mathsf{B})$ is a $\ell$ -query protocol, if for every function $f$ , each party always queries $f$ on at most $\ell$ points during the interaction between $\mathsf{A}^{f}$ and $\mathsf{B}^{f}$ .

2.3 Key-Agreement Protocols

We now define key-agreement protocols with respect to a function family ${\cal F}$ . In the random oracle model, we choose ${\cal F}$ to be the all-function family, over some fixed domain and range.

Definition 2 (Key-agreement protocol).

A no-input oracle-aided two-party protocol $(\mathsf{A},\mathsf{B})$ is a $(q,\alpha,\gamma)$ key-agreement protocol with respect to a function family ${\cal F}$ if the following holds:

1.

Agreement:

${\mathrm{Pr}}_{f\leftarrow{\cal F},\\ ({\sf trans},{\rm out}_{\mathsf{A}},{\rm out}_{\mathsf{B}})\leftarrow\Pi^{f}}% \mathopen{}\mathclose{{\left[{\rm out}_{\mathsf{A}}={\rm out}_{\mathsf{B}}}}% \right]\geq 1-\alpha.$
2.

Security: For every algorithm $\mathsf{E}$ , making at most $q$ queries, it holds that

${\mathrm{Pr}}_{f\leftarrow{\cal F},({\sf trans},{\rm out}_{\mathsf{A}},{\rm out% }_{\mathsf{B}})\leftarrow\Pi^{f}}\mathopen{}\mathclose{{\left[\mathsf{E}^{f}({% \sf trans})={\rm out}_{\mathsf{A}}}}\right]\leq\gamma.$

Note that the above security definition requires that the adversary will not be able to guess the key, but the adversary may know some partial information on the output of $\mathsf{A}$ (for example, the first bit). Given such a security guarantee, the parties can amplify it to get a stronger security notion, in which the key is (somewhat) indistinguishable from random in the eyes of the eavesdropper. This can be done by either extracting randomness from the outputs (for example, using the Goldreich-Levin hardcore predicate [13]), or using the random oracle, by querying the common output and using its image as the key.³³3A problem can occur in the last approach if the image of the key is used in the protocol, as happens in Merkle’s Puzzles. In this case, the parties can, for example, use only the prefix of the images in the protocol, and use the suffix as the secret key.

Let ${\cal D}$ and ${\cal R}$ be two sets, and let ${\cal F}=\mathopen{}\mathclose{{\left\{f\mid f\colon{\cal D}\to{\cal R}}}\right\}$ be the all-function family over the domain ${\cal D}$ and the range ${\cal R}$ . When $\mathopen{}\mathclose{{\left|{\cal D}}}\right|=\Omega(\ell^{2})$ , and $\mathopen{}\mathclose{{\left|{\cal R}}}\right|>>\ell^{2}$ , the Merkle’s Puzzles protocol, mentioned in the introduction, is a $\ell$ -query, $(q,0.01,O(q/\ell^{2}))$ key-agreement protocol with respect to ${\cal F}$ , and for every $q\in{\mathbb{N}}$ .

3 The Key-Agreement Protocol

We now describe our key-agreement protocol. Let $\ell,M\in{\mathbb{N}}$ be two parameters, and let ${\cal F}_{\ell,M}=\mathopen{}\mathclose{{\left\{f\mid f\colon[\ell^{2}]\to[M]}% }\right\}$ be the family of all functions from $[\ell^{2}]$ to $[M]$ . For simplicity, we think of the domain of every $f\in{\cal F}_{\ell,M}$ as $[\ell]\times[\ell]$ . Namely, we think of every $f\in{\cal F}_{\ell,M}$ as $f\colon[\ell]\times[\ell]\to[M]$ .

Theorem 3.

The following holds for every $\ell,M\in{\mathbb{N}}$ . There exists an $\ell$ -query two-party protocol, which is a $(q,0,\frac{2(q+1)}{\ell^{2}}+\frac{2\ell^{2}}{M})$ key-agreement protocol with respect to to ${\cal F}_{\ell,M}$ , for every $q\in{\mathbb{N}}$ .

The protocol is as follows.

Protocol 4.

Parameters:

$\ell,M\in{\mathbb{N}}$ .

Common function:

$f\colon[\ell]\times[\ell]\to[M]$ .

Operation:

1.

Party $\mathsf{A}$ samples $x_{1},\dots,x_{\ell}\leftarrow[\ell]$ uniformly and independently at random, and queries $(1,x_{1}),\dots,(\ell,x_{\ell})$ . Let $a_{i}=f(i,x_{i})$ for every $i\in[\ell]$ .
2.

Party $\mathsf{B}$ samples an index $j\leftarrow[\ell]$ uniformly at random, and queries $(j,1),\dots,(j,\ell)$ . Let $b_{i}=f(j,i)$ for every $i\in[\ell]$ .
3.

$\mathsf{A}$ sends $a_{1},\dots,a_{\ell}$ in a random order.
4.

$\mathsf{B}$ checks if the number of different images in $\mathopen{}\mathclose{{\left\{a_{1},\dots,a_{\ell},b_{1},\dots,b_{\ell}}}\right\}$ is exactly $2\ell-1$ (that is, if there is exactly one collision). If not, $\mathsf{B}$ notifies $\mathsf{A}$ , and both parties output $0$ . Otherwise, $\mathsf{B}$ finds the unique $z\in\mathopen{}\mathclose{{\left\{a_{1},\dots,a_{\ell}}}\right\}\cap\mathopen{% }\mathclose{{\left\{b_{1},\dots,b_{\ell}}}\right\}$ , and sends $z$ to $\mathsf{A}$ .
5.

Party $\mathsf{A}$ outputs $(i,x_{i})$ for the unique $i\in[\ell]$ for which $f(i,x_{i})=z$ . $\mathsf{B}$ outputs $(j,k)$ for the unique $k\in[\ell]$ for which $f(j,k)=z$ .

.

We turn to analyze the agreement and security of Protocol 4. Towards this, fix the parameters $M$ and $\ell$ , and let ${\cal F}={\cal F}_{\ell,M}$ . Let $F\leftarrow{\cal F}$ be a random variable representing a random function from ${\cal F}$ , and let $O_{\mathsf{A}}$ and $O_{\mathsf{B}}$ be the outputs of $\mathsf{A}$ and $\mathsf{B}$ , respectively, in a random execution of Protocol 4 using the function $F$ . Finally, Let $T$ be the transcript of the protocol in this execution. Theorem 3 is a direct implication of the following two claims. The first states that Protocol 4 has perfect agreement.

$\vartriangleright$ Claim 5 (Agreement).

{\mathrm{Pr}}\mathopen{}\mathclose{{\left[O_{\mathsf{A}}=O_{\mathsf{B}}}}% \right]=1.

The second claim establishes the security of the protocol.

$\vartriangleright$ Claim 6 (Security).

For every $q$ -query algorithm $\mathsf{E}$ , it holds that

{\mathrm{Pr}}\mathopen{}\mathclose{{\left[\mathsf{E}^{F}(T)=O_{\mathsf{A}}}}% \right]\leq\frac{2(q+1)}{\ell^{2}}+\frac{2\ell^{2}}{M}.

We prove Claim 5 and Claim 6 below, but first let us conclude the proof of Theorem 3.

Proof of Theorem 3.

The proof follows by Claim 5 and Claim 6, together with the observation that the parties in Protocol 4 make $\ell$ queries each. $\hfill\blacktriangleleft$

3.1 Agreement – Proving Claim 5

We start by showing that Protocol 4 has perfect agreement.

Proof of Claim 5.

Claim 5 follows immediately by the query distribution of the parties. Specifically, observe that for every sampling of the $\ell$ points of $\mathsf{A}$ , $x_{1},\dots,x_{\ell}$ , and for every sampling of $j$ , $\mathsf{A}$ and $\mathsf{B}$ have a common query, $(j,x_{j})$ . Thus, the parties have at least one common image. If further there are no other collisions in the union of the two sets of images, then $O_{\mathsf{A}}=O_{\mathsf{B}}=(j,x_{j})$ .

On the other hand, when there are other collisions in the union of the sets, $O_{A}=O_{B}=0$ . Overall, we get that $O_{\mathsf{A}}=O_{\mathsf{B}}$ , with certainty, as wanted. $\hfill\vartriangleleft$

3.2 Security – Proving Claim 6

In this part we prove that Protocol 4 has roughly the same security as Merkle’s Puzzles. We do it by defining simplified security games, and showing a reduction between the security of Protocol 4 and these games.

Balls and Boxes games

To analyze the security of Protocol 4, in the following we define two “balls and boxes” games, to which we refer as the “unique-ball” game, and the “multi-ball” game. Intuitively, breaking the security of Merkle’s Puzzles is equivalent to winning the unique-ball game, and, on the other hand, we will show that breaking the security of Protocol 4 is equivalent to winning the multi-ball game. In the following we define these two games, and show that every strategy for the multi-ball game is an (almost) as good strategy for the unique-ball game. This will imply that Protocol 4 has security similar to the security of Merkle’s Puzzles.

We start with defining the unique-ball game.

Definition 7 (The unique-ball game).

Let $\ell,q\in{\mathbb{N}}$ be two parameters. In the $(\ell,q)$ -unique-ball game, there are $\ell^{2}$ boxes ordered in $\ell$ rows and $\ell$ columns. All the boxes are empty, except for one box, chosen uniformly at random, that contains a red ball in it.

The player is allowed to (adaptively) open up to $q$ boxes. The player wins the game if it finds the ball.

It is not hard to see that for every strategy of the player, the probability of finding the ball is at most $q/\ell^{2}$ . We now define the multi-ball game.

Definition 8 (The multi-ball game).

Let $\ell,q\in{\mathbb{N}}$ be two parameters. In the $(\ell,q)$ -multi-ball game, there are $\ell^{2}$ boxes ordered in $\ell$ rows and $\ell$ columns. In each row, there is a single box chosen uniformly and independently at random, that contains a ball in it. All the other boxes are empty. The ball in one row, chosen uniformly at random, is red, and the other balls are blue.

The player is allowed to (adaptively) open up to $q$ boxes. The player wins the game if it finds the red ball.

That is, as in the unique-ball game, the goal of the player is to find the box that contains the red ball, out of $\ell^{2}$ possible boxes. However, this time when the player finds a blue ball, it knows that the red ball is not in this row, and thus can stop opening boxes in this row. Intuitively, this corresponds to the images $\mathsf{A}$ sends in Protocol 4, which can help the adversary to rule out some possible indices. The connection between the security of Protocol 4 to the multi-ball game is stated in the following claim.

$\vartriangleright$ Claim 9.

Assume there exists a $q$ -query algorithm $\mathsf{E}$ such that ${\mathrm{Pr}}\mathopen{}\mathclose{{\left[\mathsf{E}^{F}(T)=O_{\mathsf{A}}}}% \right]=p$ . Then there exists a player $\mathsf{P}$ that wins the $(\ell,q+1)$ -multi-ball game with probability at least $p-\frac{2\ell^{2}}{M}$ .

We prove Claim 9 in Section 3.3, but first let us use it to prove Claim 6. To do so, we need to prove an upper bound on the winning probability of every strategy for the multi-ball game. This is done by showing that every strategy to the multi-ball game can be used in the unique-ball game with roughly the same success probability. Formally,

$\vartriangleright$ Claim 10.

Assume there exists a strategy for the $(\ell,q)$ -multi-ball game that wins with probability $p$ . Then there exists a strategy for the $(\ell,q)$ -unique ball game with winning probability $p/2$ .

Proof of Claim 10.

Let $\mathsf{P}$ be a player for the $(\ell,q)$ -multi-ball game, that wins with probability $p$ . We show how to use $\mathsf{P}$ to construct $\mathsf{P}^{\prime}$ that wins in the $(\ell,q)$ -unique-ball game with probability $p/2$ .

Given $\ell^{2}$ boxes, $\mathsf{P}^{\prime}$ samples $x_{1},\dots,x_{\ell}\leftarrow[\ell]$ uniformly and independently at random. Informally, $\mathsf{P}^{\prime}$ will “plant” a blue ball in the box at location $(i,x_{i})$ for every $i\in[\ell]$ , and then run $\mathsf{P}$ . More formally, $\mathsf{P}^{\prime}$ simulates the game for $\mathsf{P}$ . Every time $\mathsf{P}$ chooses to open a box $(i,j)$ , $\mathsf{P}^{\prime}$ opens the same box. If this box contains the red ball, $\mathsf{P}^{\prime}$ wins. If this box is empty and $j=x_{i}$ , $\mathsf{P}^{\prime}$ reports to $\mathsf{P}$ that the box contains a blue ball. Otherwise, $\mathsf{P}^{\prime}$ reports to $\mathsf{P}$ that the box is empty.

Observe that $\mathsf{P}^{\prime}$ wins if and only if $\mathsf{P}$ finds the red ball in the simulated game.⁴⁴4Notice that $\mathsf{P}$ may find $\ell$ blue balls in the simulated game, and this cannot happen in the real multi-ball game. However, this event is not counted as a win. To see that $\mathsf{P}$ wins the simulated game with probability at least $p/2$ , first observe that in the simulated game, there is one row $i^{*}$ that contains two balls (one red ball and one blue ball, possibly at the same box), and all the other rows contain exactly one (blue) ball. Notice that if both of the balls in row $i^{*}$ were red, the winning probability of $\mathsf{P}$ in the simulated game was at least $p$ (as we only added a red ball to the grid). That is, $\mathsf{P}$ finds (at least) one ball on row $i^{*}$ with probability at least $p$ . By symmetry, the probability that the first ball in row $i^{*}$ found by $\mathsf{P}$ is indeed the true red ball is $1/2$ . Thus, the winning probability of $\mathsf{P}$ is at least $p/2$ , as stated. $\hfill\vartriangleleft$

As a direct corollary from Claim 5 and the fact that there is no strategy for the unique-ball game with a winning probability better than $q/\ell^{2}$ , we get that every strategy for the $(\ell,q)$ -multi-ball game wins with probability at most $2q/\ell^{2}$ .

Corollary 11.

The winning probability of any strategy for the $(\ell,q)$ -multi-ball game is at most $2q/\ell^{2}$ .

We can now conclude Claim 6.

Proof of Claim 6.

Immediately follows by Corollaries 11 and 9. $\hfill\vartriangleleft$

3.3 Proving Claim 9

Lastly, we show that an adversary $\mathsf{E}$ that makes $q$ queries to $F$ and breaks Protocol 4 with probability $p$ , can be used to win the $(\ell,q+1)$ -multi-ball game with roughly the same probability.

To prove Claim 9, consider the following player $\mathsf{P}$ that plays the multi-ball game by simulating $\mathsf{E}$ on a random function $F$ and transcript $T$ . In the following, assume without loss of generality that $\mathsf{E}$ never asks the same query twice. Moreover, at the cost of one additional query, assume that $\mathsf{E}$ always queries $F$ on its output.

Algorithm 12 ( $\mathsf{P}$ ).

Parameters:

$\ell,M\in{\mathbb{N}}$ .

Operation:

1.

$\mathsf{P}$ samples $a_{1},\dots,a_{\ell}\leftarrow[M]$ uniformly and independently at random, and $j\leftarrow[\ell]$ .
2.
$\mathsf{P}$ simulates $\mathsf{E}$ on the transcript ${\sf trans}=((a_{1},\dots,a_{\ell}),z=a_{j})$ . Every time $\mathsf{E}$ makes a query $(i,j)$ , $\mathsf{P}$ opens the box at location $(i,j)$ . $\mathsf{P}$ answers to $\mathsf{E}$ ’s query as follows:
- $\blacksquare$
  
  If the box contains a red ball, $\mathsf{P}$ wins and halts.
- $\blacksquare$
  
  If the box is empty, $\mathsf{P}$ answers with a random element from $[M]$ .
- $\blacksquare$
  
  If the box contains a blue ball, $\mathsf{P}$ answers with a random element from $\mathopen{}\mathclose{{\left\{a_{1},\dots,a_{\ell}}}\right\}\setminus\mathopen% {}\mathclose{{\left\{a_{j}}}\right\}$ that was not in use before.

.

We are now ready to prove Claim 9.

Proof of Claim 9.

Let $\mathsf{E}$ be a $(q+1)$ -query algorithm that, given the transcript of Protocol 4, queries the function $F$ on the output $O_{\mathsf{A}}$ of $\mathsf{A}$ with probability at least $p$ . Let $\mathsf{P}$ be Algorithm 12.

We start with considering a modified version of Protocol 4 (which cannot be implemented as a protocol), in which $\mathsf{B}$ does not notify $\mathsf{A}$ in step 4 in case $\mathsf{B}$ sees a collision in the function $f$ . Instead, in this case we assume that $\mathsf{B}$ sends the correct image $z=f(j,x_{j})$ , and that $\mathsf{A}$ outputs the correct intersection $(j,x_{j})$ .

As the above modified version and Protocol 4 differ only in the case that there is a collision in $f$ , it is not hard to see that in this modified version, $\mathsf{E}$ guesses the output of party $\mathsf{A}$ with probability at least

	$\displaystyle p-{\mathrm{Pr}}\mathopen{}\mathclose{{\left[F(q)=F(q^{\prime})% \textit{ for two distinct queries $q\neq q^{\prime}$ of $\mathsf{A}$ and $% \mathsf{B}$}}}\right]$
	$\displaystyle\geq p-{2\ell\choose 2}\cdot\frac{1}{M}$
	$\displaystyle\geq p-\frac{2\ell^{2}}{M},$

where the first inequality holds by the union bound, since every two queries have probability $1/M$ to collide, and there are at most $2\ell$ queries made by the parties.

To see that the success probability of Algorithm 12 is $p-\frac{2\ell^{2}}{M}$ , note that it readily follows by inspection that the distribution seen by $\mathsf{E}$ in a random execution of Algorithm 12 on a random multi-ball game, is exactly the same distribution seen by $\mathsf{E}$ in a random execution of the above modified protocol. Moreover, Algorithm 12 finds the red ball in the multi-ball game if and only if $\mathsf{E}$ queries the secret key in the modified protocol. The claim follows. $\hfill\vartriangleleft$

References

[1] Miklós Ajtai and Cynthia Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In stoc29, pages 284–293, 1997. See also ECCC TR96-065. doi:10.1145/258533.258604.
[2] Michael Alekhnovich. More on average case vs approximation complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 298–307. IEEE, 2003. doi:10.1109/SFCS.2003.1238204.
[3] Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 171–180, 2010. doi:10.1145/1806689.1806715.
[4] Boaz Barak and Mohammad Mahmoody. Merkle puzzles are optimal – An $o(n^{2})$ -query attack on any key exchange from a random oracle. In Annual International Cryptology Conference, pages 374–390. Springer, 2009.
[5] Nir Bitansky and Vinod Vaikuntanathan. A note on perfect correctness by derandomization. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 592–606. Springer, 2017. doi:10.1007/978-3-319-56614-6_20.
[6] Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, and Alon Rosen. Public-key encryption from homogeneous clwe. In Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part II, pages 565–592. Springer, 2022. doi:10.1007/978-3-031-22365-5_20.
[7] Dan Boneh, Richard A DeMillo, and Richard J Lipton. On the importance of eliminating errors in cryptographic computations. Journal of cryptology, 14:101–119, 2001. doi:10.1007/S001450010016.
[8] Zvika Brakerski, Jonathan Katz, Gil Segev, and Arkady Yerukhimovich. Limits on the power of zero-knowledge proofs in cryptographic constructions. In Theory of Cryptography: 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011. Proceedings 8, pages 559–578. Springer, 2011. doi:10.1007/978-3-642-19571-6_34.
[9] Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, pages 644–654, 1976. doi:10.1109/TIT.1976.1055638.
[10] Cynthia Dwork, Moni Naor, and Omer Reingold. Immunizing encryption schemes from decryption errors. In Advances in Cryptology – EUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004. Proceedings 23, pages 342–360. Springer, 2004. doi:10.1007/978-3-540-24676-3_21.
[11] Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In Annual International Cryptology Conference (CRYPTO), pages 10–18, 1984.
[12] Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Eliminating decryption errors in the ajtai-dwork cryptosystem. In Advances in Cryptology – CRYPTO’97: 17th Annual International Cryptology Conference Santa Barbara, California, USA August 17–21, 1997 Proceedings 17, pages 105–111. Springer, 1997. doi:10.1007/BFB0052230.
[13] Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of computing (STOC), pages 25–32, 1989. doi:10.1145/73007.73010.
[14] Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, and Amir Yehudayoff. On the communication complexity of key-agreement protocols. 10th Innovations in Theoretical Computer Science, 2019. doi:10.4230/LIPIcs.ITCS.2019.40.
[15] Iftach Haitner, Eran Omri, and Hila Zarosim. Limits on the usefulness of random oracles. Journal of Cryptology, 29(2):283–335, 2016. doi:10.1007/S00145-014-9194-9.
[16] Thomas Holenstein and Renato Renner. One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption. In Annual International Cryptology Conference, pages 478–493. Springer, 2005. doi:10.1007/11535218_29.
[17] Mi-Ying Miryam Huang, Xinyu Mao, Guangxu Yang, and Jiapeng Zhang. Communication lower bounds of key-agreement protocols via density increment arguments. Cryptology ePrint Archive, 2023. URL: https://eprint.iacr.org/2023/1349.
[18] Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In Proceedings of the twenty-first annual ACM symposium on Theory of computing (STOC), pages 44–61. ACM Press, 1989. doi:10.1145/73007.73012.
[19] Jeff Kahn, Michael Saks, and Cliff Smyth. A dual version of Reimer’s inequality and a proof of Rudich’s conjecture. In 15th Annual IEEE Conference on Computational Complexity, pages 98–103, 2000. doi:10.1109/CCC.2000.856739.
[20] Huijia Lin and Stefano Tessaro. Amplification of chosen-ciphertext security. In Advances in Cryptology–EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings 32, pages 503–519. Springer, 2013. doi:10.1007/978-3-642-38348-9_30.
[21] Robert J McEliece. A public-key cryptosystem based on algebraic. Coding Thv, 4244:114–116, 1978.
[22] Ralph C Merkle. Secure communications over insecure channels. Communications of the ACM, 21(4):294–299, 1978. doi:10.1145/359460.359473.
[23] John Proos. Imperfect decryption and an attack on the ntru encryption scheme. Cryptology ePrint Archive, 2003. URL: https://eprint.iacr.org/2003/002.
[24] Michael O Rabin. Digitalized signatures and public-key functions as intractable as factorization. Technical report, Massachusetts Inst of Tech Cambridge Lab for Computer Science, 1979.
[25] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009. doi:10.1145/1568318.1568324.
[26] Ronald L Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978. doi:10.1145/359340.359342.
[27] Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303–332, 1999. doi:10.1137/S0036144598347011.

[bib.bib1] [1] Miklós Ajtai and Cynthia Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In stoc29, pages 284–293, 1997. See also ECCC TR96-065. doi:10.1145/258533.258604.

[bib.bib2] [2] Michael Alekhnovich. More on average case vs approximation complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 298–307. IEEE, 2003. doi:10.1109/SFCS.2003.1238204.

[bib.bib3] [3] Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 171–180, 2010. doi:10.1145/1806689.1806715.

[bib.bib4] [4] Boaz Barak and Mohammad Mahmoody. Merkle puzzles are optimal – An $o(n^{2})$ -query attack on any key exchange from a random oracle. In Annual International Cryptology Conference, pages 374–390. Springer, 2009.

[bib.bib5] [5] Nir Bitansky and Vinod Vaikuntanathan. A note on perfect correctness by derandomization. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 592–606. Springer, 2017. doi:10.1007/978-3-319-56614-6_20.

[bib.bib6] [6] Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, and Alon Rosen. Public-key encryption from homogeneous clwe. In Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part II, pages 565–592. Springer, 2022. doi:10.1007/978-3-031-22365-5_20.

[bib.bib7] [7] Dan Boneh, Richard A DeMillo, and Richard J Lipton. On the importance of eliminating errors in cryptographic computations. Journal of cryptology, 14:101–119, 2001. doi:10.1007/S001450010016.

[bib.bib8] [8] Zvika Brakerski, Jonathan Katz, Gil Segev, and Arkady Yerukhimovich. Limits on the power of zero-knowledge proofs in cryptographic constructions. In Theory of Cryptography: 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011. Proceedings 8, pages 559–578. Springer, 2011. doi:10.1007/978-3-642-19571-6_34.

[bib.bib9] [9] Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, pages 644–654, 1976. doi:10.1109/TIT.1976.1055638.

[bib.bib10] [10] Cynthia Dwork, Moni Naor, and Omer Reingold. Immunizing encryption schemes from decryption errors. In Advances in Cryptology – EUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004. Proceedings 23, pages 342–360. Springer, 2004. doi:10.1007/978-3-540-24676-3_21.

[bib.bib11] [11] Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In Annual International Cryptology Conference (CRYPTO), pages 10–18, 1984.

[bib.bib12] [12] Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Eliminating decryption errors in the ajtai-dwork cryptosystem. In Advances in Cryptology – CRYPTO’97: 17th Annual International Cryptology Conference Santa Barbara, California, USA August 17–21, 1997 Proceedings 17, pages 105–111. Springer, 1997. doi:10.1007/BFB0052230.

[bib.bib13] [13] Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of computing (STOC), pages 25–32, 1989. doi:10.1145/73007.73010.

[bib.bib14] [14] Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, and Amir Yehudayoff. On the communication complexity of key-agreement protocols. 10th Innovations in Theoretical Computer Science, 2019. doi:10.4230/LIPIcs.ITCS.2019.40.

[bib.bib15] [15] Iftach Haitner, Eran Omri, and Hila Zarosim. Limits on the usefulness of random oracles. Journal of Cryptology, 29(2):283–335, 2016. doi:10.1007/S00145-014-9194-9.

[bib.bib16] [16] Thomas Holenstein and Renato Renner. One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption. In Annual International Cryptology Conference, pages 478–493. Springer, 2005. doi:10.1007/11535218_29.

[bib.bib17] [17] Mi-Ying Miryam Huang, Xinyu Mao, Guangxu Yang, and Jiapeng Zhang. Communication lower bounds of key-agreement protocols via density increment arguments. Cryptology ePrint Archive, 2023. URL: https://eprint.iacr.org/2023/1349.

[bib.bib18] [18] Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In Proceedings of the twenty-first annual ACM symposium on Theory of computing (STOC), pages 44–61. ACM Press, 1989. doi:10.1145/73007.73012.

[bib.bib19] [19] Jeff Kahn, Michael Saks, and Cliff Smyth. A dual version of Reimer’s inequality and a proof of Rudich’s conjecture. In 15th Annual IEEE Conference on Computational Complexity, pages 98–103, 2000. doi:10.1109/CCC.2000.856739.

[bib.bib20] [20] Huijia Lin and Stefano Tessaro. Amplification of chosen-ciphertext security. In Advances in Cryptology–EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings 32, pages 503–519. Springer, 2013. doi:10.1007/978-3-642-38348-9_30.

[bib.bib21] [21] Robert J McEliece. A public-key cryptosystem based on algebraic. Coding Thv, 4244:114–116, 1978.

[bib.bib22] [22] Ralph C Merkle. Secure communications over insecure channels. Communications of the ACM, 21(4):294–299, 1978. doi:10.1145/359460.359473.

[bib.bib23] [23] John Proos. Imperfect decryption and an attack on the ntru encryption scheme. Cryptology ePrint Archive, 2003. URL: https://eprint.iacr.org/2003/002.

[bib.bib24] [24] Michael O Rabin. Digitalized signatures and public-key functions as intractable as factorization. Technical report, Massachusetts Inst of Tech Cambridge Lab for Computer Science, 1979.

[bib.bib25] [25] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009. doi:10.1145/1568318.1568324.

[bib.bib26] [26] Ronald L Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978. doi:10.1145/359340.359342.

[bib.bib27] [27] Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303–332, 1999. doi:10.1137/S0036144598347011.

Key-Agreement with Perfect Completeness from Random Oracles

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

The Random Oracle Model

Merkle’s Puzzles

1.1 Our Results

Theorem 1 (Main theorem, informal).

The protocol

Security

Comparison with Merkle’s Puzzles

Perspective and Additional Related Work

Perfect primitives in the ROM

Public-key encryption with perfect completeness

2 Preliminaries

2.1 Notations

2.2 Interactive Protocols and Oracle-Aided Protocols

2.3 Key-Agreement Protocols

Definition 2 (Key-agreement protocol).

3 The Key-Agreement Protocol

Theorem 3.

Protocol 4.

⊳ Claim 5 (Agreement).

⊳ Claim 6 (Security).

Proof of Theorem 3.

3.1 Agreement – Proving Claim 5

Proof of Claim 5.

3.2 Security – Proving Claim 6

Balls and Boxes games

Definition 7 (The unique-ball game).

Definition 8 (The multi-ball game).

⊳ Claim 9.

⊳ Claim 10.

Proof of Claim 10.

Corollary 11.

Proof of Claim 6.

3.3 Proving Claim 9

Algorithm 12 (𝖯).

Proof of Claim 9.

References

$\vartriangleright$ Claim 5 (Agreement).

$\vartriangleright$ Claim 6 (Security).

$\vartriangleright$ Claim 9.

$\vartriangleright$ Claim 10.

Algorithm 12 ( $\mathsf{P}$ ).