US patent 4200770, Hellman Diffie Merkle, public-key cryptography

This patent expired in 1997.

Most patented "inventions" are obvious from the prior art. The DH system was a rare exception: it revolutionized cryptography. Does this mean the patent was beneficial? No! Look at the timeline:

• Summer 1975: Merkle submitted a paper "Secure communications over insecure channels" describing a public-key system (the puzzles system), making no effort to patent it. See 1995 interview and copies of documents.
• December 1975: Diffie and Hellman, independently of Merkle, distributed a paper "Multiuser cryptographic techniques" describing various public-key systems (e.g., the permuted-circuit system), making no effort to patent these systems. See the paper from the June 1976 National Computer Conference, and a 1988 history from Diffie saying (page 562) "We wrote the paper in December 1975 and sent preprints around immediately".
• May/June 1976: Diffie and Hellman distributed a paper "New directions in cryptography" describing the DH modular-exponentiation key-exchange system, making no effort to patent this system. See 1988 history from Diffie: (page 562) exponentiation was suggested as a one-way function by John Gill; (page 562) Hellman "eventually made the breakthrough early one morning in May 1976"; (page 563) Diffie and Hellman "hastened to add it to both the upcoming National Computer Conference presentation and to 'New Directions'. The latter now contained a solution to each aspect of the public-key problem, though not the combined solution I had envisioned. It was sent off to the IEEE Transactions on Information Theory prior to my departure for NCC and like all of our other papers was immediately circulated in preprint".
• June 1976: Diffie and Hellman presented the DH modular-exponentiation key-exchange system at the National Computer Conference in Massachusetts and at another conference in Sweden. Levy's 2001 book Crypto, which is based on "a series of personal interviews", says (fifth page before the end of the "public key" chapter) that at this time "thoughts about exploiting intellectual property were the furthest thing from the minds of these information scientists. In contrast to what struck them as a government refusal to provide all the details of the Data Encryption Standard, they were creating a fully open alternative to conventional cryptography itself".
• September 1977: Stanford, evidently realizing that it could make money from this, filed patent 4200770.

The patent was granted in 1980. Robert B. Fougner from "Public Key Partners" claimed that "all known methods of practicing the art of Public Key" were covered by this and followup patents. The patent itself claims the entire concept of public-key encryption (see claim 1), along with the DH modular-exponentiation key-exchange system in particular (see claim 6).

Under United States case law, a document has been published if it "has been disseminated or otherwise made available to the extent that persons interested and ordinarily skilled in the subject matter or art, exercising reasonable diligence, can locate it". How does a September 1977 patent on public-key encryption avoid admitting that public-key encryption had already been introduced in the "Multiuser cryptographic techniques" paper distributed in 1975? Answer: The patent description acknowledges the "Multiuser cryptographic techniques" paper as prior art but falsely claims that the paper "presents neither proof that public key cryptosystems exist, nor a demonstration system".

How does a September 1977 patent on modular-exponentiation key exchange avoid admitting that modular-exponentiation key exchange had already been introduced in the "New directions in cryptography" paper distributed in May/June 1976? Answer: The Stanford lawyers allowed the patent office to believe that the paper was first available in November 1976. Unlike most countries, the U.S. allows patents to be filed up to a year after public disclosure.

My notes say that Mike Matyas received a copy of "New directions in cryptography" in August 1976. Several further examples of public distribution of the DH results have been documented in detail. None of this was disclosed to the patent office.

The 1985 court case MIT v. Fortia invalidated another patent because the patent holder had handed out six copies of a preprint at a conference fourteen months before applying for the patent. It should have been straightforward to kill the DH patent in court: non-disclosure of prior art is "inequitable conduct" invalidating the whole patent, and, more to the point, the modular-exponentiation key-exchange system that people wanted to use was already stated in the prior art.

The fact that there was direct prior art for the DH patent appears to have been first pointed out as part of the complaint in a 1994 court case Schlafly v. Public Key Partners. This was 17 years after the patent was filed, too late to be of any use. This part of the case was privately settled by the parties in March 1997, presumably with the patent holder promising not to enforce the patent against Schlafly for the remaining 6 months before the patent expired.

To summarize, all available evidence is that Merkle, Diffie, and Hellman were distributing their work for free, driven by the usual academic publication incentives, and that they filed this patent only as an afterthought.