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 correspondents receiving public information .alpha..sup.x where x is an integer selected by another of said correspondents, determining whether said public information .alpha..sup.x when exponentiated to a value t where t is a divisor of q provides a resultant value .alpha..sup.xt corresponding to the group identity and rejecting messages utilizing said public information if said resultant value corresponds to said group identity. 3. A method according to claim 1 wherein said order q is a prime number. but IIUC it is exactly what DSA does: q is a prime, p = q z + 1 is also a prime, g = h^z (p), that is g^q = 1 (p) and thus g "is an element of a finite group S of order q ... wherein said order q is a prime number," as a part of a signature g^x is sent, where "x is an integer selected by another of said correspondents". Am I missing something?] US 6,141,420 "Elliptic Curve Encryption Systems" pertains to point compression [Point compression theme seems to start from the following claims: 29. A method of transferring the coordinates of a point on an algebraic curve defined by a function of two variables between a pair of correspondents connected by a data communications link comprising the steps of forwarding from one correspondent to another a coordinate of said point, providing at said other correspondent parameters of said algebraic curve, and computing at said other correspondent said other coordinate from said one coordinate and said algebraic curve. 30. A method according to claim 29 including the step of forwarding with said one coordinate identifying information of said other coordinate and utilising said identifying information and a discriminating function to determine the appropriate value of said other coordinate. In other words, instead of sending a pair (x,y) that satisfies F(x,y) = 0 one sends x and the recipient recovers y using the equation alone (29) or using an additional hint about which of several y was used (30). Here the art is (lossless) data compression and every "person having ordinary skill in the art" is aware of predictor-corrector method used here: using partial data (x and, possibly, a hint) and the knowledge of data distribution (F(x,y)=0) the recipient recovers the whole information. How it is possible to get a patent on such an obvious application of a well-known technique? >From my POV point compression in the EC(GF_p) case is absolutely trivial, but the case of EC(GF_{2^p}) probably is less so. In any case, there is no problem to implement ECDSA and ECDH without point compression. Any pointers to prior art about at least point compression in EC(GF_p)?] US 6,618,483 "Elliptic curve encryption systems" pertains to point compression [Here Claim 3 seems to be of the same type.] US 6,704,870 "Digital Signatures on a Smart Card" pertains to ECDSA [Seems to be an optimization for a smartcard which uses computational power of the card accepting device: == Abstract == A digital signature scheme for a "smart" card utilizes a set of prestored signing elements and combines pairs of the elements to produce a new session pair. The combination of the elements is performed partly on the card and partly on the associated transaction device so that the exchange of information between card and device does not disclose the identity of the signing elements. The signing elements are selected in a deterministic but unpredictable manner so that each pair of elements is used once. Further signing pairs are generated by implementing the signing over an anomalous elliptic curve encryption scheme and applying a Frobenius Operator to the normal basis representation of one of the elements.] CH 693 252 "Verfahren und Vorrichtung zur Erzeugenung einer ganzen Zahl" [that is, IIUC, "Procedure and device for the generation of an integer"] pertains to key generation [Any idea where to download this one?] US 6,078,667 "Generating Unique and Unpredictable Values" pertains to key generation [The method disclosed in this patent: == Abstract == An integer for a private key is generated utilising a pair of components that are combined in a fixed predictable manner. The first component is generated from a sequencer such as a counter that generates non-repeating distinct value and the second component is generated in a random manner. By combining the components the integer has a unique and unpredictable value. is both obvious (to get X with properties A and B concatenate X_a, which has property A, and X_b, which has property B) and AFAIU pointless for real key-generation because a long-enough random key is unique with overwhelming probability.] AU 758044 "Implicit certificate scheme" pertains to bullet certificates EP 1 066 699 "Method of generating a public key in a secure digital communication system and implicit certificate" pertains to bullet certificates US 6,792,530 "Implicit certificate scheme" pertains to bullet certificates [Implicit (aka. bullet) certificates "allow the recipient to extract and verify the public key of the other party from the signature portion."] Pertinent patent applications: * Methods to improve the performance of elliptic-curve arithmetic. * Methods to improve the performance of finite-field operations. * Methods to improve the performance of private-key operations. * Methods to improve the performance of public-key operations, including signature verification. * Methods to improve the performance of modular arithmetic. * Methods pertaining to the validation of elliptic-curve public keys. * Methods to thwart domain-parameter attacks. * Methods to perform efficient basis conversion. * Methods to generate keys with desirable cryptographic properties. * Methods pertaining to PV signatures. [1] http://cvs.openssl.org/getfile/openssl/README?v=1.52.2.17 [2] http://www.secg.org/collateral/certicom_secg_patent.pdf [3] http://www.secg.org/download/aid-398/certicom_patent_letter_SECG.pdf [4] http://www.secg.org/?action=secg,docs_member_patents -- Regards, ASK --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]