New Directions in Cryptography
Two strangers can agree on a secret in full public view — and a listener still can't share it.
How can two people who have never met shout numbers back and forth in a crowded room and walk away sharing a secret that no one else in the room can know?
The big idea
For all of history, keeping a message secret meant first sharing a key — a codebook, a password — through some safe, private channel. But if you've never met the other person, how do you share that first key safely? Diffie and Hellman found a way to skip the problem entirely.
Their trick lets two people build a shared secret key out in the open. Each person keeps one private number to themselves and announces a second number for everyone to hear. By combining their own private number with the other person's public number, both arrive at the exact same secret — yet an eavesdropper who heard every public number cannot work it out. The secret is never sent; it is grown, separately and identically, on each side.
How it came about
In the early 1970s cryptography was the private domain of governments and militaries. Whitfield Diffie, a restless young programmer, became obsessed with a civilian problem: if computers were going to talk to each other across the world, ordinary people would need to communicate securely with strangers. He found a kindred mind in Martin Hellman at Stanford, and they spent years circling the puzzle of how to share a key without a secure channel.
Their 1976 paper opens by announcing a "revolution" and then delivers one: a way to agree on a key in public. They also described, but could not yet build, two further ideas — the public key (encrypt with a key everyone knows; only the owner can decrypt) and the digital signature. A third researcher, Ralph Merkle, had reached related ideas independently. Unknown to all of them, cryptographers at Britain's secret GCHQ had quietly discovered much the same thing a few years earlier — but it stayed classified until 1997, so the public credit, and the 2015 Turing Award, went to Diffie and Hellman.
Why it mattered
This is the invention that made the internet trustworthy for ordinary use. Every time you see a padlock in your browser, buy something online, or send a private message, your device is quietly performing a version of this exchange with a server it has never met before — agreeing on a secret key in the open, in a fraction of a second, before any of your data is sent. Without it, there is no online banking, no e-commerce, no private messaging at scale.
A way to picture it
Picture mixing paint. Everyone agrees on a shared starting colour — say, yellow — out loud. Alice secretly stirs in her private colour; Bob secretly stirs in his. They swap the two mixed pots in full view. Now Alice adds her private colour to Bob's pot, and Bob adds his to Alice's — and both pots become the exact same final shade. An onlooker saw the yellow and both mixed pots, but separating a mixed colour back into its ingredients is hopelessly hard, so they can never reproduce the final shade. Numbers raised to powers behave just like that paint: easy to mix forward, practically impossible to un-mix.
Where it sits
A generation earlier, Claude Shannon had put secrecy on a mathematical footing and shown what perfect security would require. Diffie and Hellman took the next step: security you can build cheaply because some sums are easy one way and crushingly hard to reverse. Two years later RSA turned their "public key" concept into a working system, and decades on the same public-key signatures authorize transactions on Bitcoin — the Library's Nakamoto paper rests on the foundations laid here.
We stand today on the brink of a revolution in cryptography.
We propose some techniques for developing public key cryptosystems, but the problem is still largely open.
More precisely, a function f is a one-way function if, for any argument x in the domain of f, it is easy to compute the corresponding value f(x), yet, for almost all y in the range of f, it is computationally infeasible to solve the equation y = f(x) for any suitable argument x.