# Merkle Puzzles in a Quantum World

 Merkle Puzzles in a Quantum World Authors Gilles Brassard[@: 1],Peter Høyer[@: 2], Kassem Kalach[@: 3], Marc Kaplan[@: 4], Sophie Laplante[@: 5] and Louis Salvail[@: 6] Published 2011. Web site Department of Computer Science Download original
Abstract. In 1974, Ralph Merkle proposed the first unclassified scheme for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of computational effort proportional to some parameter ${\displaystyle N}$, an eavesdropper cannot break into their communication without spending a time proportional to ${\displaystyle N^{2}}$ which is quadratically more than the legitimate effort. We showed in an earlier paper that Merkle’s schemes are completely insecure against a quantum adversary, but that their security can be partially restored if the legitimate parties are also allowed to use quantum computation: the eavesdropper needed to spend a time proportional to ${\displaystyle N^{3/2}}$ to break our earlier quantum scheme. Furthermore, all previous classical schemes could be broken completely by the onslaught of a quantum eavesdropper and we conjectured that this is unavoidable.
We give two novel key agreement schemes in the spirit of Merkle’s. The first one can be broken by a quantum adversary that makes an effort proportional to ${\displaystyle N^{5/3}}$ to implement a quantum random walk in a Johnson graph reminiscent of Andris Ambainis’ quantum algorithm for the element distinctness problem. This attack is optimal up to logarithmic factors. Our second scheme is purely classical, yet it cannot be broken by a quantum eavesdropper who is only willing to expend effort proportional to that of the legitimate parties.
Keywords: Merkle Puzzles, Public Key Distribution, Quantum Cryptography.

## Introduction

While Ralph Merkle was delivering the 2005 International Association for Cryptologic Research (IACR) Distinguished Lecture at the Crypto annual conference in Santa Barbara, describing his original unpublished 1974 scheme[1] for public key distribution (much simpler and more elegant than his subsequently published, yet better known, Merkle Puzzles[2]), one of us (Brassard) immediately realized that this scheme was totally insecure against an eavesdropper equipped with a quantum computer. The obvious question was: can Merkle’s idea be repaired and made secure again in our quantum world? The defining characteristics of Merkle’s protocol are that (1) the legitimate parties communicate strictly through an authenticated classical channel on which eavesdropping is unrestricted and (2) a protocol is deemed to be secure if the cryptanalytic effort required of the eavesdropper to learn the key exchanged by the legitimate parties grows super-linearly with the legitimate work.

We partially repaired Merkle’s scheme in Ref.[3] with a scheme in which the eavesdropper needed an amount of work in ${\displaystyle \Omega (N^{3/2})}$ to obtain the key established by quantum legitimate parties whose amount of work is in ${\displaystyle O(N)}$. This was not quite as good as the work in ${\displaystyle \Omega (N^{2})}$ required by a classical eavesdropper against Merkle’s original scheme, but significantly better than the work in ${\displaystyle O(N)}$ sufficient for a quantum eavesdropper against the same scheme. Two main questions were left open in [3]:

1. Can the quadratic security possible in a classical world be restored in our quantum world?
2. Is any security possible at all if the legitimate parties are purely classical, yet the eavesdropper is endowed with a quantum computer?

We give two novel key distribution protocols to address these issues. In the first protocol, the legitimate parties use quantum computers and classical authenticated communication to establish a shared key after ${\displaystyle O(N)}$ expected queries to two black-box random functions (which can be modelled with a single random oracle). We then give a nontrivial quantum cryptanalytic attack that uses a quantum random walk in a Johnson graph, much like Andris Ambainis’ algorithm to solve the element distinctness problem[4], which allows a quantum eavesdropper to learn the key after ${\displaystyle \Theta (N^{5/3})}$ queries to the functions. Finally, we prove that our attack is optimal up to logarithmic factors. Therefore, we have not quite restored the quadratic security possible in a classical world, but we have made significant progress towards it.

Second, we give a purely classical protocol, in which the legitimate parties use classical communication and classical computation to establish a key after ${\displaystyle O(N)}$ calls to similar black-box random functions. We then attack this protocol with a quantum cryptanalytic algorithm that uses${\displaystyle \Theta (N^{13/12})}$ queries to the functions. As unlikely as it may sound, this attack is optimal (up to logarithmic factors) and therefore it is not possible to break this purely classical protocol with a quantum attack that uses an amount of resource linear in the legitimate effort.

Before describing our new protocols (Sects. 3 and 4), quantum attacks against them (Sects. 3.1 and 4.1), proofs of optimality for those attacks (Sects. 3.2 and 4.2), and conjectures about the existence of even better schemes (Sect. 5), we begin with a review (lifted from Ref. [3]) of Merkle’s original idea, its meltdown against a quantum eavesdropper, and our earlier partial quantum solution (Sect. 2). Some of the technical tools required by our quantum attacks are reviewed in the Appendix and new lower bound techniques are introduced.

## Merkle’s Original Scheme and How to Break and Partially Repair It

The first unclassified document ever written that pioneered public key distribution and public key cryptography was a project proposal written in 1974 by Merkle when he was a student in Lance Hoffman’s CS244 course on Computer Security at the University of California, Berkeley [1]. Hoffman rejected the proposal and Merkle dropped the course but “kept working on the idea” and eventually published it as one of the most seminal cryptographic papers in the second half of the twentieth century [2]. Merkle’s scheme in his published paper was somewhat different from his original 1974 idea, but both share the property that they “force any enemy to expend an amount of work which increases as the square of the work required of the two [legitimate] communicants” [2]. It took 35 years before Boaz Barak and Mohammad Mahmoody-Ghidary proved that this quadratic discrepancy between the legitimate and eavesdropping efforts are the best possible in a classical world[5].

In his IACR Distinguished Lecture 4, which he delivered at the Crypto’05 Conference in Santa Barbara, Merkle described from memory his first solution to the problem of secure communications over insecure channels. As a wondrous coincidence, he unsuspectingly opened up a box of old folders a mere three weeks after his Lecture and happily recovered his long-lost CS244 Project Proposal, together with comments handwritten by Hoffman [1]! To quote his original typewritten words:

Method 1: Guessing. Both sites guess at keywords. These guesses are one-way encrypted, and transmitted to the other site. If both sites should chance to guess at the same keyword, this fact will be discovered when the encrypted versions are compared, and this keyword will then be used to establish a communications link.

Discussion: No, I am not joking.

In more modern terms, let ${\displaystyle f}$ be a one-way permutation. In order to “one-way encrypt” ${\displaystyle x}$, as Merkle said in 1974, we assume that one can compute ${\displaystyle f(x)}$ in unit time for any given input ${\displaystyle x}$ but that the only way to retrieve x given ${\displaystyle f(x)}$ is to try preimages and compute ${\displaystyle f}$ on them until one is found that maps to ${\displaystyle f(x)}$. This is known as the black-box (or oracle) model. Hereinafter, in accordance with this model, efficiency is defined solely in terms of the number of calls to such black-box functions (there could be more than one). In the quantum case, these calls can be made in superposition of inputs. We also assume throughout this paper (as did Merkle) that an authenticated channel is available between the legitimate communicants, although this channel offers no protection against eavesdropping.

The “keywords” guessed at by “both sites” are random points in the domain of ${\displaystyle f}$. They are “one-way encrypted” by applying ${\displaystyle f(x)}$ to them. If there are ${\displaystyle N^{2}}$ points in the domain of ${\displaystyle f}$, it suffices to guess ${\displaystyle O(N)}$ keywords at each site before a variation on the birthday paradox makes it overwhelmingly likely that “both sites should chance to guess at the same keyword”, which becomes their shared key. An eavesdropper who listens to the entire conversation has no other way to obtain this key than to invert ${\displaystyle f}$ on the revealed common encrypted keyword. In accordance with the black-box model, this can only be done by trying on the average half the points in the domain of ${\displaystyle f}$ before one is found that is mapped by ${\displaystyle f}$ to the target value. This will require an expected number of calls to ${\displaystyle f}$ in ${\displaystyle \Omega (N^{2})}$, which is quadratic in the legitimate effort.

Shortly thereafter, Whitfield Diffie and Martin Hellman discovered a celebrated method for public-key distribution that makes the cryptanalytic effort apparently exponentially harder than the legitimate effort[6]. However, no proof is known that the Diffie-Hellman scheme is secure at all since it relies on the conjectured difficulty of extracting discrete logarithms, an assumption doomed to fail whenever quantum computers become available. In contrast, Merkle’s approach offers provable quadratic security against any possible classical attack, under the sole assumption that ${\displaystyle f}$ cannot be inverted by any other means than exhaustive search.

Next, we explain why Merkle’s original proposal becomes completely insecure if the eavesdropper is capable of quantum computation (Merkle’s published “puzzles”[2] are equally insecure). We then sketch a protocol from Ref.[3] that is not completely broken. This is be achieved by granting similar quantum computation capabilities to one of the legitimate communicating parties.

### Quantum Attack and Partial Remedy

Let us now assume that function ${\displaystyle f}$ can be computed quantum mechanically on a superposition of inputs. In this case, Merkle’s original scheme is completely compromised by way of Grover’s algorithm [7].. Indeed, this algorithm needs only${\displaystyle O({\sqrt {N^{2}}})=O(N)}$ calls on ${\displaystyle f}$ in order to invert it on any given point of its image, making the cryptanalytic task as easy (up to constant factors) as the legitimate key setup process. 5

To remedy the situation, we allow the communicating parties to use quantum computers as well (actually, one of the parties will remain classical), and we increase the domain of ${\displaystyle f}$ from ${\displaystyle N^{2}}$ to ${\displaystyle N^{3}}$ points. Instead of having both sites transmit one-way encrypted guesses to the other site, one site called Alice chooses ${\displaystyle N}$ distinct random values ${\displaystyle x_{1},x_{2},\ldots ,x_{N}}$ and transmits them, one-way encrypted by the application of ${\displaystyle f}$, to the other site called Bob. Let ${\displaystyle Y=\{f(x_{i})\quad |\quad 1\leq i\leq N\}}$ denote the set of encrypted keywords received by Bob, which becomes known to the eavesdropper. Now, Bob defines Boolean function ${\displaystyle g}$ on the same domain as ${\displaystyle f}$ by

${\displaystyle g(x)={\begin{cases}1,&{\mbox{if }}f(x)\in Y\\0,&{\mbox{otherwise}}\end{cases}}}$

Out of ${\displaystyle N^{3}}$ points in the domain of ${\displaystyle f}$, there are exactly ${\displaystyle t=N}$ solutions to the problem of finding an ${\displaystyle x}$ so that ${\displaystyle g(x)=1}$. It suffices for Bob to apply the BBHT generalization[8] of Grover’s algorithm[7], which finds such an ${\displaystyle x}$ after ${\displaystyle O({\sqrt {N^{3}/t}})=O({\sqrt {N^{2}}})=O(N)}$ calls on ${\displaystyle g}$ (and therefore on ${\displaystyle f}$). Bob sends back ${\displaystyle f(x)}$ to Alice, who knows the value of ${\displaystyle x}$ because she was careful to keep her randomly chosen points. Therefore, it suffices of ${\displaystyle O(N)}$ calls on ${\displaystyle f}$ by Alice and Bob for them to agree on key ${\displaystyle x}$.

The eavesdropper, on the other hand, is faced with the need to invert ${\displaystyle f}$ on a specific point of its image. Even with a quantum computer, this requires a number of calls on ${\displaystyle f}$ proportional to the square root of the number of points in its domain[9], which is ${\displaystyle \Omega ({\sqrt {N^{3}}})=\Omega (N^{3/2})}$. This is more effort than what is required of the legitimate parties, yet less than quadratically so, as would have been possible in a classical world. Even though we have avoided the meltdownof Merkle’s original approach, the introduction of quantum computers available to all sides seems to be to the advantage of the codebreakers. Can we remedy this situation? Furthermore, is any security possible at all against a quantum computer if both legitimate parties are restricted to being purely classical? We address these two questions in the rest of this paper.

## Improved Key Distribution Scheme

For any positive integer ${\displaystyle N}$, let ${\displaystyle [N]}$ denote the set of integers from 1 to ${\displaystyle N}$. We describe our novel key distribution protocol assuming the existence of two black-box random functions ${\displaystyle f:[N^{3}]\to [N^{k}]}$ and ${\displaystyle g:[N^{3}]\times [N^{3}]\to [N^{k'}]}$ that can be accessed in quantum superposition of inputs. Constants ${\displaystyle k}$ and ${\displaystyle k'}$ are chosen large enough so that there is no collision in the images of ${\displaystyle f}$ and ${\displaystyle g}$, except with negligible probability. (For simplicity, we shall systematically disregard the possibility that such collisions might exist.) Notice that a single binary random oracle (which “implements” a random function from the integers to {0, 1}) could be used to define both functions ${\displaystyle f}$ and ${\displaystyle g}$ provided we disregard logarithmic factors in our analyses since ${\displaystyle O(\log N)}$ calls to the random oracle would suffice to compute ${\displaystyle f}$ or ${\displaystyle g}$ on any single input. For this reason, it is understood hereinafter that all our results are implicitly stated “up to logarithmic factors”. As mentioned in the previous section, the only resource that we consider in our analyses of efficiency and lower bounds is the number of calls made to these functions or, equivalently, to the underlying binary random oracle.

Protocol 1.
1. Alice picks at random N distinct values ${\displaystyle \{x_{i}\}_{i=1}^{N}}$ with ${\displaystyle x_{i}\in [N^{3}]}$ and transmits the encrypted values ${\displaystyle y_{i}=f(x_{i})}$ to Bob. Let ${\displaystyle X}$ and ${\displaystyle Y}$ denote${\displaystyle \{x_{i}\quad |\quad 1\leq i\leq N\}}$ and ${\displaystyle \{y_{i}\quad |\quad 1\leq i\leq N\}}$, respectively. Note that Alice knows both ${\displaystyle X}$ and ${\displaystyle Y}$, whereas Bob and the eavesdropper have immediate knowledge (i.e. without querying the black-box for function ${\displaystyle f}$) of ${\displaystyle Y}$ only.
2. Bob finds the pre-images ${\displaystyle x}$ and ${\displaystyle x'}$ of two distinct random elements in ${\displaystyle Y}$. To find each one of them, he uses BBHT[8] to search for an ${\displaystyle x}$ such that ${\displaystyle \phi (x)=1}$, where ${\displaystyle \phi :[N^{3}]\to \{0,1\}}$ is defined as follows:
${\displaystyle \phi (x)={\begin{cases}1,&{\mbox{if }}f(x)\in Y\\0,&{\mbox{otherwise}}\end{cases}}}$

There are exactly ${\displaystyle N}$ values of ${\displaystyle x}$ such that ${\displaystyle \phi (x)=1}$, out of ${\displaystyle N^{3}}$ points in the domain of ${\displaystyle \phi }$. Therefore, Bob can find one such random ${\displaystyle x}$ with ${\displaystyle O({\sqrt {N^{3}/N}})=O(N)}$ calls to function ${\displaystyle f}$. He needs to repeat this process twice in order to get both ${\displaystyle x}$ and ${\displaystyle x'}$. (A small variation in function φ can be used the second time to make sure that ${\displaystyle x'\neq x}$).

1. Bob sends back ${\displaystyle w=g(x,x')}$ to Alice.
2. Because Alice had kept her randomly chosen set ${\displaystyle X}$, there are only ${\displaystyle N^{2}}$ candidate pairs${\displaystyle (x_{i},x_{j})\in X\times X}$ such that ${\displaystyle g(x_{i},x_{j})}$ could equal ${\displaystyle w}$. Using Grover’s algorithm, she can find the one pair ${\displaystyle (x,x')}$ that Bob has in mind with ${\displaystyle O({\sqrt {N^{2}}})=O(N)}$ calls to function ${\displaystyle g}$.
3. The key shared by Alice and Bob is the pair ${\displaystyle (x,x')}$.

All counted, Alice makes ${\displaystyle N}$ calls to ${\displaystyle f}$ in step 1 and ${\displaystyle O(N)}$ calls to g in step 4, whereas Bob makes ${\displaystyle O(N)}$ calls to ${\displaystyle f}$ in step 2 and a single call to ${\displaystyle g}$ in step 3. If the protocol is constructed over a binary random oracle, it will have to be called ${\displaystyle O(N\log N)}$ times since it takes ${\displaystyle O(\log N)}$ binary queries to compute either function on any given input.

### Quantum Attack

All the obvious (and not so obvious) cryptanalytic attacks against this scheme, such as direct use of Grover’s algorithm (or BBHT), or even more sophisticated attacks based on amplitude amplification [7], require the eavesdropper to call Ω(N2) times functions f and/or g. Unfortunately, a more powerful attack based on the more recent paradigm of quantum walks in Markov chains [17] allows the eavesdropper to recover Alice and Bob’s key (x, x0 ) with an expected O(N5/3) calls to f and O(N) calls to g. This attack was inspired by Ambainis’ quantum algorithm for element distinctness [2], which can find the unique pair (i, j) such that c(i) = c(j) with O(N2/3) expected queries to single-collision function c whose domain contains N elements (whereas all previous approaches based on Grover’s algorithm and amplitude amplification [12, 9] had required Ω(N3/4) queries).

Theorem 1.
There exists an eavesdropping strategy that outputs the pair (x, x0) in Protocol 1 with O(N5/3) expected quantum queries to functions f and g.
Proof
{{{3}}}

Note that the use of Grover’s algorithm in the checking step was not necessary to prove Theorem 1. Should this step be carried out classically, this would result in C = O(r 2) calls to g. The net result would be that the key is found after an expected O(N5/3 ) calls to f and also O(N5/3) calls to g.

### Lower Bound

The proof that the quantum attack described above against our protocol is optimal proceeds in three steps.

1. We define a search problem reminiscent of element distinctness;
2. We prove a lower bound on the difficulty to solve this search problem; and
3. We reduce this search problem to the eavesdropping problem against our protocol. More precisely, we show that any attack on our key distribution scheme that would have a nonvanishing probability of success after o(N5/3) calls to functions f and g could be turned into an algorithm capable of solving the search problem more efficiently than possible.

First, consider a function c : [N] → [N] so that there exists a single pair (i, j), 1 6 i < j 6 N, for which c(i) = c(j). Ambainis’ quantum algorithm for element distinctness [2] can find this pair with O(N2/3) queries to function c and Scott Aaronson and Yaoyun Shi proved that this is optimal even for the decision version of this problem [1].

Now, consider a function h : [N] × [N2] → [N]0, where [N]0 denotes {0} ∪ [N]. The domain of this function is composed of N “buckets” of size N2, where h(i, ·) corresponds to the i th bucket, 1 6 i 6 N. In bucket i, all values of the function are 0 except for one single random vi ∈ [N2] for which h(i, vi) = c(i): h(i, j) = ( c(i) if j = vi 0 otherwise .

It follows from the definitions of c and h that there is a single pair of distinct a and b in the domain of h such that h(a) = h(b) 6= 0. How difficult is it to find this pair given a black box for function h but no direct access to c?

Lemma 1. Given h structured as above, finding the pair of distinct elements a and b in the domain of h such that h(a) = h(b) 6= 0 requires Ω(N5/3) quantum queries to h, except with vanishing probability.|This problem can be modelled as the composition of element distinctness across buckets with finding the single non-zero entry in each bucket. It is therefore a special case of technical Lemma 5, stated in the Appendix, with parameters α = N (the number of buckets) and β = N2 (the size of the buckets). It follows that finding the desired pair (a, b) requires Ω(α 2/3β 1/2 ) = Ω(N 2/3 √ N2 ) = Ω(N 5/3 ) quantum queries to h, except with vanishing probability.

Consider now a slightly different search problem in which there are no buckets anymore, but there is an added coordinate in the image of the function:h0: [N3] → [N]0 × [N]0 is defined so that h0(a) = (0, 0) on all but N randomly chosen points in its domain, namely w1, w2,. . . , wN . On these N points,h0(wi) = (i, c(i)), where c is the function considered at the beginning of this section. We are required to find the unique pair of distinct a and b in [N3] such that π2(h0(a)) = π2(h0(b)) 6= 0, where “ π2 ” denotes the projection on the second coordinate (similarly for “ π1 ”). The lower bound on the earlier search problem concerning h implies directly the same lower bound on the new search problem concerning h0 since any algorithm capable of solving the new problem can be used at the same cost to solve the earlier problem through randomization. In other words, the more structured version of the problem cannot be harder than the less structured one. The next Lemma formalizes the argument above. Lemma 2. Given h0 structured as above, finding the pair of distinct elements a and b in the domain of h0 such that π2(h0(a)) = π2(h0(b)) 6= 0 requires Ω(N5/3) quantum queries to h0, except with vanishing probability.|Define intermediary function h˜ : [N] × [N2] → [N]0 × [N]0 by h˜(i, j) = ( (i, h(i, j)) = (i, c(i)) if h(i, j) 6= 0 (0, h(i, j)) = (0, 0) otherwise .

It is elementary to reduce the search problem concerning h to the one concerning h˜ as well as the search problem concerning h˜ to the one concerning h0.Therefore, the lower bound concerning h given by Lemma 1 applies mutatis mutandis to h0.

Finally, we show how to reduce the search problem concerning h0 to the cryptanalytic difficulty for the eavesdropper to determine the key that Alice and Bob have established by using our protocol. This is the last step in proving the security of our scheme.

Theorem 2. Any eavesdropping strategy that recovers the key (x, x0) in protocol 1 requires a total of Ω(N5/3) quantum queries to functions f and g, except with vanishing probability.|Consider any eavesdropping strategy A that listens to the communication between Alice and Bob and tries to determine the key (x, x0 ) by querying blackbox functions f and g. In fact, there are no Alice and Bob at all! Instead, there is a function h0: [N3] → [N]0 × [N]0 as described above, for which we want to solve the search problem by using unsuspecting A as a resource.
We start by supplying A with a completely fake “conversation” between “Alice” and “Bob”: for sufficiently large k and k0, we choose randomly N points y1, y2,. . . , yN in [Nk] and one point w ∈ [Nk0] and we pretend that Alice has sent the y’s to Bob and that Bob has responded with w. We also choose random functions ˆf : [N3] → [Nk] and ˆg : [N3] × [N3] → [Nk0], as well as a random Boolean s ∈ {true, false}. Note that the selection of ˆf and ˆg may take a lot of time, but this does not count towards the number of queries that will be made of function h0, and our lower bound on the search problem concerns only this number of queries. The Boolean s indicates, when true (resp. false), that the fake “execution” is such that “Bob” has first picked x and then x0 such that x < x0 (resp. x0 > x). Both cases happen with probability 1/2 in any real execution and for any public announcements Y and w. The value s will be used in the reduction to distinguish between g(x, x0 ) and g(x0, x) so that only g(x, x0) will be set to w.
Now, we wait for A’s queries to f and g. – When A asks for f(i) for some i ∈ [N3], there are two possibilities.

• If h0(i) = (0, 0), return ˆf(i) to A as value for f(i).
• Otherwise, return yπ1(h0(i)) .

– When A asks for g(i, j) for some i, j ∈ [N3], there are again two possibilities.

• If π2(h0(i)) = π2(h0(j)) 6= 0 and either s is true and i < j or s is false and i > j, return w as value for g(i, j).
• Otherwise, return ˆg(i, j).

Suppose A happily returns the pair (i, j) for which it was told that g(i, j) = w, which is what a successful eavesdropper is supposed to do. This pair is in fact the answer to the search problem concerning h0 since g(i, j) = w implies that π2(h0(i)) = π2(h0(j)) 6= 0, except with the negligible probability that ˆg(i0, j0) = w for some query (i0, j0) that A asks about g.
Queries asked by A concerning f and g are answered in the same way as they would be if f and g were two random functions consistent with the Y and w announced by Alice and Bob during the execution of a real protocol. To see this, remember that Y (subset of [Nk]) and w (element of [Nk0]) are uniformly pickedat random in both the simulated and the real worlds. Moreover, the simulated function f is such that f(i) is random when h 0(i) = (0, 0). The remaining N output values are in Y, as expected by A. On the other hand, the simulated function g is random everywhere except for one single input pair (i, j), i 6= j for which g(i, j) = w, as it is also expected by A. Therefore, A will behave in the environment provided by the simulation exactly as in the real world. Since we disregard the negligible possibility that g might not be be one-to-one, the reduction solves the search problem concerning h 0 whenever A succeeds in finding the key. Notice finally that each (new) question asked by A to either f or g translates to one or two questions actually asked to h0.
It follows that any successful cryptanalytic strategy that makes o(N5/3) total queries to f and g would solve the search problem with only o(N5/3) queries to function h0, which is impossible, except with vanishing probability. This establishes the Ω(N5/3 ) lower bound on the cryptanalytic difficulty of breaking our key exchange protocol, again except with vanishing probability, which matches the upper bound provided by the explicit attack given in Sect. 3.1.

## Fully Classical Key Distribution Scheme

In this section, we revert to the original setting imagined by Merkle in the sense that Alice and Bob are now purely classical. However, we allow full quantum power to the eavesdropper. Recall that Merkle’s original schemes [15, 16] are completely broken in this context [8]. Is it possible to restore some security in this highly adversarial (and unfair!) scenario? The following purely classical key distribution protocol, which is inspired by our quantum protocol described in the previous section, provides a positive answer to this conundrum.

This time, black-box random functions f and g are defined on a smaller domain to compensate for the fact that classical Alice and Bob can no longer use Grover’s algorithm. Specifically, f : [N2] → [Nk] and g : [N2]×[N2] → [Nk0], again with sufficiently large k and k0 to avoid collisions in these functions, except with negligible probability (k and k0 need not be the same here as in the previous section). As before, these two functions could be replaced by a single binary random oracle. For simplicity, we choose N to be a perfect square.

Protocol 2. 1. Alice picks at random N distinct values {xi} Ni=1 with xi ∈ [N2] and transmits the encrypted values yi = f(xi) to Bob. Let X and Y denote {xi| 1 6 i 6 N} and {yi | 1 6 i 6 N}, respectively. 2. Bob finds the pre-images x and x0 of two distinct random elements in Y.To find each one of them, he chooses random values in [N2] and applies f to them until one is found whose image is in Y. By virtue of the birthday paradox, he is expected to succeed after O(N2 ) = O(N) calls to function f. Until now this is identical to Merkle’s original scheme, except for the fact that Bob needs to find two elements of X rather than one. 3. Bob sends back w = g(x, x0) to Alice. In addition, he chooses N − 2 random elements from Y \ {f(x), f(x0)} and he forms a set Y0 of cardinality N by adding f(x) and f(x0) to those elements. He sends the elements of Y0 to Alice in increasing order of values. 4. Because Alice had kept her randomly chosen set X, she knows the preimages of each element of Y0. Let X0 denote {x ∈ X | f(x) ∈ Y0}. By exhaustive search over all pairs of elements of X0, Alice finds the one pair (x, x0) such that g(x, x0) = w.5. The key shared by Alice and Bob is the pair (x, x0).

All counted, Alice makes N calls to f in step 1 and at most N calls to g in step 4 because there are NN = N pairs of elements of X0 and one of them is the correct one. As for Bob, he makes an expected O(N) calls to f in step 2 and a singe call to g in step 3. The total expected number of calls to f and g is therefore in O(N) for both legitimate parties.

### Quantum Attack

Theorem 3. There exists an eavesdropping strategy that outputs the pair (x, x0)in Protocol 2 with O(N13/12) expected quantum queries to functions f and g.|A quantum eavesdropper can set up a walk in a Johnson graph very similar to the one explained in Sect. 3.1, except that now the nodes in the graph contain some number r (to be determined later) of distinct elements of X0 (rather than of X). The eavesdropper can find random elements of X0 from his knowledge of Y0 with an expected .... calls to f per element of X0 . Therefore, S = O(rN3/4 ) calls to f, U = O(N3/4 ) calls to f and C = O(r) calls to g. Furthermore, δ is still Θ(1/r) butε = Ω(r2/N).
Putting it all together, the expected quantum cryptanalytic cost is .... To minimize the number of calls to f, we choose r so that rN3/4 = N5/4/r, which is r = N1/3. It follows that a quantum eavesdropper is able to find the key (x, x0 ) with an expected O(rN3/4) = O(N13/12) calls to f and O(N) callsto g.

### Lower Bound

The proof that it is not possible to find the key (x, x0) with fewer than Ω(N13/12) calls to f and g, except with vanishing probability, follows the same lines as the lower bound proof in Sect. 3.2. It is therefore possible for purely classical Alice and Bob to agree on a shared key after calling f and g an expected number of times in the order of N whereas it is not possible, even for a quantum eavesdropper, to be privy of their secret with an effort in the same order, except with vanishing probability. We refer the reader to Sect. 3 for the meaning of notation [N] and to Sect. 3.2 for the definitions of projectors π1, π2, and the meaning of notation [N]0. Consider a function c : [N ] → [N] so that there is a single pair (i,j),
1 6 i < j 6N, for which c(i) = c(j). Aaronson and Shi’s lower bound [1] tells us that finding this pair requires Ω((√N)2/3) = Ω(N1/3) calls to function c.Now, consider a function h : [√N ] × [N3/2] → [√N]0 where h(i, ·) denotes the ith bucket, 1 6 i 6√N. In bucket i, all values of the function are 0 except for one: there is a single random vi ∈ [N3/2] such that h(i, vi) = c(i). It follows from the definitions of c and h that there is a single pair of distinct a and b in the domain of h such that h(a) = h(b) 6= 0.

Lemma 3. Given h structured as above, finding the pair of distinct elements a and b in the domain of h such that h(a) = h(b) 6= 0 requires Ω(N13/12) quantum queries to h, except with vanishing probability.|The proof is identical to the one for Lemma 1, mutatis mutandis. It is again a special case of Lemma 5, but with parameters α =N (the numberof buckets) and β = N3/2 (the size of the buckets). It follows that finding the desired pair (a, b) requires .... quantum queries to h, except with vanishing probability.

Let h0: [N2] → [√N ]0 × [√N ]0 denote the unstructured version of the same search problem for h, defined the same way as in Sect. 3.2, mutatis mutandis. There is a single pair of distinct elements a and b such that π2(h0(a)) = π2(h0(b)) 6= 0. The problem of finding this pair is at least as difficult as finding the collision in h. Lemma 4. Given h0structured as above, finding the pair of distinct elements aand b in the domain of h0such that π2(h0(a)) = π2(h0(b)) 6= 0 requires Ω(N13/12)quantum queries to h0, except with vanishing probability.|Without proof. It remains to show that the search problem concerning h0 reduces to the cryptanalytic difficulty for the eavesdropper to determine the key established by Alice and Bob.

Theorem 4. Any eavesdropping strategy that recovers the key (x, x0) in protocol 2 requires a total of Ω(N13/12) quantum queries to functions f and g, except with vanishing probability.|Consider any eavesdropping strategy A that listens to the communication between Alice and Bob and tries to determine the key (x, x0) by querying the black-box functions f and g. As before, the reduction does not have access to Alice and Bob but instead, to a function h0: [N2] → [√N ]0 × [√N ]0 as described above and given as an oracle, for which we want to solve the search problem by using A as a resource.
We choose random functions ˆf : [N2] → [Nk] and ˆg : [N2] × [N2] → [Nk0], as well as a random Boolean s ∈ {true, false}, which has the same purpose as in the proof of Theorem 2. Let Im( ˆf) denote the image of function ˆf. We then supply A with a fake “conversation” between “Alice” and “Bob”: we choose randomly √N points y01, y02,. . . , y√0Nin [Nk], N −√N points y1, y2, . . . , yN−√N in Im( ˆf) ⊂ [Nk], and one point w ∈ [Nk0]. We pretend that Alice has sent thelist Y = {y1, y2, . . . , yN−√N} ∪ {y01, y02, . . . , y√0N} to Bob (in random order) and that Bob has responded with Y0 = {y01, y02, . . . , y√0N} (in increasing order) and w.
Now, we wait for A’s queries to f and g.

• When A asks for f(i) for some i ∈ [N2], there are two possibilities:
• If h0(i) = (0, 0), return ˆf(i) to A as value for f(i).
• Otherwise, return y0π1(h0(i)) .
• When A asks for g(i, j) for some i, j ∈ [N2], there are two possibilities:
• If π2(h0(i)) = π2(h0(j)) 6= 0 and either s is true and i < j or s is false and i > j, return w as value for g(i, j).
• Otherwise, return ˆg(i, j).

Suppose A happily returns the pair (i, j) for which it was told that g(i, j) = w, which is what a successful eavesdropper is supposed to do. This pair is in fact the answer to the search problem concerning function h 0. Indeed, g(i, j) = w for only the pair (i, j) for which π2(h0(i)) = π2(h0(j)) 6= 0, except with the negligible probability that ˆg(i0, j0) = w for some query (i0, j0) that A asks about g. However, we need an additional condition for the reduction to create an environment identical to the real one: if y ∈ Y then h 0(f−1(y)) = (0, 0). This is required for all elements in Y \ Y0to be accessible when A is querying f inthe reduction. Fortunately, it is easy to see that this condition is satisfied except with vanishing probability when k is large enough. Provided this condition is satisfied, queries asked by A concerning f and g are answered in the same way as they would be if both f and g were random functions consistent with the Y, Y 0 and w announced by Alice and Bob during the execution of the protocol. To see this, remember that Y and Y0 (subsetsof [Nk]) and w (element of [Nk0]) are uniformly picked at random in both the simulated and the real worlds. Moreover, the simulated function f is such that f(i) is random when h0(i) = (0, 0). Among these N2 −√N input values, thereare exactly N −√N output values in Y \ Y0√, as expected by A. The remainingN input values i also satisfy f(i) ∈ Y0 as it should be. On the other hand, the simulated function g is random everywhere except for one single input pair(i, j), i 6= j, for which g(i, j) = w, as it is also expected by A. Therefore, A will behave in the environment provided by the simulation exactly as in the real case. Since we disregard the negligible possibility that g might not be be one-to-one, the reduction solves the search problem concerning h 0 whenever A succeeds in finding the key. Notice again that each (new) question asked by A to either f or g translates to one or two questions actually asked to h0. It follows that any successful cryptanalytic strategy that makes o(N13/12)total queries to f and g would solve the search problem with only o(N13/12) queries to function h0, which is impossible by Lemma 4, except with vanishing probability. This establishes the Ω(N13/12) lower bound on the cryptanalytic difficulty of breaking our key exchange protocol, which matches the upper bound provided by the explicit attack discussed in Sect. 4.1.

## Conclusion, Conjectures and Open Questions

We presented an improved protocol for quantum key distribution over a classical channel and the first secure protocol for classical key distribution against a quantum adversary. Is it possible that they are optimal? We conjecture that they are not. Indeed, we have discovered two sequences of protocols Q and C for  > 2 (which we shall describe in a subsequent paper) with the following properties. In protocol Q, a classical Alice exchanges a key with a quantum Bob after O(N) accesses to a random oracle in such a way that our most efficient quantum eavesdropping strategy requires the eavesdropper to access the same random oracle ΘN1+ +1 � expected times. In protocol C, purely classical Alice and Bob exchange a key after O(N) accesses to a random oracle in such a way that our most efficient quantum eavesdropping strategy requires the eavesdropper to access the same random oracle ΘN12 + +1 � expected times.

Our attacks proceed by quantum walks in Johnson graphs similar to those exploited in the proofs of Theorems 1 and 3 to obtain optimal attacks against our protocols 1 and 2. If they are the best possible against our new protocols as well, then key distribution protocols a la Merkle can be arbitrarily as secure in our quantum world as they were in the whimsical classical world known to Merkle in 1974: arbitrarily close to quadratic security can be restored. The obvious open question is to prove the optimality of our attacks. It would also be interesting to find a quantum protocol that exactly achieves quadratic security. . . or better! Indeed, even though it has been proven in the classical case that quadratic security is the best that can be achieved [3], there is no compelling evidence yet that such a limitation exists in the quantum world.

If our quantum attacks against the classical protocols are optimal, classical Alice and Bob can exchange a secret key against a quantum eavesdropper with as good a security (in the limit) as it was known to be possible for quantum Alice and Bob before this work. The main open question would be to break the Ω(N3/2) barrier or prove that this is not possible. Even though our protocols Q and C require classical Alice to access the random black-box function only N times, she has to work for a time in Θ(N) to complete her share of the protocol. (This could be reduced to Θ(N/2) for Q if both Alice and Bob used quantum computing capabilities, but this remainsnonlinear as soon as  > 3.) Could similar protocols exist in which Alice would be efficient even outside the required calls to the black-box function?

Finally, our lower bounds prove that it is not possible for the eavesdropper tolearn Alice and Bob’s key (x, x0), except with vanishing probability, unless she queries the black-box functions significantly more than the legitimate parties. However, we have not addressed the possibility for the eavesdropper to obtain efficiently partial information about the key. We leave this important issue for further research.

## Acknowledgements

We are grateful to Troy Lee and Mohammad Mahmoody-Ghidary for insightful discussions. G. B. is also grateful to Ralph Merkle for his most inspiring Distinguished Lecture at Crypto ’05, which sparked this entire line of work. G. B. is supported in part by Canada’s Natural Sciences and Engineering Research Council of Canada (Nserc), the Institut transdisciplinaire d’informatique quantique (Intriq), the Canada Research Chair program, the Canadian Institute for Advanced Research (Cifar) and the QuantumWorks Network. P. H. is supported in part by Nserc, Cifar, QuantumWorks, and the Canadian Network Centres of Excellence for Mathematics of Information Technology and Complex Systems (Mitacs). S. L. is supported in part by the European Union 7th framework program Qcs, Anr D´efis Qrac and Anr Jeune chercheur Cryq. L. S. is supported in part by Nserc, QuantumWorks, Fundamental Research on Quantum Networks and Cryptography (Frequency) and Intriq.

## Contacts

Cite error: Invalid <references> tag; parameter "group" is allowed only.

Use <references />, or <references group="..." />

## References

Cite error: Invalid <references> tag; parameter "group" is allowed only.

Use <references />, or <references group="..." />

Cite error: <ref> tags exist for a group named "@:", but no corresponding <references group="@:"/> tag was found, or a closing </ref> is missing
1. R. Merkle, “C.S. 244 Project Proposal”, 1974. Facsimile available at http://www.merkle.com/1974.
2. R. Merkle, “Secure communications over insecure channels”, Communications of the ACM 21(4):294–299, 1978.
3. Cite error: Invalid <ref> tag; no text was provided for refs named .5B8.5D
4. Cite error: Invalid <ref> tag; no text was provided for refs named .5B2.5D
5. B. Barak and M. Mahmoody–Ghidary, “Merkle puzzles are optimal — An O(n2)– query attack on any key exchange from a random oracle”, Advances in Cryptology – Proceedings of Crypto 2009, Santa Barbara, California, pp. 374–390, 2009.
6. W. Diffie and M. E. Hellman, “New directions in cryptography”, IEEE Transac- tions on Information Theory 22(6):644–654, 1976.
7. L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack”, Physical Review Letters, 79(2):325–328, 1997.
8. M. Boyer, G. Brassard, P. Høyer and A. Tapp, “Tight bounds on quantum search- ing”, Fortschritte Der Physik 46:493–505, 1998.
9. C. H. Bennett, E. Bernstein, G. Brassard and U. V. Vazirani, “Strengths and weak- nesses of quantum computing”, SIAM Journal on Computing 26(5):1510–1523, 1997.