Recently, the paper “A Discrete Logarithm Attack on Elliptic Curves” by Otto Johnston was posted on the IACR server as eprint 2010/575. This blog entry makes some general remarks about this work.

(Disclaimer: I have not studied the paper in complete detail or checked all the technical details. My opinions are subject to change.)

The paper is in the topic of “Weil descent”, which is a general approach to solving the discrete logarithm problem (DLP) on elliptic curves over extension fields F_{q^n} where n > 1. The basic idea of all these methods is to consider the group of points on an elliptic curve E( F_{q^n} ) as the group of points on some higher dimensional geometric object over F_q. One then hopes to solve the DLP using some kind of index calculus method. Most authors prefer to use field-theoretic language rather than geometric tools. A good survey of the subject is Chapter VIII, by Florian Hess, of the book “Advances in Elliptic Curve Cryptography”, edited by Ian Blake, Gadiel Seroussi and Nigel Smart.

This approach to the elliptic curve (DLP) has had some famous successes. Particularly striking is the work of Pierrick Gaudry and Claus Diem (independently). Their methods lead to a general method to solve the DLP on an elliptic curve E( F_{p^4} ) in \tilde{O}( p^{1.5} ) bit operations. This is asymptotically faster than the \tilde{O}( p^2 ) bit operations of Pollard rho. (Recall that \tilde{O}( p^2 ) means O( p^2 \log(p)^m ) for some integer m.)

Gaudry’s result is heuristic, but the algorithm has been put on a sound footing in Diem’s habilitation thesis On arithmetic and the discrete logarithm problem in class groups of curves. Theorem 5 (on page vi) of Diem’s thesis states that the discrete logarithm problem in the group of rational points of an elliptic curves E( F_{p^n} ) can be solved in an expected time of \tilde{O}( q^{2 – 2/n} ) bit operations. When n = 4 this gives the above claim. (Diem’s paper also gives many other results which are not relevant in this post.)

The paper on eprint makes the same claim. Section 1.3 of the paper speaks of solving the DLP on E( F_q ) in “roughly O( q^{3/8} )” operations; since this result requires q = p^4 we have complexity \tilde{O}( p^{1.5} ) as before.

However, Otto’s paper uses a much more efficient index calculus method than used by Gaudry and Diem, since it reduces the problem to a DLP on the Jacobian of a curve whereas Gaudry and Diem need to use summation polynomials. Hence, from a practical point of view, the result has more impact on the actual security of the elliptic curve DLP than the results of Gaudry and Diem. (Essentially, the devil is in the \tilde{O}.)

The technique of the paper is to exploit a nice geometric construction for Weil descent of quadratic extensions over fields of odd characteristic. For certain elliptic curves (see equation (3.2) of the paper) this approach can be iterated twice. In the special case of elliptic curves over F_{q^4} one therefore goes to a dimension 2 Jacobian over F_{q^2} and then a dimension 4 Jacobian over F_q.

Another benefit of the approach is that it works with isogenies of Jacobians, rather than maps between curves. This means the method is potentially more powerful than approaches using function fields (an algebraic extension of function fields corresponds to a rational map between the underlying curves, and hence a homomorphism of Jacobians, but the converse does not hold.)

Similar ideas have appeared previously in the literature, but had not been combined in this way before. For example, explicit formulae for Weil descent of quadratic extensions appear in the paper Weil descent attack for Kummer extensions by Nicolas Theriault. Theorem 6 of that paper (taking n = r = 2) gives doubling of genus under a quadratic extension for certain curves; as does Johnston. The idea of iterating constructions from Kummer or Artin-Schrier extensions is given by Florian Hess in Generalising the GHS Attack on the Elliptic Curve Discrete Logarithm Problem.

There is no doubt that Otto’s ideas deserve further study. Some natural problems are to determine the exact class of curves which are vulnerable to the approach. Another natural problem is to implement the index calculus algorithm to see how it performs in practice (remember: the devil is in the \tilde{O}!). It is likely that this paper extends our current toolbox of algorithms for the DLP on elliptic curves over small degree extension fields.

— Steven Galbraith