Elliptic Curve Cryptography


This page no longer maintained!

Click here for the elliptic curve cryptography blog.


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:

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:

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.


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


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.

Errata for the book.

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.


Links


Click here to find where the image at the top of the page comes from


Back

Last Modified: 23-8-2010