 Elliptic Curve Cryptography

Summary

Elliptic curve cryptography (ECC) was proposed by Victor Miller and Neal Koblitz in the mid 1980s.

An elliptic curve is the set of solutions (x,y) to an equation of the form y^2 = x^3 + Ax + B, together with an extra point O which is called the point at infinity. For applications to cryptography we consider finite fields of q elements, which I will write as F_q or GF( q ). When q is a prime one can think of F_q as the integers modulo q.

We usually write E for the equation y^2 = x^3 + Ax + B and use the notation E( F_q ) for the set of points (x,y) with coordinates in the field F_q together with the point O (which is defined over every field).

The set of points on an elliptic curve forms a group under a certain addition rule, which we write using the notation +. The point O is the identity element of the group. When we work over a finite field then this group is necessarily finite (as there are only finitely many points).

Given a point P=(x,y) and a positive integer n we define [n]P = P + P + ... + P (n times). The order of a point P=(x,y) is the smallest positive integer n such that [n]P = O.

We denote by < P > the group generated by P. In other words < P > = {O, P, P+P, P+P+P, . . .}.

The security of elliptic curve cryptography relies on the following problem:

Elliptic Curve Discrete Logarithm Problem (ECDLP): Let E be an elliptic curve over a finite field F_q. Suppose P is some point of E( F_q ) and let Q be a point in < P >. Find an integer t such that Q = [t] P.

It is widely believed that the elliptic curve discrete logarithm problem is hard to computationally solve when the point P has large prime order. The known methods for solving the ECDLP are:

• The Pohlig-Hellman algorithm (which reduces the problem to subgroups of prime order).
• Shanks' baby-step-giant-step method.
• Pollard's methods, the rho method and the kangaroo method, both of which have parallel versions due to van Oorschot and Wiener.
• The Menezes-Okamoto-Vanstone (MOV) attack using the Weil pairing.
• The Frey-Rueck attack using the Tate pairing.
• The attacks on anomalous elliptic curves (i.e., elliptic curves over F_p which have p points) due to Semaev, Satoh-Araki and Smart.
• Weil descent (for some special finite fields).
Of the above methods, only the anomalous curves attack runs in polynomial time. The MOV, Frey-Rueck and Weil descent methods are (at their fastest) subexponential in complexity.

Due to the Pohlig-Hellman algorithm we always restrict to the case where the point P has large prime order. Then the only algorithms which are applicable for all elliptic curves are the methods of Shanks and Pollard, and these methods have exponential complexity.

The public key cryptosystems available for ECC are analogues of the cryptosystems available for other discrete logarithm based systems (such as the multiplicative group of a finite field). These include Diffie-Hellman key exchange, El Gamal public key encryption, and ECDSA (an analogue of the US government's digital signature standard).

In fact, the security of cryptosystems based on elliptic curves usually relies on related problems like the (computational) Diffie-Hellman problem (CDH) or the Decision Diffie-Hellman problem (DDH).

News

The best way to get the news about ECC is to attend the annual ECC conference. The 2007 ECC conference was in Dublin on September 5-7. The 2008 conference was held in the Netherlands. The 2009 conference was held in Calgary, Canada. The ECC 2010 conference will be held in Redmond, Washington State, USA, Oct 18-22, 2010.

For the past 5 years or more there have been no significant new results on the elliptic curve discrete logarithm problem. There are at least two possible interpretations of this fact:

• Everyone has been working on pairing-based cryptography and has stopped looking at the ECDLP.
• Everyone is now interested in lattices and no-one is looking at elliptic curves any more.
• Research progress on the ECDLP has stabilised, in much the same way that progress on factoring has been stable for the last 15 or more years. This interpretation suggests that the ECDLP is indeed a hard computational problem.
In any case, the lack of any significant progress on the ECDLP in recent years further supports my opinion that elliptic curve cryptosystems are a secure choice for public key cryptography.

Other news:

I like most of Jung-Hee Cheon's recent papers on Pollard rho etc. I also like the GLS paper on the GLV method, but I would say that wouldn't I? And I like Icart's result on hashing to elliptic curves. Sutherland's work is very cool too. But none of these have any significant impact on the practical use of ECC.

• Edwards elliptic curves

A surprising discovery by Edwards is that there is another way to write elliptic curves (i.e., not in Weierstrass form) so that the group law can be computed more efficiently than the usual methods.

This work has been detailed by Tanja Lange and Dan Bernstein. See this page for a summary of progress.

The big news (in my opinion) in ECC over the last 2--3 years was the following:

• NSA support for elliptic curves

The NSA has decided to move to elliptic curve based public key cryptography. You can read more about this here. The full package of specified cryptography algorithms is called `Suite B'.

• Weil pairing and Tate pairing

The use of the Weil pairing and Tate pairing in cryptography goes back to Victor Miller's unpublished paper of 1986, and in particular the results of Menezes-Okamoto-Vanstone and Frey-Rueck. However, these first applications were destructive (i.e., using pairings to transform the ECDLP into a discrete logarithm problem in the multiplicative group of a finite field).

More recently it has been noticed that pairings can be used to build cryptosystems with certain functionality. The foundational paper is Antoine Joux ``A one-round protocol for tripartite Diffie-Hellman''. In fact, earlier work suggesting the use of pairings in cryptography was done by Mitsunari-Sakai-Kasahara in 1999 and Sakai-Ohgishi-Kasahara in 2000. In particular, the paper of Sakai-Ohgishi-Kasahara suggests that pairings could be used to enable identity-based cryptography. However, these two Japanese papers were not known to the `western' academic community until 2002.

The most impressive application of pairings to cryptography is the identity-based encryption scheme of Boneh and Franklin (Crypto 2001). This system elegantly solves the long-standing open problem of providing secure and efficient identity-based encryption (Shamir had already given identity-based signatures in his 1984 paper which invented the principle). A generalisation of this concept is identifier-based cryptography.

Note that, in implementations, the Tate pairing is superior to the Weil pairing. There are numerous papers on pairing implementation. The most significant of recent works is (in my opinion) eprint 2004/375 and eprint 2006/110.

There has also been a lot of interest in generating ordinary elliptic curves with suitable embedding degree. The starting paper in this subject is by Miyaji, Nakabayashi and Takano.

Other good work has been done by Scott-Barreto and Barreto-Naehrig. For information about families of MNT curves with cofactors (from the Galbraith-McKee-Valenca paper) see Paula Valenca's web page.

Pairings are currently the most active research area in ECC. There is even a conference series devoted entirely to pairings. The Pairing 2007 conference was held in Tokyo in July 2007. The Pairing 2008 conference will be held at Royal Holloway in September 2008.

• Index calculus on abelian varieties and Weil descent

This was the most exciting development in 2004.

Igor Semaev proposed the use of summation polynomials for an index calculus algorithm for elliptic curves. However, his approach would require overcoming a serious practical obstacle which currently seems insurmountable. Nevertheless, Pierrick Gaudry realised that the method might be more applicable in the case of abelian varieties, especially the Weil restriction of an elliptic curve over an extension field GF( q^n ) where n is 3 or 4. Pierrick's preprint ``Index calculus for abelian varieties and the elliptic curve discrete logarithm problem'' contains these results.

Subsequently, Claus Diem has extended the idea for larger values of n. In particular, he has given a complexity analysis along a certain curve in (q,n)-space and shown that the method has subexponential complexity (with factor 3/4). This is an exciting and surprising result!
For more details please see Claus Diem's new book.

The first family of elliptic curve discrete logarithm problems which can be solved in subexponential time was the case of supersingular curves. Diem's result adds another family to this list, namely all elliptic curves over fields GF( q^n ) where both q and n are `large'. It is important to stress that the two cases widely used in practice, which are GF( p ) and GF( 2^n ), are not vulnerable to this approach.

A related topic is Claus Diem's index calculus method for non-hyperelliptic genus 3 curves. This result potentially gives further discouragement from considering curves of genus different from 1 or 2 in cryptography.

• Certicom Challenge

It is over a year since the last Certicom challenge result (namely, ECC2-109). Since the next challenge is 131 bits, I'm guessing it will be a long time before I need to update this text.

Information about the challenge is available here.

Books

There are now several excellent books about ECC.

Advances in Elliptic Curve Cryptography edited by I. Blake, G. Seroussi and N. Smart. This is definitely not an introductory text. Instead it covers recent developments in ECC. The intended reader is someone with a basic knowledge of ECC who wants to learn about the latest research developments without having to read all the papers in the subject. I think it is an excellent book, but I am a contributor so am completely biased.
This book is highly recommended for researchers in the field.

The Handbook of elliptic and hyperelliptic curve cryptography edited by H. Cohen and G. Frey. This is an excellent reference for researchers in the field. I increasingly use this book as a reference, and I increasingly find it useful.
This book is highly recommended for experts in cryptography.

A Course in Number Theory and Cryptography by Neal Koblitz. This is the best ``easy'' reference for ECC. It contains a nice presentation of the basic ideas. Unfortunately, the book is too elementary to cover many topics which are needed to understand the research literature in ECC.
This book is highly recommended for beginners.

Guide to Elliptic Curve Cryptography by Darrel Hankerson, Alfred Menezes, and Scott Vanstone. This book is written for computer scientists, engineers and security professionals. It gives a very thorough and detailed presentation of the implementation aspects of ECC. Many efficient algorithms for point multiplication etc are described. The book does not deeply discuss the mathematics behind ECC.
This book is highly recommended for cryptographers who want to implement or use ECC in practice.

Elliptic Curves and Cryptography by Ian Blake, Gadiel Seroussi and Nigel Smart. This book is useful resource for those readers who have already understood the basic ideas of elliptic curve cryptography. This book discusses many important implementation details, for instance finite field arithmetic and efficient methods for elliptic curve operations. The book also gives a partial description of the Schoof-Atkin-Elkies point counting algorithm (mainly in characteristic two) and a description of some of the mathematics behind the attacks on the ECDLP.
This book is recommended for researchers in the field.

Elliptic Curves: Number Theory and Cryptography by Lawrence C. Washington. This is a very nice book about the mathematics of elliptic curves. It contains proofs of many of the main theorems needed to understand elliptic curves, but at a slightly more elementary level than, say, Silverman's book. This book would be an excellent next step after the book of Koblitz mentioned above. I recommend this book to all my students and I have not had any serious complaints yet. There is quite a lot of information about cryptographic aspects, including a discussion of the Weil and Tate pairings.

There is a new edition of Washington's book with a little bit of extra material. It remains a fine text.
This book is highly recommended for those who want to get a deeper understanding of the mathematics behind ECC.

An introduction to mathematical cryptography by J. Hoffstein, J. Pipher and J. H. Silverman. This book contains a good introduction to all sorts of public key cryptography, including elliptic curves, at an advanced undergraduate level. It seems to be a good book and would be a suitable alternative to Stinson or Koblitz.
This book is recommended for students of mathematics who want an introduction to the subject.

Algebraic aspects of cryptography by Neal Koblitz. A more advanced book than the earlier book by Koblitz. This book features some discussion on hyperelliptic curve cryptography, but it does not have much of interest to say about ECC.

Elliptic curve public key cryptosystems by Alfred Menezes. This book contains a lot of the mathematical background in a fairly simple form. It is a useful book, although now quite out-of-date. Menezes himself does not recommend this book.

Elliptic Curves and Their Applications to Cryptography: An Introduction by Andreas Enge. This book covers most of the mathematics behind ECC in a very explicit, elementary and detailed fashion. I find the style too detailed and I do not believe the book is good value for money.