New Directions in Cryptography — Sharing a Secret Without Delivering a Key

In November 1976, volume IT-22, number 6 of IEEE Transactions on Information Theory carried an invited paper by Whitfield Diffie and Martin Hellman, pages 644 to 654, titled "New Directions in Cryptography". Its opening sentence is unusually direct for a journal article: "We stand today on the brink of a revolution in cryptography."

The manuscript was received on 3 June 1976. Parts of the work had already been presented — at the IEEE Information Theory Workshop in Lenox, Massachusetts, in June 1975, and at the IEEE International Symposium on Information Theory in Ronneby, Sweden, in June 1976.

The Two Problems

The paper named two obstacles.

Key distribution. Cryptography until then assumed sender and receiver already held the same key. That meant the key had to arrive in advance over a separate secure channel — a courier, registered mail, a trusted hand. But businesses transact with parties they have never met. Once the network is global, that assumption converts directly into cost and delay.

Authentication. A paper contract is made binding by a signature, and a signature has a specific property: the holder can produce it to a third party, in court. If electronic dealing is to replace paper, something has to play that role.

What It Introduced, and What It Did Not

This is the part most often garbled.

And what it did not deliver: a working public-key cryptosystem. The paper suggests techniques for building one and says plainly that the problem remains largely open. The working system arrived the following year, when Ronald Rivest, Adi Shamir and Leonard Adleman of MIT circulated it as a technical memo in 1977 and published it in February 1978 as Communications of the ACM 21(2), 120–126 — RSA.

Put another way: of the two problems, 1976 solved key distribution. Encryption and signatures were formulated as goals. Half of what the phrase public-key cryptography now denotes was completed outside this paper.

Ralph Merkle Got There First

Reference [1] of the paper is Ralph Merkle's "Secure communication over an insecure channel," listed as submitted to CACM. Merkle, then a student at Berkeley, had conceived in 1974 the scheme now known as Merkle's Puzzles: a key agreement in which the attacker's work grows as the square of the legitimate users' work. The Diffie–Hellman paper names Merkle's approach a "public key distribution system", weighs its transmission overhead in detail, and then offers its own scheme as an improvement on precisely that ground. Merkle's paper did not appear in print until April 1978, in CACM 21(4), 294–299 — a year and a half after Diffie–Hellman.

ACM's Turing Award record notes that Diffie regarded Merkle as possibly the most inventive figure in the public-key story, and that Hellman later argued the credit should read Diffie–Hellman–Merkle. The IEEE Kobayashi Award of 1999 and the Hamming Medal of 2010 did go to all three. The 2015 ACM A.M. Turing Award went to two: Diffie and Hellman, "For inventing and promulgating both asymmetric public-key cryptography, including its application to digital signatures, and a practical cryptographic key-exchange method."

The British Government Already Knew

On 16 December 1997, CESG — GCHQ's information assurance arm — released an internal paper written in 1987 by James Ellis, "The Story of Non-Secret Encryption". Ellis had died three weeks earlier. The chronology in its reference list is precise:

• January 1970 — Ellis, "The Possibility of Secure Non-Secret Digital Encryption": an existence theorem for secure communication without a pre-shared key.
• 20 November 1973 — Clifford Cocks, "A Note on Non-Secret Encryption". Ellis writes that this is essentially the RSA algorithm.
• 21 January 1974 — Malcolm Williamson, "Non-Secret Encryption Using a Finite Field": a three-pass scheme exploiting the commutativity of exponentiation.
• 10 August 1976 — Williamson, "Thoughts on Cheaper Non-Secret Encryption", which Ellis says Williamson wrote much later than he thought of it.

That last one is Diffie–Hellman key exchange. Ellis is blunt about it: the published Diffie–Hellman method "was identical to Williamson's version, except that they restricted q to be prime." Note the dates carefully, though: Williamson's August 1976 report postdates the receipt of the Diffie–Hellman manuscript on 3 June. The secret side was earlier in conception, not in documentation.

And the secret side changed nothing. As ACM's record observes, it was the open community — Diffie, Hellman, Merkle, Rivest, Shamir, Adleman — whose work actually enlarged the possibilities for secure communication and digital authentication; the work inside GCHQ and NSA did not. The paper's own citation of Claude Shannon's 1949 theory of secrecy systems makes the same point structurally: this field accumulates only along the published lineage.

Solved Several Million Times a Second

Diffie–Hellman and RSA became the foundation of HTTPS, SSH, PGP and end-to-end encryption. On today's web the standard arrangement is elliptic-curve Diffie–Hellman (ECDHE), generating a throwaway key for every connection. The problem set out in 1976 — share a key with no secure channel to share it over — is now solved several million times a second.

And the assumptions that solution rests on, that discrete logarithms are hard and factoring is hard, do not survive a large quantum computer. That the 2025 Turing Award went to quantum key distribution is precisely an attempt to move the guarantee off those assumptions and onto a different foundation.