The Key to Privacy

It was unusual for Martin Hellman, a professor of electrical engineering at Stanford University, to present two papers on cryptography at the International Symposium on Information Theory in October 1977. Under normal circumstances, Steve Pohlig or Ralph Merkle, the doctoral students who also had worked on the papers, would have given the talks, but on the advice of Stanford’s general counsel, it was Hellman who spoke.

The reason for the caution was that an employee of the U.S. National Security Agency, J.A. Meyer, had claimed publicly discussing their new approach to encryption would violate U.S. law prohibiting the export of weapons to other countries. Stanford’s lawyer did not agree with that interpretation of the law, but told Hellman it would be easier for him to defend a Stanford employee than it would be to defend graduate students, so he recommended Hellman give the talk instead.

Whitfield Diffie, another student of Hellman’s who says he was a hippie with “much more anti-societal views then,” had not been scheduled to present a paper at the conference, but came up with one specifically to thumb his nose at the government’s claims. “This was just absolute nonsense, that you could have laws that could affect free speech,” Diffie says. “It was very important to defy them.”

In the end, no one was charged with breaking any laws, though as Hellman, now professor emeritus, recalls, “there was a time there when it was pretty dicey.” Instead, the researchers’ work started to move the field of cryptography into academia and the commercial world, where the cutting edge had belonged almost exclusively to government researchers doing classified work.

Diffie and Hellman wrote a paper in 1976, “New Directions in Cryptography,” introducing public key cryptography that still prevails in secure online transactions today. As a result, they have been named the 2015 recipients of the ACM A.M. Turing Award.

The researchers’ work started to move the field of cryptography into the realm of academia and the commercial world.

Public key cryptography arose as the solution to two problems, says Diffie, former vice president and chief security officer at Sun Microsystems. One was the problem of sharing cryptographic keys. It was possible to encrypt a message, but for the recipient to decrypt it, he would need the secret key with which it was encrypted. The sender could physically deliver the secret key by courier or registered mail, but with millions of messages, that quickly becomes unwieldy. Another possibility would be to have a central repository of keys and distribute them as needed. That is still difficult, and not entirely satisfactory, Diffie says. “I was so countercultural that I didn’t regard a call as secure if some third party knew the key.”

Meanwhile, Diffie’s former boss, John McCarthy, a pioneer in the field of artificial intelligence, had written about future computer systems in which people could use home terminals to buy and sell things; that would require digital signatures that could not be copied, in order to authenticate the transactions.

Both problems were solved with the idea of a public key. It is possible to generate a pair of complementary cryptographic keys. A person who wants to receive a message generates the pair and makes one public; then a sender can use that public key to encrypt a message, but only the person with the private key, which does not have to be sent anywhere, can decrypt it.

Hellman compares it to a box with two combination locks, one to lock the box and the other to unlock it. Alice, the sender, and Bob, the receiver, each generate a pair of keys and make one public. Alice puts a message in the “box,” then locks it with her secret key, guaranteeing its authenticity since only she knows how to do that. She then places that locked box inside a larger one, which she locks with Bob’s public key. When Bob gets the box, he uses his private key to get past the outer box, and Alice’s public key to open the inner box and see the message.

Hellman and Diffie, building on an approach developed by Merkle, later came up with a variation on the scheme now called the Diffie-Hellman Key Exchange (though Hellman argues Merkle’s name should be on it as well). In this version, the box has a hasp big enough for two locks. Alice places her message in the box and locks it with a lock to which only she knows the combination, then sends it to Bob. Bob cannot open it, nor can anyone who intercepts it en route, but he adds his own lock and sends it back. Alice then takes off her lock and sends the box back to Bob with only his lock securing it. On arrival, he can open it. In the Internet world, that translates to a commutative one-way function that allows Alice and Bob to create a common key in a fraction of a second. While an eavesdropper, in theory, could compute the same key from what he hears, that would take millions of years.

“Cryptography has really blossomed since the publication of their paper. It’s become the key tool of the information age.”

Ron Rivest, an Institute Professor in the Massachusetts Institute of Technology’s Computer Science and Artificial Intelligence Laboratory, calls the duo’s impact on the field revolutionary. “Cryptography has really blossomed since the publication of their paper,” he says. “It’s become a key tool of the information age.” Rivest, with his colleagues Adi Shamir and Leonard Adleman, developed the first practical implementation of public key encryption, stimulated, Rivest says, by Diffie and Hellman’s paper. Rivest, Shamir, and Adleman were awarded the ACM A.M. Turing Award for that work in 2002.

The Turing Award carries a $1 million prize, which Diffie and Hellmann will split. Diffie says he plans to use his half of the award to pursue research on the history of cryptography. Hellman and his wife, Dorothie, will use the money, and the attendant publicity, to bring attention to their forthcoming book about how they transformed an almost-failed marriage into one in which they have reclaimed the love they felt when they first met, and how that same approach can be used to rescue the world from the risk posed by nuclear weapons.

If young people want to go into the field of cryptography, there are three great problems for them to tackle, Diffie says: cryptography resistant to quantum computing; proof of the computational complexity of cryptosystems; and homomorphic encryption that would allow computations to be carried out on encrypted data.

Hellman encourages people to take risks and not wait to know everything they think they should know before launching a project. “When I first started working in cryptography, my colleagues all told me I was crazy,” he says. “My advice, is don’t worry about doing something foolish.”