Several recent preprints have discussed summation polynomial attacks on the ECDLP in characteristic 2:
- eprint 2015/310, New algorithm for the discrete logarithm problem on elliptic curves, by Igor Semaev.
- eprint 2015/319, Point Decomposition Problem in Binary Elliptic Curves, by Koray Karabina.
- arxiv 1503.08001, Notes on summation polynomials, by Michiel Kosters and Sze Ling Yeo.
To recall some history, in 2004 Semaev introduced a fundamental new idea for index calculus algorithms for the ECDLP. Fix an elliptic curve over a field . Semaev’s summation polynomials have the property that if for some field elements then there are elliptic curve points on such that .
Gaudry and Diem explored how to use this idea in the context of Weil descent and the ECDLP on elliptic curves over . In particular, Diem showed there exists a sequence of finite fields (not of prime degree) such that the ECDLP along this sequence is provably subexponential. In these cases, the idea is to choose in some dimension subspace of and to write a "random point" as a sum of such points by finding a solution to . One chooses to have a good chance of a relation, in which case one has to solve a system of polynomial equations involving variables and equations.
The main problem is that the summation polynomial has degree in each variable, meaning that after Weil descent the system of equations in a large number of variables has extremely high degree. The difficult case is when is a prime and so one cannot choose the subspace of dimension to be a subfield. There have been a number of recent papers that exploit invariants under group actions to lower the degree, and hence improve these attacks in the case when is prime. I mention just three of these works:
- Jean-Charles Faugere, Pierrick Gaudry, Louise Huot and Guenael Renault, Using Symmetries in the Index Calculus for Elliptic Curves Discrete Logarithm, J. Crypt., Volume 27, Issue 4 (2014) 595-635.
- Yun-Ju Huang, Christophe Petit, Naoyuki Shinohara and Tsuyoshi Takagi, Improvement of Faugere et al.’s Method to Solve ECDLP, in K. Sakiyama and M. Terada (eds.), IWSEC 2013, Springer LNCS 8231 (2013) 115–132.
- Steven D. Galbraith and Shishay W. Gebregiyorgis, Summation polynomial algorithms for elliptic curves in characteristic two, in W. Meier and D. Mukhopadhyay (eds), INDOCRYPT 2014, Springer LNCS 8885 (2014) 409-427.
The challenge in solving large systems of multivariate equations is always the same: How to choose new variables that enable lowering the degree of the system of equations. The simplest of all such ideas is linearisation: replace every monomial with a new variable. The aim is to lower the degree by increasing the number of variables, but hopefully by not introducing too many new variables.
The new idea in the papers by Semaev and Karabina is elegant, natural and simple. The idea is natural when one knows that the summation polynomials are computed recursively by taking resultants. The idea is to “unroll” the resultant computation by introducing new variables for the intermediate points. Putting the idea simply, instead of trying to write for points in the factor base, we write
where the are completely arbitrary points.
Hence, one now has a system of variables and equations, but the equations all have total degree 4 because only has total degree 4. The big question is whether this is a good way to trade-off the number of variables versus degree from the point of view of solving systems of equations. Both the Semaev and Karabina papers give evidence that this choice of variables and equations is easier to solve than previous ones.
So far so good, but now the papers become more speculative. In particular, the papers both assume the “first fall” conjecture of Petit and Quisquater.
Karabina is relatively modest. He suggests taking , with the aim of getting a algorithm that would beat the of Pollard rho (here ). He gives some experimental evidence that the first fall conjecture applies in this case (his data only goes up to n=19 for the case m=5, but this is using rather than the full idea of ). He suggests the algorithm might start to beat rho once .
Semaev is more aggressive in his choice of parameters. He takes growing with , and assumes the first fall conjecture holds in this case. Experimental results are given in the paper, but the largest appears to be 21 and the largest is 6. In my opinion there is insufficient evidence in the paper to support the conjecture as and both grow in the required way. But it is interesting to speculate on how the algorithm might go. For Semaev suggests , giving running time where is the linear algebra constant. The claimed complexity is much better than Pollard rho for such a curve.
However, I note that the storage cost for the matrix representing the system of equations is where is the number of binary variables in the descended polynomial equations. In the case the storage cost is at least bits, which is more than terabytes. To put this in perspective, Avogadro’s constant is about , so storing such a matrix seems way beyond current engineering and so there is no current reason to be concerned about such algorithms. (Francisco Rodriguez-Henriquez pointed out to me that the entire world wide web in 2013 required about 4 zettabytes which is terabytes.) I stress that this matrix needs to be stored as part of the Groebner basis computation for every single relation computation (and this cannot be effectively distributed, as far as we know). The final linear algebra stage is easier.
As an aside, Semaev’s choice of title “New algorithm for the discrete logarithm problem on elliptic curves” seems exaggerated. The title of the paper suggests there is a major new idea, rather than merely an elegant choice of variables for which to implement a known algorithm.
Finally I mention the Kosters-Yeo paper. Section 3 of the paper is about NP-completeness of an elliptic curve version of subset-sum, which is already well-known, see for example the discussion here. Section 4 is more relevant to this blog post as it discusses the first fall conjecture. The paper seems to give evidence that the first fall conjecture is false. It is also notable that this paper reports much larger computations, going as far as , while Karabina and Semaev do not go beyond . If it turns out that the first fall conjecture is false, then there is no reason to believe the claims by Semaev and Karabina that index calculus methods could beat Pollard rho for the ECDLP on binary curves.
One thing is clear, more work needs to be done to evaluate the first fall conjecture and the performance of this class of algorithms. But the current state of knowledge is that there is no serious threat to the ECDLP over binary fields of prime extension degree .
— Steven Galbraith
PS. Semaev has drawn my attention to the revision of his paper on eprint, which now relies on a weaker assumption (Assumption 2). However, I am still of the opinion that there is currently insufficient evidence to support this assumption for the case of very large n.
PPS. This post had around 200 views in its first 17 hours. It is good to know there is a lot of interest in this topic.