Antoine Joux and Vanessa Vitse have updated their paper “Cover and Decomposition Index Calculus on Elliptic Curves made practical: Application to a previously unreachable curve over F_{p^6}” on eprint (eprint 2011/020). As I have already mentioned, this paper is accepted to EUROCRYPT 2012.
The paper is about “Weil descent” attacks on the ECDLP for curves over extension fields. More precisely they combine a cover attack (transforming the ECDLP to a DLP in some divisor class group of a high genus curve over an extension field of smaller degree) with Gaudry’s index calculus method (using summation polynomials for groups over extension fields). The paper does not contain any new fundamental concepts, but it gives tricks and techniques that can lead to large speedups for practical computation. The main computational result in the paper is a 149-bit elliptic curve discrete logarithm computation (taking about one month of elapsed time). This is an impressive computational result. In contrast, the current record for Pollard-type methods is around 110 bits (and a major campaign to solve a 130-bit instance for a Koblitz curve has already been running for over two years elapsed time).
Rather than discuss all the contents of the paper I will focus on the computational result.
The ECDLP instance is, of course, very special. It is important to note that it is not used for any application, and is already known to be a “weak curve”. First, the elliptic curve is defined over F_{p^6} where p is a 25-bit prime (the group order is four times a 149-bit prime). Second, the elliptic curve is of the very particular form y^2 = x(x – alpha)(x – alpha^{p^2}) where alpha in F_{p^6}, so that (as follows from work of Diem/Momose-Chao/Theriault) the Gaudry-Hess-Smart technique gives a method to transfer the discrete logarithm problem to a hyperelliptic genus 3 curve over F_{p^2}.
The first part of the attack is thus to transfer the DLP to the divisor class group of the hyperelliptic genus 3 curve over F_{p^2}. Now one can attempt to solve this DLP using Gaudry’s index calculus algorithm (inspired by Semaev’s summation polynomials). Instead of using summation polynomials, the authors follow a suggestion by Nagao to compute relations by computing Riemann-Roch spaces. Such computations boil down to solving systems of non-linear polynomial equations using Groebner basis methods. One of the main ideas in the paper is to pre-compute a “generic” Groebner basis for a “generic” system of such polynomials. This enables the authors to employ a sieving process, and this leads to an enormous practical speedup in the algorithm. The collection of relations using sieving is parallelised: the authors used 1024 cores for about 3 days to collect the required relations. The factor base was chosen to have size 2^{24}.
Rather than using a large-prime variant (which would be hard to combine with the sieving), the authors perform structured Gaussian elimination to eliminate about four-fifths of the elements of the factor base. The remaining linear algebra problem is solved using a Lanczos method and this is by far the most time-consuming part of the process (taking about 28.5 days). I am focussing here on the real elapsed time rather than total computational resources since what really matters in practice is the actual elapsed time of a computation, and some aspects of the algorithm cannot be arbitrarily sped-up using parallelisation.
To summarise, although this instance of the ECDLP was “clearly weak”, it was not at all clear that it could be solved with relatively modest computing resources in such a short time. The importance of the paper is to show that the Gaudry/Nagao algorithm can be made much more practical than expected in certain cases by using some good ideas and careful implementation.
What impact does this paper have on our understanding of the ECDLP over general extension fields F_{p^n} with n >= 4?
I suppose the main impact is to re-inforce that theoretically weak cases really should be treated with caution. Once the theoretical tools are in place, one should not be surprised if implementation tricks enable relatively large instances to be solved in relatively little time.
The paper discusses n = 6 in detail and gives several cases different to the one mentioned above. The case n = 4 is also studied, and a smaller improvement over the previous “state of the art” is obtained. In both cases it is not possible to attack a fully general elliptic curve over those fields, instead it would be necessary to use isogenies to pass to one of the special families of curves and this process is slow if the families are “sparse” among all curves. For prime values of n (such as n = 3, 5 and 7) one cannot combine the two methods, and so the paper does not discuss these cases (though the improvements to the Gaudry/Nagao method may be of interest). The cases n = 8 and 9 might be interesting to study, by again using a covering attack with respect to the degree 2 or 3 extension and then using Semaev/Gaudry/Nagao. For general n one needs to have good theoretical results about covering attacks to get the process started.
— Steven Galbraith
ellipticnews 