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:
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:
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.
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:
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'.
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.
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.
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.
Links
Click here to find where the image at the top of the page comes from
Last Modified: 23-8-2010
