A Matter of Agreement
On the 2015 Turing Award
|Mirror image of source|
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 Dick and I 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 that was used for every one of the Germans’ Enigma machines that day. Having the same machines in their possession did not solve the problem. The movie shows how inferring some of the plaintext cut down the space of possibilities enough for their “Bombe” decoding machines to reduce the cracking time to some number of minutes.
Suppose the Germans had instead behaved this way: Randomly select initial states each morning, where is fairly large but not prohibitive. Don’t send those states but rather encrypt messages as ciphertexts , where uses key , as “puzzles” of the kind that one’s own people at each field point can break in minutes. To make it easier for one’s own people, the can contain exposed plaintext to make them easier to crack—so deliberately doing the kind of mistake the movie says “won the war” for the Allies. Each field point chooses one at random, breaks it in minutes to get , and sends a key-dependent response back to HQ over the open channels. It is important that does not simply reveal or , but HQ can tell which of it belongs to by its prior knowledge. Then HQ and that field point can communicate using .
Now picture the poor people at Bletchley Park. They have time to crack any one key , but there is less than a chance that is even used. If they crack some number of them, they need to expect to get even one that is used. Together with the intercepted they can verify that is being used, but that’s good for only one field point—it doesn’t compromise the whole military command. Worst, if there is a field point that they particularly desire to crack, their chance of getting its key is bounded by . They would need upwards of Bombes to compromise most of the enemy or hit a particular field station, but that’s times as many cracking aids as the enemy needs to deploy.
Even if two or more field stations “collide” by having chosen the same —as is likely by the “birthday paradox” when —this doesn’t improve Bletchley’s expectation. Only by spending order-of 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 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 to crack versus 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 Key Agreement
Enter Diffie and Hellman. The idea is amazingly simple. Take any cyclic group for which we can find a generator . The bellwether instance is being the multiplicative group modulo an -bit prime but it could be anything. We need to be large in terms of but powering for to be computable in time that is a small polynomial in . All participants know and (or ) in advance, and these may be publicly known. The protocol goes as follows:
- HQ privately selects a private integer , forms , and sends over an open channel to a field station.
- The field station simultaneously selects its own , forms , and sends to HQ.
- HQ forms and knows that the field station will get the same value via .
- The parties then communicate using the initial state .
This scheme can easily be replicated for field stations. HQ should choose a different private for each station (which in turn uses its own ) but it is OK to use the same and . Alternatively, three parties can make a communications triangle by respectively choosing their own and sharing and so on. But all this is jumping ahead—let’s just consider with two parties.
Picture our Bletchley Park people now. They can read and besides knowing and (that is, ). The question is, can they infer the powers of that make and ? Or the product of these powers? Or:
Can an efficient random procedure create a small subset of that includes with non-negligible probability, given only and (and and )?
A ‘no’ answer is called the computational Diffie-Hellman assumption (CDH) (for a polynomial-size listing). The stronger assertion that provided and are randomized, no efficient sampler has more than negligible probability of distinguishing from with a random , is the decision version (DDH). Both versions underscore how is an exponential-sized haystack in which to narrow down or tell apart the particular needle .
Should our Bombe crew give up? All of this rests on the presumed hardness of computing such that given and (and or some other specifier of ). 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.
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 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 .
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 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 and now can do work in the same time to implement the scheme, now that is compared to giving you a better ratio
that you had before. So the future may only bode better for Ralph’s work, along lines of this recent appreciation—while we must gratefully admit that the present would be inconceivable without the realization of Diffie-Hellman and RSA.
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…” After all, Merkle’s paper was titled that way. We noticed and reported this on Saturday. Update (3/8/16): Today the ACM office changed it to read:
The ability for two parties to use encryption to communicate privately over an otherwise insecure channel is fundamental for billions of people around the world.