Skip to content

A Matter of Agreement

March 7, 2016


On the 2015 Turing Award

hamming_vt_newsFlipped
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 {s} that was used for every one of the Germans’ {n} 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 {m} of minutes.

Suppose the Germans had instead behaved this way: Randomly select {Cn} initial states {s_i} each morning, where {C} is fairly large but not prohibitive. Don’t send those states but rather encrypt {Cn} messages {m_i} as ciphertexts {t_i}, where {t_i} uses key {s_i}, as “puzzles” of the kind that one’s own people at each field point can break in {m} minutes. To make it easier for one’s own people, the {t_i} 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 {t_j} at random, breaks it in {m} minutes to get {s_j}, and sends a key-dependent response {r_j} back to HQ over the open channels. It is important that {r_j} does not simply reveal {m_j} or {s_j}, but HQ can tell which of {s_1,\dots,s_{Cn}} it belongs to by its prior knowledge. Then HQ and that field point can communicate using {s_j}.

Now picture the poor people at Bletchley Park. They have time to crack any one key {s_k}, but there is less than a {1/C} chance that {s_k} is even used. If they crack some number {d} of them, they need {d \approx C} to expect to get even one {s_j} that is used. Together with the intercepted {r_j} they can verify that {s_j} 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 {d/Cn}. They would need upwards of {Cn} Bombes to compromise most of the enemy or hit a particular field station, but that’s {C} times as many cracking aids as the enemy needs to deploy.

Even if two or more field stations “collide” by having chosen the same {t_j}—as is likely by the “birthday paradox” when {C = o(n)}—this doesn’t improve Bletchley’s expectation. Only by spending order-of {mCn} 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 {mCn} 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 {O(mnC)} to crack versus {O(nC + m)} 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 {A} for which we can find a generator {g}. The bellwether instance is {A} being the multiplicative group modulo an {n}-bit prime {p} but it could be anything. We need {|A|} to be large in terms of {n} but powering {g^a} for {a < |A|} to be computable in time that is a small polynomial in {n}. All participants know {g} and {A} (or {p}) in advance, and these may be publicly known. The protocol goes as follows:

  • HQ privately selects a private integer {a}, forms {h = g^a}, and sends {h} over an open channel to a field station.

  • The field station simultaneously selects its own {b}, forms {h' = g^b}, and sends {h'} to HQ.

  • HQ forms {s = h'^a = g^{ba}} and knows that the field station will get the same value via {s = h^b = g^{ab}}.

  • The parties then communicate using the initial state {s}.

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

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

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

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

Should our Bombe crew give up? All of this rests on the presumed hardness of computing {a} such that {g^a = h} given {h} and {g} (and {p} or some other specifier of {A}). 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 {m} 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 {m}.

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 {\mathsf{P = NP}} 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 {Cmn \gg m+n} and now can do {D(m+n)} work in the same time to implement the scheme, now that is compared to {CD^2 mn} giving you a better ratio

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

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.

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…” 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.

13 Comments leave one →
  1. BusyBeaver permalink
    March 7, 2016 4:26 pm

    The Turing Award is more geared to multiple fundamental contributions.

    I don’t think so. Here’s a direct quote from the ACM call for nominations:

    “Although the long-term influences of the nominee’s work are taken into consideration, there should be a particular outstanding and trend-setting technical achievement that constitutes the principal claim to the award.”

    • March 7, 2016 5:52 pm

      On the other hand, in the description here it says, “It is given to an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the computer field.” The last 6 citations begin “For fundamental contributions…” or words to that effect, followed mostly by to-an-area or by multiple items.

      Added later: The drift of the paragraph is that even if you regard this Turing Award as being for the main achievement, it is still significant that Merkle is on the patent for it. Dick and I (Ken) discussed all this on Saturday, hence the joint-handle answer.

      • BusyBeaver permalink
        March 8, 2016 8:52 am

        I’ve been minorly involved with two candidate dossiers, as an informal referee of sorts. In one of the two cases I was told of the specific main contribution the candidate was ultimately evaluated on. The candidate won and the citation mentions his main contribution prominently though it also mentions some other important work. Indeed, one would be hard pressed to deduce from the text alone which one of those contributions was primus inter pares.

        I don’t know why the discrepancy between the call for nominations and the citation, nor do I know if the practice of identifying the main contribution at evaluation time has carried across evaluation committees to the present time.

  2. March 7, 2016 8:47 pm

    asymmetric encryption is one of the great modern achievements/ wonders of complexity theory and has strong connections to key open areas such as the P vs NP problem (they were both formulated at nearly exactly the same time), existence of trapdoor functions, average case complexity etc.; virtually all online payment systems would be impossible without it; also its had major implications in cyberpolitics/ libertarianism; its highly intrinsic to the emerging Bitcoin system; national security and the NSA are highly tied up in its history. an entire book could easily be written on the subject, not sure of the best ref on it so far (does anyone know a good one?). you make no mention of key fact that NSA cryptographers claim they invented asymmetric crypto shortly before academic ones and this factoid was declassified awhile back (no complaint here, understand this is a free blog page).

    and the “elephant in the room”: its interesting synchronicity that there is now a massive case involving Apple with huge implications on law and technology, with many top silicon valley companies now weighing in with amicus briefs in the case; cook CEO of apple says he will argue it all the way to the supreme court. hope the supreme court does agree to take the case AND find a constitutional right to encryption based on freedom from illegal search and seizure and freedom of speech basis. not an expert but afaik public key crypto plays a key role in the apple security (would like to see a careful analysis of that by someone). more on apple/ silicon valley/ privacy rights vs FBI

    • March 7, 2016 9:11 pm

      VZN, when you say “NSA cryptographers…shortly before…” are you saying this is besides the GCHQ cryptographers who invented it shortly before the academic ones—whom this post names?

      • March 7, 2016 9:28 pm

        hi KWR sorry missed your brief ref to the GCHQ in the post 1st scan, that is most of what was referring to. am not an expert on this but my memory was that the NSA possibly was (“asserted to be”) involved in the public key crypto discovery other than the GCHQ. might try to write up all this in a blog sometime but it would be tricky (the refs seem to be quite scattered, hence my asking if anyone knows of definitive books that ideally incorporate the late-revealed GCHQ/ NSA angles). afaik there is some question whether the GCHQ shared this discovery with NSA at the time. they have classified material-sharing agreements in modern times but dont know how many decades back those go. here are some claims that maybe the NSA was early in the discovery also.

        https://www.cs.columbia.edu/~smb/nsam-160/

        obviously this is all highly complicated by the fact that these discoveries were classified secrets of high national security at the time, and for decades after. which opens up a lot of questions about the legitimacy of such classifications, and speculation of whether the NSA/ GCHQ are possibly aware of other groundbreaking discoveries in computational complexity/ cryptography that are as-yet-unclassified. and what does it mean to give awards for these discoveries to academics when possibly unheralded govt employees deserve some of the credit? (reminds me of the “simultaneous” discovery of P vs NP by Cook/ Levin.) also forgot to note, there is recent news of an experiment demonstrating “scalable qubits for factoring” that is highly related to this topic also.

        http://news.mit.edu/2016/quantum-computer-end-encryption-schemes-0303

        my feeling is this is a bit overhyped in the terminology with only 5 qubits/ atoms as so-called “scalable” but agree its an important advance.

      • March 7, 2016 11:45 pm

        Thanks for clarifying. We decided to leave the MIT quantum link on the cutting-room floor along with some others. For awhile we’ve intended to do a post on how earlier Shor implementations cut corners, in a way this one does not, as well as ones on the broader issues with D-Wave. We do try to keep most posts to within 5 “quarto-size” LaTeX pages, which this one fit exactly minus the footnote (any reaction on it?); originally it was going to be shorter but I cooked up the “Imitation” description of Merkle’s Puzzles…

      • March 8, 2016 2:13 pm

        public key crypto converts insecure “channels” into secure ones, so to speak, right? a not-elementary concept/ distinction that might easily be lost in popsci writing eh? even the word “channel” seems kind of old/ dated these days and a better modern phrase might be “communication link”… etc

  3. March 8, 2016 1:17 am

    I think that “The ability for two parties to communicate privately over a secure channel” can be interpreted in the correct way. It is the Diffie-Hellman protocol that creates the secure channel and thus gives privacy. While I like your modification, it might confuse more people than the original. Maybe I would go for something like “over a channel that they can make secure themself” but this makes the sentence too complicated.

    • March 8, 2016 2:13 pm

      Wikipedia’s segue from a paragraph with “insecure” to a paragraph with Diffie-Hellman can also be read both ways. I (Ken) was going to suggest saying “unsecured channel” or “open channel”, but ACM today reworded it to something using “insecure” but even better: “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.”

Trackbacks

  1. number theory news/ highlights: prime bias, Diffie-Hellman, Zhang-Tao, Wiles, Riemann | Turing Machine
  2. Quantum Supremacy and Complexity | Gödel's Lost Letter and P=NP
  3. The World Turned Upside Down | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s