Elliptic curve cryptosystems, as introduced in 1985 by Neal Koblitz and Victor Miller, have no general patents, though some newer elliptic curve algorithms and certain efficient implementation techniques may be covered by patents.
Here are some relevant implementation patents.
- Apple Computer holds a patent on efficient implementation of odd-characteristic elliptic curves, including elliptic curves over GF(p) where p is close to a power of 2.
- Certicom holds a patent on efficient finite field multiplication in normal basis representation, which applies to elliptic curves with such a representation
- Cylink also holds a patent on multiplication in normal basis
Certicom also has two additional patents pending. The first of these covers the MQV (Menezes, Qu, and Vanstone) key agreement technique. Although this technique may be implemented as a discrete log system, a number of standards bodies are considering adoption of elliptic-curve-based variants. The second patent filing treats techniques for compressing elliptic curve point representations to achieve efficient storage in memory.
In all of these cases, it is the implementation technique that is patented, not the prime or representation, and there are alternative, compatible implementation techniques that are not covered by the patents. One example of such an alternative is a polynomial basis implementation with conversion to normal basis representation where needed. (This should not be taken as a guarantee that there are no other patents, of course, as this is not a legal opinion.) The issue of patents and representations is a motivation for supporting both representations in the IEEE P1363 and ANSI X9.62 standards efforts.
The patent issue for elliptic curve cryptosystems is the opposite of that for RSA and Diffie-Hellman, where the cryptosystems themselves have patents, but efficient implementation techniques often do not.