It is Christmas 1974, in the midst of the cold war, and intelligence officer Alice is trying to reach her asset Bob, who is undercover in Budapest, from her apartment in Amsterdam. She knows Bob has confidential information to share with her, but the two of them suspect their telephone line may be tapped. Indeed, East German counter-intelligence agent Eve is listening in to their conversation. The problem of securely transmitting information over an insecure channel has been studied for thousands of years and could, for many purposes, be considered a solved problem by the 1970s. In particular, ciphers like the one-time pad allowed for unbreakable encryption of communication as long as the two communicating parties agreed on a large enough shared secret, the so-called secret key, ahead of time. Unfortunately for our two protagonists, Bob lost the secret key he had agreed with Alice during his latest undercover operation. Up until this point in history, conventional wisdom was that Alice and Bob were now screwed: That without a secret key shared ahead of time, there was no way for Bob to transmit information such that Alice could decipher it but eavesdropping Eve could not.

Luckily for Alice, just a few months before on the other side of the world, UC Berkeley undergraduate student Ralph Merkle wrote a course project proposal that challenged this long-standing belief (Merkle 1974). His idea, nowadays known as Merkle puzzles, constituted the world’s first key exchange protocol.

Key exchange protocols

A key exchange protocol is a set of instructions telling Alice and Bob what to compute and send over the channel, such that, after the execution of all instructions, both obtain the same secret key which is oblivious to any eavesdropper like Eve. Concretely, we parameterize the effort it takes Alice and Bob to execute the protocol by a security parameter $n$. (This could for example be the total number of steps they need to execute, but we’ll see a better quantity soon.) We then measure the amount of effort it would take Eve to have any real chance at recovering the secret Alice and Bob agreed to just from the information sent via the channel in terms of the same security parameter $n$. A key exchange protocol requires that Eve needs to exert strictly more effort than Alice and Bob. A protocol is more secure the larger the gap between these two is. Once Alice and Bob have agreed on a shared secret, they can use the existing cryptographic protocols to communicate securely.

Asymmetry in computation

Merkle’s breakthrough result relies on an observation about asymmetry in the world of computation, specifically that we think some functions $f$ are easy to compute for any given input $x$ but hard to invert. Breaking up a completed jig-saw puzzle does not lose any information in the sense that most jig-saw puzzles have only one sensible arrangement, but clearly the process of breaking up the completed puzzle is much easier than putting the individual puzzle pieces back together. Some mathematical problems seem to be of a similar nature. For example: Multiplying prime numbers together is easy, while we don’t know any efficient procedure to split composite numbers into all of their prime factors. The notion of non-invertibility needed for Merkle puzzles is as follows: We want some easy-to-compute function $f$, such that given a (uniformly) random input $x$, no algorithm can successfully determine an $x'$ such that $f(x) = f(x')$ but with a negligible probability. There are many candidate functions that are believed to exhibit this behavior, but actually proving this would have wide-ranging implications (including that $P \not= NP$) and seems beyond our current methods. Instead, for analyzing a protocol like this we turn to an idealized form of such a function, a so-called Random Oracle (RO). Think of a RO as a single magic box that each of Alice, Bob, and Eve have access to and can query with an input $x$.

The first time the RO is queried on the input $x$, it picks a random value $y$ to output. Every subsequent time the RO is queried with the same $x$ it outputs the same $y$. It is easy to see that such a RO is hard-to-invert, since given a $y$ there is clearly no better strategy of finding the corresponding input $x$ than simply trying out all possible inputs. Of course, random oracles don’t actually exist in the real world, but in practise we can instantiate (substitute) them with any of the candidate hard-to-invert functions.¹

Merkle puzzles

Let $n \in \mathbb{N}$ be the security parameter and $\mathrm{RO} \colon \{1, \dots, n^2\} \to \{0,1\}^n$ be a random oracle that maps inputs between $1$ and $n^2$ to binary strings of length $n$. The Merkle Puzzle key exchange now proceeds as follows:²

1. Alice chooses $10n$ numbers $x_1, \dots, x_{10n}$ uniformly at random from the range between 1 and $n^2$. For each $x_i$ she queries the RO and receives an output $a_i = \mathrm{RO}(x_i)$. She sends all $10n$ values $a_1, \dots, a_{10n}$ to Bob via the channel.
2. Analogously, Bob chooses $10n$ numbers $y_1, \dots, y_{10n}$ uniformly at random from the range between 1 and $n^2$. For each $y_i$ he queries the RO and receives an output $b_i = \mathrm{RO}(x_i)$. He sends all $b_1, \dots, b_{10n}$ over the channel.
3. If there exists a pair $(i,j)$ such that $a_i = b_j$, then both Alice and Bob take the lexicographically smallest (first) such pair and take $x_i$ and $y_j$ as their secret keys respectively. We call such a pair a collision. If no such collision exists, they both take $1$ as their secret key.

In our model, the security parameter $n$ therefore quantifies how many times Alice and Bob have to query the RO ($10n$ times each). This is a good measure as computing the hard-to-invert function which the RO stands in for is usually the most computationally intensive part of the protocol by far. Alice and Bob will agree to the same (non-trivial) key if:

1. the RO is injective, whereby we ensure any collision in step 3 actually leads to Alice and Bob’s adopted keys $x_i$ and $y_j$ being equal, and
2. a collision occurs.

The chance that the random oracle assigns two different inputs $x_1$ and $x_2$ the same output $y$ is $\frac{1}{2^n}$. By a union bound, the likelihood of this not happening for any of the $\approx n^2 \cdot n^2$ pairs of distinct inputs is at least $1 - \frac{n^4}{2^n}$ which quickly approaches 100% as we increase the security parameter $n$.

The birthday problem

As for point 2, one might intuitively think that because Alice and Bob only pick $10n$ random values from a possible range of $n^2$ (which is far larger for even moderate choices of $n$) there is a good chance of no collision occurring at all. To see why this is intuition is wrong, let us consider the closely relate birthday problem. How large does a friend group have to be for at least two people in the group to share the same birthday? Despite the probability of two people sharing the same birthday being just $\frac{1}{365}$, it turns out that with just 23 people, it is more likely than not that two of them do in fact share the same birthday. Intuitively, this is because we have to consider all possible pairs of people, of which there are $\frac{23 \cdot 22}{2} = 253$ within a group of 23. Applying this to our collision problem, the chance of no collision happening turns out to be less than 1 in $2^{100}$ (for $n$ at least 10). Therefore, Alice and Bob fail to agree on a shared secret key with only a miniscule probability.

No luck for the eavesdropper

What about Eve, who has been listening in this whole time? All the information she sees communicated are the $a_i$s and $b_i$s. She can of course also find the collision $a_i = b_j$ but the only way she can compute the underlying shared secret is to invert the random oracle given the output $a_i = b_j$. As mentioned earlier, there can be no better strategy than just trying out all $n^2$ possible inputs, and we expect her to find the correct input only after $\frac{n^2}{2}$ tries. As we increase the security parameter $n$, this effort soon exceeds the $10n$ queries needed by Alice and Bob, meaning Merkle Puzzles indeed form a key exchange.

Outlook

The “square” gap between the effort of magnitude $n$ by Alice and Bob against the $\approx n^2$ required by Eve to recover the shared secret is not considered large enough for practical use. Luckily, only two years later in 1976, Whitfield Diffie and Martin Hellman (whom Merkle had approached after his course instructor rejected his project idea) developed an improved key exchange with a much larger gap in effort ($n$ vs $\approx 2^{\sqrt[3]{n}}$), using not any hard-to-invert function, but one specific candidate and its special algebraic properties (Diffie and Hellman 1976). More than 40 years after they were conceived, Boaz Barak and Mohammad Mahmoody proved that Merkle Puzzles are in fact optimally secure among key exchanges that work with arbitrary hard-to-invert functions (Barak and Mahmoody-Ghidary 2017).

Bibliography

Barak, Boaz, and Mohammad Mahmoody-Ghidary. 2017. “Merkle’s Key Agreement Protocol Is Optimal: An o(n${}^{\mbox{2}}$) Attack on Any Key Agreement from Random Oracles.” J. Cryptol. 30 (3): 699–734. https://doi.org/10.1007/S00145-016-9233-9 .

Canetti, Ran, Oded Goldreich, and Shai Halevi. 2004. “The Random Oracle Methodology, Revisited.” J. ACM 51 (4): 557–94. https://doi.org/10.1145/1008731.1008734 .

Diffie, Whitfield, and Martin E. Hellman. 1976. “New Directions in Cryptography.” IEEE Trans. Inf. Theory 22 (6): 644–54. https://doi.org/10.1109/TIT.1976.1055638 .

Merkle, Ralph C. 1974. “Publishing a New Idea.” https://www.ralphmerkle.com/1974/ .