On Sun, 11 Sep 2005, Alexander Klimov wrote:
Does anyone know a good survey about ECC patent situation?
I have made a shallow review (comments are welcome!) of the
patents that Certicom claims are pertained to ECC implementation
and it looks like there are no real road-blocks for ECDH and
ECDSA among them. In other words, IIUC it is possible to
implement EC encryption and signing without violating any patent
(of course, the implementer must be lucky enough to avoid any
patented optimization).
BTW, it looks like OpenSSL developers share this POV: README [1]
on branch OpenSSL_0_9_8-stable which implements ECDH and ECDSA
has PATENTS section which does not say a word about ECC.
In order to make this review I located two documents [2,3] in
which Certicom lists its patents related to ECC. It is
impossible to say that nobody else has patents in this area, but
the fact that the web site of SECG [4] (which is the first
working group anywhere that is devoted exclusively to developing
standards based on ECC) does not have claims by anybody else
can be viewed as a hint of this.
Let us now review these lists. The first of them [2] contains
the following patents:
[As of May 26, 1999] Certicom is the owner of the following
issued patents:
US 4,745,568 Computational method and apparatus for finite
field multiplication, issued May 17, 1988. This patent
includes methods for efficient implementation of finite field
arithmetic using a normal basis representation.
[Optimization of multiplication in GF_{2^n}]
US 5,787,028: Multiple Bit Multiplier, issued July 28, 1998.
[Multiplication in GF_{2^{nm}}, IIUC it is of no use now due to
Weil descent attack for EC(GF_{2^k}) with composite k.]
US 5,761,305 Key Agreement and Transport Protocol with
Implicit Signatures, issued June 2, 1998. This patent includes
versions of the MQV protocols.
US 5,889,865 Key Agreement and Transport Protocol with
Implicit Signatures, issued March 30, 1999. This patent
includes versions of the MQV protocols.
US 5,896,455 Key Agreement and Transport Protocol with
Implicit Signatures, issued April 20, 1999. This patent
includes versions of the MQV protocols.
[These three are about MQV protocol and so are unrelated to ECDH
and ECDSA.]
Certicom has the exclusive North American license rights to
the following issued patent:
US 5,600,725 Digital signature method and key agreement
method, issued Feb. 4, 1997. This patent includes the
Nyberg-Rueppel (NR) signature method.
[Described as pertains to PV signatures below.]
Certicom has patent applications that include the following:
* Methods for efficient implementation of elliptic curve
includes efficient methods for computing inverses.
* Methods for point compression.
* Methods to improve performance of private key operations.
* Various versions of the MQV key agreement protocols.
* Methods to avoid the small subgroup attack.
* Methods to improve performance of elliptic curve
arithmetic; in particular, fast efficient multiplication
techniques.
* Methods to improve performance of finite field
multiplication.
* Methods for efficient implementation of arithmetic modulo n.
* Methods to perform validation of elliptic curve public keys.
* Methods to perform efficient basis conversion.
The second [3] of the lists contains the following:
[As of February 10, 2005] Certicom is the owner of the
following issued patents:
EP 0 739 105 B1 (validated in DE, FR, and the UK) Method for
signature and session key generation pertains to the MQV
protocol
[Anybody knows, where it is available online?]
US 5,761,305 Key Agreement and Transport Protocols with
Implicit Signatures pertains to the MQV protocol
US 5,889,865 Key Agreement and Transport Protocol with
Implicit Signatures pertains to the MQV protocol
US 5,896,455 Key Agreement and Transport Protocol with
Implicit Signatures pertains to the MQV protocol
US 6,122,736 Key agreement and transport protocol with
implicit signatures pertains to the MQV protocol
US 6,785,813 Key agreement and transport protocol with
implicit signatures pertains to the MQV protocol
[Menezes-Qu-Vanstone (MQV) protocol -- an authenticated protocol
for key agreement based on the Diffie-Hellman scheme.]
US 5,600,725 Digital Signature Method and Key Agreement
Method pertains to PV signatures
[Pintsov-Vanstone (PV) signatures -- a scheme with partial
message recovery.]
US 5,933,504 Strengthened public key protocol pertains to
preventing the small-subgroup attack
[This one contains the following claims:
1. A method of determining the integrity of a message
exchanged between a pair of correspondents, said message
being secured by embodying said message in a function of
.alpha..sup.x where .alpha. is an element of a finite
group S of order q, said method comprising the steps of
at least one of the
