Elliptic crypto is patented

Eric asks whether elliptic encryption might not be a solution to the world's
patenting woes.

Last April, schirado@lab.cc.wmich.edu (Schirado) asked whether anyone was 
interested in trying an implementation. I was relatively free of work at that
time, and volunteered. Then I got busy; IAC it appeared far too slow for
software.

Read: _An Implementation of Elliptic Curve Cryptosystems Over F-2-155_ , 
IEEE Journal on Selected Areas in Communications, Vol. 11, #5, June 1993 
(page 804).

Incidentally Next Computer's Fast Elliptic Encryption, FEE, used
elliptic curves, and is patented (by R E Crandell, USP# 5,159,632,27 October 
1992); also, elliptic crypto is probably covered by the DH/PKP patents.


"We know everything about you that we need to know" - Coleta Brueck, IRS
-----------------------------------------------------------------------------
Rishab Aiyer Ghosh                                "In between the breaths is
rishab@dxm.ernet.in                                  the space where we live"
rishab@arbornet.org                                        - Lawrence Durrell
Voice/Fax/Data +91 11 6853410  
Voicemail +91 11 3760335                 H 34C Saket, New Delhi 110017, INDIA

> Incidentally Next Computer's Fast Elliptic Encryption, FEE, used
> elliptic curves, and is patented (by R E Crandell, USP# 5,159,632,27 October 
> 1992); also, elliptic crypto is probably covered by the DH/PKP patents.
> 

Is the FEE patent on some tweaking of it, or are they claiming 
anything using ECs for crypto? (Esp. DH and ElGamal analogue)?

PKP claims all public key, but: 

a) Vanilla El Gamal crypto is covered, tenuously at best, by their 
   Diffie-Hellman patent, which some consider to be contestable based 
   on publication more than a year before filing. The DH patent 
   expires in a few years as well.

b) EC-based El Gamal is ever farther from DH and vanilla El Gamal
   (since it uses different math). It is even less likely to be
   held to infringe.

PKP's overall claim to public key cryptography may also be
weakened by several different outcomes to the current round
of lawsuits.

One thing that is _not_ likely to be weakened is their claim on
RSA. Therefore, if you're not interested in supporting PKP's
attempt to make their strongest patent the centerpiece of 
various Internet standards, working towards EC encryption is a
Good Thing.

From: rishab@dxm.ernet.in

   Incidentally Next Computer's Fast Elliptic Encryption, FEE, used
   elliptic curves, and is patented (by R E Crandell, USP#
   5,159,632,27 October 1992); 

Does anybody have a copy of this to see exactly what is claimed?

   elliptic crypto is probably
   covered by the DH/PKP patents.

If you believe RSADSI it is.  Now, are they going to say otherwise?

The fact of the matter is, you can't patent ideas, nor general
characteristics of devices.  You can patent particular processes or
mechanisms for particular purposes.  If you come up with a different
process or mechanism, the patent does not cover it.  If you come up
with a different purpose (!), the patent does not hold.  

The limitation to this difference is the doctrine of extension.  A
patent covers not only the particular thing patented but also things
substantially similar to it.  This is to prevent trivial changes from
remaining unprotected.

Another, less relevant, protection is given to inclusion.  If a device
includes a patented mechanism, then the patent is required to practice
the device, even if the larger device is also patented.  Ciphers
typically do not include other specific ciphers wholesale, so this
doesn't typically apply.  One big exception is the blind signature,
which does use specifics of RSA.  This may be one of the issues with
respect to restricted availability of the ecash trial in the USA.

In my opinion, RSADSI is claiming far too much for their patent
portfolio.  In particular, claiming "all public key" is just hogwash.
Elliptic curve cryptosystems certainly use a different enough
mechanism not to fall under extension.  El Gamal is a completely new
mechanism; if RSADSI wants to claim that modular exponentiation for
crypto is covered, they'll have a hard time actually arguing that one.

Eric