Hacker News new | past | comments | ask | show | jobs | submit login
Diffie and Hellman Win Turing Award (nytimes.com)
1272 points by matt_d on Mar 1, 2016 | hide | past | web | favorite | 78 comments



For a couple years I had an office across the hall from Diffie at Sun Labs and spent many a Friday evening Sun Labs Bash chatting with him about various topics of all kinds. Diffie is a kind and gracious man, well versed on a broad range of topics, a lot of fun, and well, a better dresser than I. Congrats to him and Martin Hellman!


History may have been different if you'd been comparable dressers... Interesting to read things from contemporaries of famous computer scientists


Ha ha not really sure you can describe Ben Titzer as a contemporary of Whitfield Diffie. Not really the same age range.


In a couple of hundred years, why not? :)


Interesting story about Diffie testifying at the Newegg trial.

http://arstechnica.com/tech-policy/2013/11/newegg-trial-cryp...


"We've heard a good bit in this courtroom about public key encryption," said Albright. "Are you familiar with that?"

"Yes, I am," said Diffie, in what surely qualified as the biggest understatement of the trial.

"And how is it that you're familiar with public key encryption?"

"I invented it."


Here's another interesting bit:

Then Fenster dropped this bombshell: "Dr. Diffie, you were not the first to invent public key cryptography, were you?"

"I believe that I may have been," said Diffie, speaking cautiously. "But perhaps you could be more specific?"

"In fact, a gentleman named James Ellis in England invented it before you, right?"

Diffie sighed. He seemed, suddenly, almost tired. He had heard this one before. "I spent a lot of time talking to James Ellis, and I can't figure it out," he said. "James Ellis did very fine work."


I don't get it. Care to explain?


Public-key encryption was supposedly invented at GCHQ by James Ellis, Clifford Cocks and Malcolm Williamson in 1975, one year before Diffie and Hellman published their paper. The work had to be kept secret though, so they never published it.


This is just like the thing between Newton and Leibniz on who invented calculus. https://en.wikipedia.org/wiki/Leibniz–Newton_calculus_contro...


As far as I'm concerned, that's the price one pays for doing research in secret.


That's a pretty biting take on the matter. Who first taught you to hate your country?


"Hate my country?" What kind of nonsense is that?


What's the "I can't figure it out" part mean?


1973.

Why the "supposedly"?


My guess is that if it was not published at the time of discovery, there's no way to know for sure whether Ellis actually invented it before Diffie and Hellman.


The irony is that such a scheme for publicly disclosing proof you have a piece of data without immediately publishing the data requires public key cryptography and digital signatures to be public knowledge. [0]

[0] https://en.wikipedia.org/wiki/Zero-knowledge_proof


Ellis conceived of practical public-key crypto PRIOR to Diffie but it was classified at GCHQ. Diffie wanted to know how Ellis invented it after he had heard this was the case.


Ellis was working at GCHQ and couldn't openly talk about his work.


stephen levy's book 'crypto' is pretty nice which can give you a sort of 'fly-on-the-wall' view of the whole thing :)


So the public key encryption equivalent of referring to TBL as "Web Developer" :)


epic :-)


Yeah, that was the first thing that came to mind when I saw this title :)


Holy damn that must have felt good haha.


Don't miss the followup: Newegg still lost.


Did they? http://arstechnica.com/tech-policy/2015/07/newegg-wins-tqp-p...

Jul 16, 2015

"Two weeks after online retailer Newegg filed a petition complaining about "excessive and unreasonable" delays in getting a final judgment in its patent case, the judge in that case has handed Newegg a big win."


Yes: http://arstechnica.com/tech-policy/2013/11/jury-newegg-infri...

But I guess I missed the followup-followup and they won in the end, that's awesome!


I think it's clear that this is very uncoincidentally an extremely timely award. The average person may have no idea, but we are in the middle of a cryptowar[1].

[1] http://reason.com/archives/2013/03/12/the-second-great-crypt...


Yeah. Individual achievement aside (and I'm not minimizing it in any way, shape or form), I'm pretty sure this is the CS profession's way of telling the FBI to get bent.


As much as I like to believe your theory, I suspect that a big award like this probably has a longer lead time than the recent Apple/FBI brouhaha.


The current Apple/FBI business is just the latest flare up in conflict that started when Apple started encrypting phones by default.


The conflict started way before that.

My reference is to when encryption was considered munitions and a bunch of people printed, shipped and scanned source code to get around the rules.


I wonder if the timing is coincident with potentially a 2nd Clinton coming to the whitehouse?


Nice!


Both gave speeches about the history of their research:

https://www.youtube.com/watch?v=zTGqP0nxX08

https://www.youtube.com/watch?v=1BJuuUxCaaY

Merkle had a huge influence also: https://en.wikipedia.org/wiki/Ralph_Merkle


Huge influence? It's his paper, his invention and this price without him is again a huge fuckup. But he should be used to that in the meantime.


certainly don't disagree. An acquaintance of mine has trying to get him work on Cryptocurrencies where Merkle trees are all around. he showed some interest and was very open to new ideas. he has a nice website http://www.merkle.com/

http://www.merkle.com/1974/RejectionLetter.pdf

"I had failed to provide any references to the prior work on public key cryptography, and the reasons previous workers in the field had rejected it as impossible. I should have looked up "public key cryptography" on Google before submitting my paper. My defense is feeble: there was no Google, the term "public key cryptography" did not yet exist, and there were no previous workers in the field. There were no words for what I had done, and looking up a concept to show that no one had previously thought of it is difficult. This is not a unique problem: it illustrates a problem faced by anyone trying to explain a new idea to an "expert" who expects a properly referenced article anytime anyone tries to explain something to them. The more a new idea is unrelated to any prior idea or concept the more it must appear as a squawling bastard, naked and alone, appearing de novo and lacking any respectable pedigree or family to vouch for its acceptability."


Any advice on what paper of theirs to read in celebration of the event? Something approachable.

When Lamport got his in 2013 I took the time to read "Time, Clocks, and the Ordering of Events in a Distributed System" [1]. Been sleeping under the rock since then.

[1] http://www.ics.uci.edu/~cs230/reading/time.pdf


Diffie and Hellman's 1976 paper, "New Directions in Cryptography"[1], cited by their Turing Award, seems like a good start.

[1] https://www-ee.stanford.edu/~hellman/publications/24.pdf


Also relevant: Whitfield Diffie's 1988 paper, "The First Ten Years of Public-Key Cryptography"[1].

[1] https://cr.yp.to/bib/1988/diffie.pdf


I attended the panel today when this was announced, and regarding the omission of Ralph Merkle, both recipients explicitly acknowledged him by name. Diffie specifically said that they built upon his prior work.

It also occurred to me that Moxie Marlinspike was in the unusual position of being the only one on the panel of five not to have (yet!) received a Turing Award. (He came off very well nonetheless.)

(In addition to Diffie and Hellman, the other two Turing-awarded panelists were Ron Rivest and Adi Shamir.)


I'm a big fan of Moxie's work, but would you mind elaborating on for which work he'd receive a Turing award? I'm not familiar with their eligibility standards. Thanks!


It's like the Nobel Prize of computer science. It's generally given to academics rather than practitioners, for deep theoretical contributions. But not always.

In any case, I didn't mean to imply that Moxie should receive a Turing Award. I just thought it was remarkable that 80% of the panel was Turing Award winners -- but only officially as of the beginning of the panel!


I used to wrongly think you need a PhD to be able to win a Turing. Diffe proved me wrong. He serves as an inspiration to anyone who mentally feels inferior to PhDs when it comes to making significant contributions to the field of Computer Science


I originally wanted to do a PhD because of the feeling smart aspect; but actuall, after I had started it (actually during the middle) I had a realisation that the people doing PhDs weren't necessarily smart; but rather they were either highly passionate about what they were doing or really enjoyed doing research.

As it happens I have probably created more outside of doing my PhD than in it; and whenever I was advising people on whether to do a PhD or not, would strongly suggest that they didn't. (The ones that ignored that advice and pressed on were exactly the type of people who could keep up the slog of doing it.)

Lots of people don't make it to the end and the going gets really tough towards the end, particularly when you are writing up and especially problematic if you have a young family. There's only so much time you can burn the candle at both ends.

So don't worry about not having a PhD; in fact, I'd argue that some of my undergraduate friends went on to much bigger and better things than I primarily because they got into the industry much earlier and therefore worked their way up.

Plus creating a startup now is so much easier than it used to be - if you see a business need that's not being satisfied, go for it. Most startups success is entirely down to chance and not educational background in any case.


You absolutely shouldn't feel "mentally inferior" to folks with PhDs. Doing academic research, which probably involves getting a PhD, is almost certainly the best way to make a significant contribution to Computer Science. These two facts aren't really in conflict, I don't think.


Not at all, and I'm skeptical any PhD (myself included) would ever say otherwise.


The very first Turing award went to Robert Floyd... he also didn't have a PhD.

Most people with PhDs are probably pretty smart. But most smart people don't have PhDs.


I thought the first one was Alan Perlis?


You're right -- he was. I'm not sure why I thought Floyd won the first one. But Floyd did win it, without a PhD. :-)


Yes, good to learn about him. Like me, he got a B.A. in Liberal Arts. Unlike me, he got his at age 17!


Martin Hellman actually has a PhD, and their work together resulted in a Turing Award.


Martin Hellman explains what he plans to do with his share of the Turing Award money:

https://nuclearrisk.wordpress.com/2016/03/01/the-turing-awar...


A noble cause. Reminding the world we have tens of thousands of nukes ready to hit every major city at any time. I wish people were more conscious of that.


Poor Ralph Merkle. Diffie and Hellman always seem to have gone out of their way to acknowledge his contribution to public key encryption, but it looks like the ACM overlooked it.


ACM did at least acknowledge Merkle in 1996, along with Adleman, Diffie, Hellman, Rivest, and Shamir, in the inaugural Paris Kanellakis Award[1].

Merkle has an article on his website about the history of his public-key cryptography work[2].

[1] http://awards.acm.org/award_winners/merkle_4605383.cfm

[2] http://www.merkle.com/1974/


I just found these free-to-watch episodes on crypto, featuring interviews with Diffie and Hellman: http://simonsingh.net/media/online-videos/cryptography/the-s...

This is by Simon Singh, who wrote the excellent book "The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography", including a chapter on Diffie–Hellman–Merkle key exchange.


The very short interview with Clifford Cocks is good too.

https://www.youtube.com/watch?v=nwNv0b-2AcU

https://www.youtube.com/watch?v=a-xEiOvXux4

"...I'm allowed to think about things outside work, but not allowed to put anything down on paper"


It speaks to how exclusive an award this is that these guys hadn't won it already. It's hard to think of achievements in computing that are as important or influential as public-key cryptography.


The ACM announcement: http://amturing.acm.org/award_winners/diffie_8371646.cfm

Marty and Whit deserve kudos for their important work in cryptography.


Seems like a good place to link this awesome panel from Defcon 19 with Whitfield Diffie and Moxie Marlinspike on SSL/PKI/etc https://www.youtube.com/watch?v=lt7uW6vDk00

Some of the Q&A is pretty weird


Since the article doesn't quote Martin Hellman here's sons of his words on cryptography (from an interview after receiving a different award): http://news.stanford.edu/news/2011/march/inventor-prize-hell...


Is it usual practice for a Turing Award to be awarded so long after the work in question?


Yes. See past recipients at https://en.wikipedia.org/wiki/Turing_Award . Almost all of them are for fundamental work that everyone builds on, and seeing that relies on the benefit of years or decades of hindsight.


It seems the trend has been towards later and later recognition, which makes sense given the age of the field and the award.

- Knuth got his for TAOCP in 1976, 8 years after first publication.

- Thompson and Ritchie got theirs for UNIX in 1983, 10 or so years after its introduction.

- Englebart got his for his HCI work in 1997, 30 or so years after the fundamental work was done (but just after its universal adoption)

- Alan Kay got his for OOP & Smalltalk in 2003, 20+ years after the first stable release.

- Cert & Kahn got theirs for TCP/IP in 2005, 20+ years on.

And so forth.


I think that's probable a good way to do it. Some things that gain great traction at one time may later turn out to have been just a sparkle, or a fad. Standing the test of time is a good litmus test for the importance of scientific achievements.


Nobel Prizes, at least in the science fields, follow the same pattern. I suspect that at least in part the Nobel committee wants to avoid awarding for something unproven such as cold fusion.

The committees in the humanities seem much less concerned about this, and are able to award much sooner.


This was on the BBC last night:

http://www.bbc.co.uk/programmes/p03l61pn


Surprising it took this long. (Especially since, for example, RS and A have had Turing awards for more than a decade)


tl;dr version of the 2016 ACM Turing Award:

((g^a) mod p)^b mod p = (g^ab) mod p = ((g^b) mod p)^a mod p

-- The beauty of math.


This skips the most important part of the proof which explains why this is not easily invertible without the secret key.


What is this part? Isn't it just by assumption? (also, by secret key, I'm guessing you mean 'a', 'b')


Why was Merkle not included?


yayy!! This is just great! Congrats to Martin and Hellman.

Why it takes such long time for Computer Scientist to achieve such Award. DH Algo has been well known for long time. On the other hand Physicists(Theoretical, Astro, ...) dont have to wait too long to gain such recognition.


Martin (sic) Hellman is one person. His co-awardee is Whitfield Diffie.


>Congrats to Martin and Hellman.

:)


just curious, is anyone wondering why ralph-merkle is not here as well ?


Finally, took long enough.




Registration is open for Startup School 2019. Classes start July 22nd.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: