Path: sirius.ucs.adelaide.edu.au!berlioz.ua.oz
From: gordoni@berlioz.ua.oz (Gordon Irlam)
Newsgroups: sci.crypt,gnu.misc.discuss
Subject: Re: Hellman & Merkle patent covers everything!
Message-ID: <3398@sirius.ucs.adelaide.edu.au>
Date: 24 May 91 13:14:09 GMT
References: <14887@ulysses.att.com>
Sender: news@ucs.adelaide.edu.au
Followup-To: sci.crypt
Lines: 72
Xref: sirius.ucs.adelaide.edu.au sci.crypt:3453 gnu.misc.discuss:2639
Nntp-Posting-Host: berlioz.cs.adelaide.edu.au

From article <14887@ulysses.att.com>, by smb@ulysses.att.com (Steven Bellovin):
>
> But prior art -- no way; they invented the concept.

I wouldn't be so sure.

A patent is invalidated by any "prior art", including that of the
applicant.

In the United States,

    "a person shall be entitled to a patent unless ... the invention
    was ... described in a printed publication in this or a foreign
    country ... more than one year prior to the date of the application
    for patent"

Circumstantial evidence exists that suggests that much of the work
performed by Hellman and Merkle was performed without the possibility
of obtaining a patent being considered.

For instance the "Multi-user cryptographic techniques" paper was
published more than one year before the patent application.  And it
appears to come perilously close to constituting prior art.

Also the "New directions in cryptography" paper was published in
November 1976.  While the "Public key cryptographic apparatus and
method" patent was filed just under a year later on October 6, 1977.
The "New directions" paper discusses knapsack cryptosystems, although
it is light on a few details.  Of this paper Diffie later remarks "It
was sent of to the IEEE ... and like all of our other papers
immediately circulated for preprint." Thus assuming this circulation
occurred more than one year prior to October 6, 1977, this paper must
also come perilously close to constituting prior art.

Finally it would appear that the idea of public key cryptography was
frequently discussed with others.  For instance it was John Gill who
suggested the idea of using discrete exponentiation.  And Donald Knuth
had suggested "that multiplying a pair of primes was easy, but that
factoring the result, even when it was known to have precisely two
factors, was exceedingly hard." In both of these cases Diffie was
talking to fellow Stanford employees.  But it is quite possible that
the topic may also have been discussed with graduate students or
others.

Thus it would appear quite plausable that a technical report produced
by Stanford that deals with the notion of public key cryptography, or
some other similar document, might exist in a public library somewhere
that would constitute prior art capable of invalidating the "public
key" patent.

In addition the validity of this patent must be questioned because the
scheme described therein does not work.

The "Cryptographic apparatus and method" patent which deals with
exponential key exchange might also be able to be invalidated on
account of prior art being found.  Ralph Merkle's "puzzles" which he
invented in 1974 appear to describe exactly the same thing as
described in claim 1 of the patent filed in 1977.  Unfortunately it
appears that it wasn't until 1978 that he managed to convince someone
to publish his paper.  Whether any prior publication occurred in a
technical report from Berkeley or something similar is not clear. 

The historical evidence surrounding the public key patents does not
support the contention that the granting of the right to exclude in
such cases is necessary to promote the progress of science and the
useful arts.

Does anyone at Berkeley or Stanford want to check to see if any
technical reports have mysteriously gone missing from the library?

                                            Gordon Irlam
                                            (gordoni@cs.adelaide.edu.au)