Patents

[derek@cs.wisc.edu (Derek Zahn)]

Cypherpunks:

Too often in email fora, when a substantive discussion results
in the presentation of interesting material, no effort is made
to integrate the result into a form that will be useful beyond
the heat of the exchange.  For this reason, I will impose once
more upon the bandwidth of Cypherpunks with a rewrite of my
previous mini-essay.  Because of the effort and generosity of
many correspondents, I hope that some of the clueless parts
have had clues plugged in.

Rather than equivocating, which is my usual practice when not
entirely certain of what I'm saying, I state some "facts" quite
plainly here because equivocation is kind of annoying to everybody.
If anybody notices that I'm "full of it" in some way, please let
me know... I have no desire to mislead or cause confusion.

Special thanks to:

E. Carp
L. Detweiler
P. Metzger
smb@research.att.com

MOTIVATION:

Starting with a premise that widespread use of Public-Key
Cryptography (PKC) would be in some sense a Good Thing
(and for our purposes here ignoring the interesting and
spirited reasons for *why* PKC is so cool), newbie
Cypherpunks may well wonder how this can be achieved.
My purpose here is not to complain about restrictions
or wonder about alternate worlds without those
restrictions; rather it's an attempt to assess what
the restrictions are and what their practical
implications are.

The important fact of life in this area is that PKC has
been granted patent protection and is proprietary
technology.  Exclusive licensing rights to PKC and
its dominant embodiment, the RSA algorithm, have been
assigned to Public Key Partners (PKP).

PATENT PROTECTION:

smb@research.att.com explained patents (only excerpts are quoted here):

> ... a patent is (theoretically) a contract between an inventor
> and society.  In return for the inventor teaching everyone about the
> new idea, he or she gets a monopoly on use of that idea for a limited
> period (normally 17 years in the U.S.).

> Patents cover the right to build, make, import, or even *use* the
> protected idea. ... A patent is *not* a license to do something.
> Rather, it is the right to prevent others from doing it.

> For our purposes, a patent consists of two major parts.  The first is
> more or less a technical paper; this is what you're supposed to learn
> from. ... The second part is the ``claims''; these are written in very dense
> legalese, and are supposed to delimit exactly what's new.  You infringe
> a patent if your activity includes all of the elements of any one
> claim.  ... you have to make sure that what your claim doesn't include
> prior art.

There are four patents of primary interest (I mention three because I'm
not certain what 4,424,414 [1984] is all about):

4,200,770, granted 1980.  This patent (smb again:) " claims virtually all
mechanisms for public key distribution or exchange systems.  Exponential
key exchange is the particular example given; it's claimed, too."  This
patent has Diffie, Hellman, and Merkle as inventors.  Diffie and Hellman
working together, and Merkle working independently, came up with the
ideas behind PKC.  The patent was assigned to Stanford University.
Since with PKC keys can be broadcast without requiring a secure channel,
it offers obvious advantages for key distribution.

4,218,582, granted 1980.  It (smb:) "claims all of public-key
cryptography.  The knapsack system was the particular system given;
it was claimed, as well."  Hellman and Merkle are the inventors
on this patent, also assigned to Stanford.  From reading Diffie's
"The First Ten Years of Public Key Cryptography," I get the impression
that Diffie was not on this patent because Hellman and Merkle
together devised the "trapdoor knapsack" that was the particular
system illustrating PKC.  At some financial cost to Merkle in lost
bets, that particular PKC system was broken, but that is only a
historical footnote.

4,405,829, granted 1983.  This patent is for the RSA algorithm,
and has Rivest, Shamir, and Adleman as inventors.  This patent
was assigned to MIT.  Diffie calls RSA "the single most spectacular
contribution to public key cryptography" and it is an un-"broken"
complete public key cryptosystem.  RSA is the overwhelmingly
dominant PKC system.  The difficulty of breaking RSA has not
been proven equal to the difficulty of factoring the product
of two large prime numbers, which would be desirable because
it would preclude some cracking scheme coming in from nowhere
(we'll say that factoring is "somewhere" because it's commonly
studied).  Rabin has come up with a RSA variant that is equivalent
to factoring, but has other technical problems.

IMPLICATIONS

Because PKP has been assigned all licensing rights to these
patents, which cover all of PKC to one extent or another,
we are not at present free to code up and sell PKC tools
without licensing the technology from PKP -- at least not
without risk of a lawsuit.  Some people believe that
one or more of the patents are invalid in some way.  A
patent must be for something new, useful, and non-obvious.
Given that PKC is useful, the other two criteria could
be challenged:
  * perhaps the ideas could be described as obvious
  * perhaps prior art could be demonstrated, so that the
    patented inventions aren't really "new".
Such an effort would cost a great deal of money and is
uncertain of success.

Other efforts to get around the PKP monopoly are possible.
One idea would be to claim an "experimental use exemption",
an unclear way of legitimately ignoring a patent for personal
experimental use (see the comp.patents FAQ for more information
on this and other patent issues).  Another idea is simply
to ignore the patent.  PKP would have to sue the infringer,
an expensive and time-consuming process and probably not worthwhile
for some small infringements -- but it's probably very unwise
to try making any money this way!  Another legal route would
be to claim that the assignment of rights by MIT and Stanford
to PKP violate anti-trust laws.

Users of the wonderful "underground" program PGP presumably
are doing so with the "experimental use" idea or the "ignore
the patent" idea in mind.  While this has caused some friction,
it appears not to be very dangerous for individual users.

The final approach to an end-run around the patents is to wait.
The broad PKC patents expire in less than four years, which
should allow non-RSA PKC schemes to be developed and sold
without restriction.  However, it is important not to
underestimate the difficulties of doing this.  Solid efficient
PKC schemes are most definitely not trivial to devise, and
an extended period of evaluation by professional cryptologists
is probably required in order to convince users that the
scheme offers good security.  The RSA patent expires in 2000.

The straightforward approach, and the only practical one for
small-time entrepreneurs wanting to develop PKC products now, is
to strike a deal with PKP for the use of RSA (as ViaCrypt has
done for the "legit" version of PGP).

It seems that the designers of Internet Privacy Enhanced Mail (PEM)
agreed with this assessment, as they took the unusual step of including
proprietary RSA in their standard.  For their part, in RFC 1170, PKP
states:

  "We assure the interested parties that Public Key Partners will comply
  with all of the policies of ANSI and the IEEE concerning the availability
  of licenses to practice this art.  Specifically, in support of any RSA
  signature standard which may be adopted, Public Key Partners hereby
  gives its assurance that licenses to practice RSA signatures will be
  available under reasonable terms and conditions on a non-discriminatory
  basis."

The exact meaning of "reasonable terms and conditions" is not clear.
For evidence we can look at the ViaCrypt product, which is apparently
available for less than $50 in quantity.  Since it includes the
extensive facilities of PGP, as well as support overhead, in addition
to the cost of the RSA license.

Standards (for example, PGP and PEM) are key to widespread use of PKC.
It appears unlikely that standards will go to something besides RSA
any time in the near future.

The final option is to invent some new revolutionary technique, to
amaze and delight Cypherpunks everywhere.  Please do.  Good luck.

REFERENCES

  sci.crypt FAQ: information about PKC
  comp.patents FAQ: information about patents
  RIPEM FAQ: stuff about PKP stopping developement of an implementation
	of Rabin's scheme
  Diffie, W.: "The First Ten Years of Public Key Cryptography", chapter
    3 of: G. Simmons (ed.), Contemporary Cryptology: the Science of
    Information Integrity. IEEE press, 1991.
      which  might be the same as:
    "The first ten years of public key cryptography", Diffie, W.,
    Proceedings of the IEEE 76:5, 1988, pp 560-577.
  Cypherpunks list archive (there is one, right?):  many interesting
	comments, often highly-clued.

derek