Wednesday, March 02, 2016

Changing This Ancient Art Into a Science

The ACM announced yesterday that they will award the 2015 Turing Award to Whitfield Diffie and Martin Hellman for contributions to modern cryptography. The Turing award is the highest honor in all of computing. John Markoff in the New York Times also has the story.
Diffie and Hellman are best known for public-key cryptography, the brilliant idea that one could communicate secretly with someone you haven't communicated previously. Without public-key cryptography there would be no e-commerce. Equally important Diffie and Hellman brought computational complexity to bare, moving cryptography into its modern age. I strongly recommend reading their 1976 gem New Directions in Cryptography (PDF) particularly the introduction and chapter 6 where Diffie and Hellman connect cryptography to computational complexity and the P v NP problem itself defined only five years earlier. Here's the first paragraph:
We stand today on the brink of a revolution in cryptography. The development of cheap digital hardware has freed it from the design limitations of mechanical computing and brought the cost of high grade cryptographic devices down to where they can be used in such commercial applications as remote key cash dispensers and computer terminals. In turn, such applications create a need for new types of cryptographic systems which minimize the necessity of secure key distribution channels and supply the equivalent of a written signature. At the same time, theoretical developments in information theory and computer science show promise of providing provably secure cryptosystems, changing this ancient art into a science. 
One question for which I shall offer no opinion: Should Ralph Merkle have been a co-recipient of this award? 


  1. Many congratulations to them both on a thoroughly deserved award that has been a long time in the coming. With regard to your question, based on Hellman's comments in
    this announcement from 2010, which incidentally also shows that Merkle has been cut out of the frame in more ways than one, I would say the answer is probably yes.

    1. Not disputing this but that description of the 2010 awarding of the Hamming prize, which went to all three, is a bit misleading. It is clear that Merkle's puzzle paper (which was submitted in August 1975 and eventually after revision was published in C.ACM, not J. ACM, in 1978) had the idea of public key cryptography and public key exchange. However, it did not have a proposed incarnation for the puzzle that would work, despite the 2010 article suggesting that he did the same thing as Diffie and Hellman had done and was simply scooped by them. The idea of using the difficulty of discrete log is only in Diffie & Hellman's paper; had their specific proposal not been such a good choice, their paper might not have been quite so compelling.

      One interesting aspect of the 2010 article, though, is the copy of the full version of the picture above, from which you can see that Merkle was originally in frame to Hellman's right.