{\huge A Matter of Agreement}

On the 2015 Turing Award \vspace{.25in}

Whitfield Diffie, Martin Hellman, and Ralph Merkle publicly broke the yoke of symmetry in cryptography in the 1970s. Their work created the era of modern cryptography---all previous work, including the great work of Claude Shannon in 1949, implicitly assumed that the system must be symmetric.

Today we congratulate Diffie and Hellman on winning the 2015 ACM Turing Award and discuss the contributions of all three.

In all previously known cryptosystems, knowledge of the encryption mechanism and the initial state conferred the ability to decode. Transmitting a complete encryption key on an insecure channel would compromise everything. They implemented ways that two separated parties could communicate over an insecure channel to agree on a common complete key without an eavesdropper being able to learn it---except by significantly greater computational effort. Then Diffie and Hellman conceived how to divide the key into halves so that transmitting one part enabled the second party to encode messages that are efficiently decodable by the first party but not by eavesdroppers, and the first party to authenticate itself as the source of its outgoing messages.

The three have been recognized together before: for the 2010 IEEE Richard W. Hamming Medal and joint with Leonard Adleman, Ronald Rivest, and Adi Shamir for the 1996 inaugural Paris Kanellakis Award. Last Tuesday's New York Times story cropped out Merkle out of the photo that had been used with Stanford University's article on the Hamming award. Above we have made a mirror image of the photo instead, so as to play on ``symmetry'' and make the names run alphabetical left-to-right.

Two Puzzles About Merkle

An obvious question concerns the omission of Merkle from the Turing Award. Ralph, who spent some years on our faculty at GIT, certainly was part of the revolution that the three started. Perhaps Ralph will be honored in the future; perhaps his long interest in other types of research, such as nano-computation, made him less obvious a candidate; perhaps there are reasons we are unaware of.

Clearly the earlier prize committees reached different conclusions, and this depends on how criteria for a prize are weighted. The Turing award is often compared to a Nobel Prize, but the latter is expressly for one discovery or one achievement. The Gödel Prize is awarded for one or more papers on a single topic. The Turing Award is more geared to multiple fundamental contributions. Evidently Diffie and Hellman were singled out for their implementation of key exchange which did not involve Merkle, but besides remarks by Hellman in a 2002 article and a 2004 interview that Merkle's name should be included on the algorithm, it strikes us as determinative that Merkle was included on the official patent.

Well, there is a third side to the story. James Ellis conceived asymmetric cryptography in 1970, Clifford Cocks essentially discovered the RSA implementation in 1973, and Malcolm Williamson discovered the Diffie-Hellman implementation of key agreement. But their work was classified in Britain's secret service until 1997. Their story was told soon afterward here with a comment that ``history books will have to be re-written,'' but have they?

Perhaps the answer to this ``Merkle puzzle'' will wind up being the way Chey Cobb put it as author of Cryptography for Dummies:

Diffie-Hellman (& Merkle)

Let's go on to describe the original Merkle Puzzles to understand the genesis of all this. As usual we try to describe things differently from other sources when we can.

The Merkle Game

The movie ``The Imitation Game'' depicts how Alan Turing's group at Bletchley Park had less than a day to crack the initial state $latex {s}&fg=000000$ used for every one of their $latex {n}&fg=000000$ Enigma machines that day. Having the same machines in their possession did not solve the problem. The movie shows how knowing some of the plaintext cut down the space of possibilities enough for their ``Bombe'' machines to reduce the cracking time to some number $latex {m}&fg=000000$ of minutes. The weakness they exploited was that the Germans had to transmit $latex {s}&fg=000000$ in a bootstrapped manner before the start of each day's business.

Suppose the Germans had behaved this way: Randomly select $latex {Cn}&fg=000000$ initial states $latex {s_i}&fg=000000$ each morning, where $latex {C}&fg=000000$ is fairly large but not prohibitive. Don't send those states but rather encrypt $latex {Cn}&fg=000000$ messages $latex {m_i}&fg=000000$ as ciphertexts $latex {t_i}&fg=000000$, where $latex {t_i}&fg=000000$ uses key $latex {s_i}&fg=000000$, as ``puzzles'' of the kind that one's own Turings and Bombes at each field point can break in $latex {m}&fg=000000$ minutes. They can deliberately contain exposed plaintext of the kind the movie says ``won the war'' for the Allies to help them get broken. Each field point chooses one $latex {t_j}&fg=000000$ at random, breaks it in $latex {m}&fg=000000$ minutes to get $latex {s_j}&fg=000000$, and sends a key-dependent response $latex {r_j}&fg=000000$ back to HQ over the open channels. It is important that $latex {r_j}&fg=000000$ does not simply reveal $latex {m_j}&fg=000000$ or $latex {s_j}&fg=000000$, but HQ can tell which of $latex {s_1,\dots,s_{Cn}}&fg=000000$ it belongs to by its prior knowledge. Then HQ and that field point can communicate using $latex {s_j}&fg=000000$.

Now picture the poor people at Bletchley Park. They have time to crack any one key $latex {s_k}&fg=000000$, but there is less than a $latex {1/C}&fg=000000$ chance that $latex {s_k}&fg=000000$ is even used. Even if they crack $latex {d}&fg=000000$-many and get one used $latex {s_j}&fg=000000$ that together with the intercepted $latex {r_j}&fg=000000$ enables them to know that $latex {s_j}&fg=000000$ is being used, that's good for only one field point. It doesn't compromise the whole military command as Ultra actually provided. Worst, is there is a field point that they particularly desire to crack, their chance of getting its key is bounded by $latex {d/Cn}&fg=000000$.

Even if two or more field stations ``collide'' by having chosen the same $latex {t_j}&fg=000000$---as is likely by the ``birthday paradox'' when $latex {C = o(n)}&fg=000000$---this doesn't improve Bletchley's expectation. Only by spending order-of $latex {mCn}&fg=000000$ time to crack most of the ciphertext ``puzzles'' could Bletchley be sure to read many of the plaintexts. However, HQ has the power to scale the parameters so that $latex {mCn}&fg=000000$ leaves not enough time in the day. The final point is that there is nothing more the Bletchley people could do---no more ingenious algebra can help---unless they could somehow expose a flaw in how the puzzles are randomly generated.

This is basically Merkle's scheme for key agreement. We have added the wrinkle of multiple field stations but noted the cover of redundancy it provides to any one station. One big strength is that the scheme is not tied to any particular implementation. The main weakness is that the time-of-cover provided is only quadratic, a matter of $latex {O(mnC)}&fg=000000$ to crack versus $latex {O(nC + m)}&fg=000000$ to implement. A higher polynomial---let alone an exponential difference---would be desirable, but this 2008 paper by Boaz Barak and Mohammad Mahmoody-Ghidary showed that quadratic advantage is tight for any implementation of ``Merkle's Puzzles'' in the random-oracle model. Can we find a different scheme to agree on a key over open channels with greater time cover?

Diffie-Hellman

Enter Diffie and Hellman. The idea is amazingly simple. Take any cyclic group $latex {A}&fg=000000$ for which we can find a generator $latex {g}&fg=000000$. The bellwether instance is $latex {A}&fg=000000$ being the multiplicative group modulo an $latex {n}&fg=000000$-bit prime $latex {p}&fg=000000$ but it could be anything. We need $latex {|A|}&fg=000000$ to be large in terms of $latex {n}&fg=000000$ but powering $latex {g^a}&fg=000000$ for $latex {a < |A|}&fg=000000$ to be computable in time that is a small polynomial in $latex {n}&fg=000000$. All participants know $latex {g}&fg=000000$ and $latex {A}&fg=000000$ (or $latex {p}&fg=000000$) in advance, and these may be publicly known. The protocol goes as follows:

• HQ privately selects a private integer $latex {a}&fg=000000$, forms $latex {h = g^a}&fg=000000$, and sends $latex {h}&fg=000000$ over an open channel to a field station.
• The field station simultaneously selects its own $latex {b}&fg=000000$, forms $latex {h' = g^b}&fg=000000$, and sends $latex {h'}&fg=000000$ to HQ.
• HQ forms $latex {s = h'^a = g^{ba}}&fg=000000$ and knows that the field station will get the same value via $latex {s = h^b = g^{ab}}&fg=000000$.
• The parties then communicate using the initial state $latex {s}&fg=000000$.

This scheme can easily be replicated for $latex {n}&fg=000000$ field stations. HQ should choose a different private $latex {a_j}&fg=000000$ for each station $latex {j}&fg=000000$ (which in turn uses its own $latex {b_j}&fg=000000$) but it is OK to use the same $latex {A}&fg=000000$ and $latex {g}&fg=000000$. Alternatively, three parties can make a communications triangle by respectively choosing their own $latex {a,b,c}&fg=000000$ and sharing $latex {g^{abc}}&fg=000000$, and so on. But all this is jumping ahead---let's just consider $latex {n = 1}&fg=000000$ with two parties.

Picture our Bletchley Park people now. They can read $latex {h}&fg=000000$ and $latex {h'}&fg=000000$ besides knowing $latex {g}&fg=000000$ and $latex {A}&fg=000000$ (that is, $latex {p}&fg=000000$). The question is, can they infer the powers of $latex {g}&fg=000000$ that make $latex {h}&fg=000000$ and $latex {h'}&fg=000000$? Or the product $latex {ab}&fg=000000$ of these powers? Or:

Can an efficient random procedure create a small subset $latex {A'}&fg=000000$ of $latex {A}&fg=000000$ that includes $latex {g^{ab}}&fg=000000$ with non-negligible probability, given only $latex {g^a}&fg=000000$ and $latex {g^b}&fg=000000$ (and $latex {g}&fg=000000$ and $latex {p}&fg=000000$)?

A `no' answer is called the computational Diffie-Hellman assumption (CDH) (for polynomial-size listing). The stronger assertion that provided $latex {g^a}&fg=000000$ and $latex {g^b}&fg=000000$ are randomized, no efficient sampler has more than negligible probability of distinguishing $latex {(g^a,g^b,g^{ab})}&fg=000000$ from $latex {(g^a,g^b,f)}&fg=000000$ with a random $latex {f}&fg=000000$, is the decision version (DDH). Both versions underscore how $latex {A}&fg=000000$ is an exponential-sized haystack in which to narrow down or tell apart the particular needle $latex {g^{ab}}&fg=000000$.

Should our Bombe crew give up? All of this rests on the presumed hardness of computing $latex {a}&fg=000000$ such that $latex {g^a = h}&fg=000000$ given $latex {h}&fg=000000$ and $latex {g}&fg=000000$ (and $latex {p}&fg=000000$ or some other specifier of $latex {A}&fg=000000$). This is just the discrete logarithm problem. We have blogged several times before about advances on discrete log, both classical and quantum, and recently about the whole foundation. Most to the point, it is no longer true that ``no more ingenious algebra can help''---maybe, especially since CDH and DDH might be considerably easier than discrete log---there are tricks they could try that work in many cases. This brings us to our punchline.

Longevity?

Let's say someone builds a quantum computer that scales up well enough so that Peter Shor's algorithm makes a practical dent in factoring and discrete log. There might still be some floor $latex {m}&fg=000000$ of physical effort and energy expense, not prohibitive but not trivial. Or perhaps some classical methods employing clever randomized approximations to yield exact results after sufficiently many trials will be found, with a similar expense $latex {m}&fg=000000$.

Despite our posts wondering ``is cryptography dead?'' it perhaps wouldn't be dead. It might still be ``Merkleizable.'' We wrote the above descriptions in a way to make it easier to imagine how this might go.

Merkle also developed a scheme for secure digital signatures. Insofar as it needs only the existence of secure one-way hash functions,

{}[its advantage] is that it is believed to be resistant against quantum computer algorithms.

What we are saying is that both RSA and Diffie-Hellman operate within a closed box of possibilities, since no one has found competitively efficient realizations that aren't limited by factoring and discrete log. Whereas only something drastic like $latex {\mathsf{P = NP}}&fg=000000$ with real efficiency might close the lid on the possibility of developing secure one-way hash functions, and Merkle's puzzle scheme has open sky. Advances in computing efficiency and scale only help the latter's outlook: if you previously relied on $latex {Cmn \gg m+n}&fg=000000$ and now can do $latex {D(m+n)}&fg=000000$ work in the same time to implement the scheme, now that is compared to $latex {CD^2 mn}&fg=000000$ giving you a better ratio

$latex \displaystyle \frac{CD^2 mn}{D(m+n)} \approx CDn \quad\text{versus the previous ratio}\quad \frac{Cmn}{m+n} \approx Cn &fg=000000$

Open Problems

What do you think should be the answers to the various ``Merkle Puzzles'' posed here?

Footnote: The official release says in its second sentence, ``The ability for two parties to communicate privately over a secure channel is fundamental for billions of people around the world.'' It strikes us that this should read ``...privately over an insecure channel...'' We noticed and reported this on Saturday.