From: anonymous-remailer@shell.portal.com
Date: Wed, 18 Oct 95 12:30:12 PDT
To: cypherpunks@toad.com
Subject: Legal argument invalidates Merkle-Hellman
Message-ID: <199510181929.MAA15347@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


More on free public key crypto!

The Hellman-Merkle patent claims to cover the entire notion of public 
key cryptography.  The patent holders say that any scheme which has a 
private key that is computationally infeasible to derive from the public 
key infringes on the Hellman-Merkle patent.  Here is a nice legal 
argument against that position.  It is taken from the public record, 
direct from Roger Schlafly's motion for summary judgment, dated October 
16th, 1995.

Basically, the knapsack algorithm disclosed in the patent does not have 
the claimed property of computational infeasibility, so the patent 
cannot cover any system that does implement the claim.  For example, if 
I submit a patent that claims coverage of all forms of cold-fusion to 
generate power, and disclose an invention that does not work, then those 
general claims are not valid.  Someone who really does invent a workable 
form of cold-fusion gets to make the big patent claims.

----------------------------

4.  Hellman-Merkle is inoperative, hence invalid.

4.1.  The Hellman-Merkle patent discloses a cryptosystem popularly known 
as the "trapdoor Knapsack system", or simply "knapsack".  Ralph Merkle 
is credited with being the principal inventor, and he placed a $100 bet 
that it is secure.  Being "secure" makes it useful for communications or 
authentication.

4.2.  Time Magazine reported on Oct. 25, 1982 that the trapdoor knapsack 
had been broken, i.e., found to be not secure.  Merkle had to pay off 
the $100 bet.  IN patent jargon, the best mode was shown to be 
inoperative.  The article is attached as Exhibit. CB.

4.3.  Apparently unhappy with the article, but not denying his $100 
payoff, Merkle wrote a letter to Time Magazine, published in the Nov. 
15, 1982 issue and attached as Exhibit. CC.  In this letter, he offered 
$1000 to anyone who could break the "multiple iteration knapsack" 
system.  That system was the only alternate mode disclosed in Hellman-
Merkle which was not shown inoperative by the work described in Time.  
Merkle recommended using two or three iterations.

4.4.  Two years later, Merkle had to pay the %1000 to Ernie Brickell who 
broke the Hellman-Merkle trapdoor knapsack scheme with up to 40 
iterations.  The Diffie survey article cited above (AM. Compl. Exhibit. 
V) documents on p. 565-566 the failure of the Hellman-Merkle invention.  
(Note that Exhibit. CI recommends this Diffie article.)  One of 
Brickell's articles on the subject, published as part of the proceedings 
of Crypto '84, is attached as Exhibit. CK.

4.5.  Note that Exhibit. CD, a paper in the Communications of the ACM, a 
leading computer science journal, has an editor's comment that "the 
trapdoor Knapsack systems have been broken".  This is a direct reference 
to Hellman-Merkle being inoperative.

4.6.  The Hellman-Merkle patent is invalid and unenforceable because it 
is inoperative as disclosed.  Claims 1-6 and 14-17 require a quantity 
computationally infeasible to generate from a public key.  Claims 1-3 
and 6-17 require secure communication over an insecure channel.  There 
are no other claims.  As documented above, it turned out to be feasible 
to compute the  secret key from the public key.  It follows that the 
claimed computational infeasibility is not achieved, and the 
communication is not secure.

4.7.  PKP partners RSADSI and Cylink have known the Hellman-Merkle 
invention to be worthless since at least 1985,  and have not used it in 
their commercial products.

4.8.  As further proof of the failure of Hellman-Merkle, PKP is refusing 
to allow it to be used to protect their own trade secrets.  There was a 
motion before the Court which hinged on this issue.  In PKP's Reply 
Memorandum, PKP argues that protecting its trade secrets with Hellman-
Merkle is tantamount to putting them in the public domain.  Schlafly 
interprets this refusal as an admission that Hellman-Merkle is not 
secure.

4.9.  The Hellman-Merkle invention is not useful because of the flaws 
explained above, and therefore fails to satisfy the 35 USC 101 
requirements for patent protection.

4.10.  In the alternative, Schlafly argues that Hellman-Merkle is 
invalid for reasons of nonstatutory subject matter.  See arguments 
pertaining to the RSA patent below.  Hellman-Merkle discloses more 
hardware than RSA, but none of it is novel, and all of the RSA arguments 
apply.  The trapdoor knapsack system is described in Exhibit. CE, a 
Scientific American article by Hellman.  It is readily seen to consist 
purely of mathematical formulas.

4.11.  PKP may argue that the Hellman-Merkle claims are broader than the 
disclosed embodiments, and therefore the patent is valid in spite of the 
failure of the embodiments.  This notion is absurd, and incorrect as a 
matter of law.  Abstract concepts and ideas cannot be patented at all, 
and certainly not with an inoperative disclosure.

4.12.  In addition, there is prior art on those abstract concepts.  See 
the conference abstracts submitted by Diffie (Exhibit. CG) and Hellman 
(Exhibit. CH).  These were published in June 1976.

4.13.  In the Hellman-Merkle file history, the inventors argue that they 
are entitled to broad patent claims because earlier embodiments of 
public key cryptosystems in the prior art were impractical.  If their 
invention is impractical, then it is no better than the prior art they 
criticized.