At the recent Eurocrypt conference there was a paper on the possibility of index calculus in elliptic curves over arbitrary finite fields of characteristic two. The paper is: Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields by Jean-Charles Faugère, Ludovic Perret, Christophe Petit and Guénael Renault.
The algorithm in the paper is based on the idea of a decomposition based index calculus attack. A heuristic analysis presented in the paper gives a (heuristic) upper bound for the running time of the algorithm which is still worse than the running time for a brute force attack (and therefore in particular worse than the time for the rho-method). The paper is however still interesting: First, experimentally, the algorithm seems to perform much better and second, the paper does contain an interesting observation. Will will come to this below.
In addition to this paper, a related paper has recently been uploaded on the IACR archive: On Polynomial Systems Arising from a Weil Descent by Christophe Petit and Jean-Jacques Quisquater. In this work, it is claimed that with a closely related algorithm one can solve the DLP in elliptic curves over F2n, n any natural number in an expected time of exp(O(n(2/3) log(n))). If correct the expected running time would therefore be subexponential in n. This would be a major breakthrough of course.
In this post, I want to evaluate the two papers. For this, and also because it has not been done yet in this entry, I am first going to give some background on the idea of decomposition based index calculus algorithms.
To put the new works into perspective, I now give some information on the historical background of the approach.
It can justifiably be said that it all started with a talk by Gerhard Frey at the ECC conference of 1998. At this conference, he first pointed out the following:
Let K|k be an extension of finite fields of degree n, and let E be an elliptic curve over K. Then we can associate to E/K an n-dimensional variety W over k with the following interesting properties:
– There is a canonical group isomorphism between E(K) and W(k).
– W has a “geometric group law”, that is a group law defined by polynomials.
– W can be embedded in projective space.
– Regarded as a variety over K, W splits into a product of elliptic curves one of which is E itself. (This is however not true over k!)
By the way: A variety which can be embedded in projective space and which has a geometric group law is called an abelian variety, so W is an abelian variety. It is called the Weil restriction of E with respect to K|k.
If one starts with an elliptic curve given by an explicit affine equation, one can easily obtain a system of affine equations which define an affine part of W. The essential idea is to “expand the equations” over k. This process of “expansion” works for any field finite field extension K|k and any variety over K. I describe it here by an example which is slightly easier to state:
Let us consider the hyperbola H given by the equation x2 – y2 -1 = i over the complex numbers, where i2 = -1. We want to perform the expansion with respect to the extension C|R. We “expand” the variables: x = x1 + i x2 and y = y1 + i y1, where the new variables only take real values. Then the defining equation is equivalent to:
(x1 + i x2)2 – (y1 + i y2)2 = i.
This is equivalent to the system of equations
x12 – x12 – y12 + y12 = 0 , 21x2 – 2y1 y1 = 1.
So, if we define W as the variety over R given by these equations, we obviously have a bijection between H(C), the solutions to the original equation over C, with W(R), the solutions of the system of equations over R.
The very general observation by Frey was: Given that the Weil restriction of an elliptic curve is a higher-dimensional variety, one might use some geometric construction to attack the DLP in the elliptic curve. Concretely he proposed: Find a curve on the Weil restriction, map the DLP to the degree 0 divisor class group of the curve and solve it there by index calculus methods.
A requirement in order that this idea can be carried out is that one finds in an explicit way a curve of rather low genus as otherwise the index calculus method cannot be applied successfully. This lead to the so-called GHS attack, where G stands for Pierrick Gaudry, H for Florian Hess and S for Nigel Smart. They focused on elliptic curves over F2n. For some parameters, for example for some elliptic curves n=127 they indeed found curves of very low genus on the Weil restriction. This was a major breakthrough.
One aspect of their approach is of interest here: They found the curves by intersecting the Weil restriction with hyperplanes. Briefly, this intersection V can be described as follows: Instead of expanding the x- and y-coordinate of points on the elliptic curve, one just expands the y-coordinates. One then has one variable for the x-coordinates and n variables for the y-coordinates. Like this, one obtains a 1-dimensional variety V in the Weil restriction whose points correspond to the points in E whose x-coordinate lies in k or is ∞.
Now, this intersection might contain several “components”. The really interesting curves can be found if the intersection splits into very many components and if one of the components is defined over k, the small field. However, for many (more accurately: for most) natural numbers n there are not enough components, the genera of the curves are two high. Moreover it turns out that in odd characteristic the situation is even worse, and here the obvious variant of the GHS attack clearly fails if n is prime and at least 11. An interesting aspect of the GHS attack and its obvious variants is that it can be formulated without even mentioning the Weil restriction: One just needs function fields in one variable.
The next step of the development was initiated by a paper by Igor Semaev: Summation polynomials and the discrete logarithm problem on elliptic curves, uploaded to the IACR server in 2004. Semaev presents some ideas for index calculus in elliptic curves over prime fields. If these will ever lead to an interesting result is a wide open problem. They highlighted however that it might be possible to apply an index calculus algorithm in elliptic curves themselves.
And this lead to a work by Pierrick Gaudry: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. The main idea is here: Let’s use the set of points of E with x-coordinate in k as a factor base. Note that this set corresponds to the points in V(k) as defined above. Then one can generate relations by solving systems of equations over k. To obtain these systems, one can use the so-called summations polynomials which were also introduced by Semaev. These polynomials indicate if n points on an elliptic curve add up to zero. Just as in the construction of the Weil restriction, one expands such a summation polynomial, obtaining a system of non-linear polynomial equations over k. And then one solves this system, for example with a Gröbner base method. The complexity to solve such a system can be described as “horrible” for growing “n”. (It is exponential in n and quickly becomes infeasible in practice.) However, for constant n the complexity is polynomial in the field size, thus very good (from an asymptotic point of view). As described, one can solve the DLP in elliptic curves over Fqn with fixed n in an expected time of O(q2) with this method. By decreasing the factor base, one can obtain an even better expected running time.
I have also made some contributions here. I realized this: Let us consider the DLP in elliptic curves over Fqn, and let us grow q and n at the same time. Then solving the systems of equations, even though “horrible”, might still lead to a subexponential expected running time. I have two works on this: On the discrete logarithm problem in elliptic curves and its successor On the discrete logarithm problem in elliptic curves II. In the first work, I use exactly the factor base described above. In the second work, I increase the factor base. I prove with a corresponding algorithm that under some restriction on q and n, one can obtain a subexponential expected running time. The best expected running time I obtain is for a · (log(q))1/2 ≤ n ≤ b · log(q)1/2 for some constants a,b >0. For this range of q and n, the expected running time is exp(O(log(qn))2/3).
The new works
After this historical excursion I now come to the new papers. Both works are closely related to my article “On the discrete logarithm problem in elliptic curve II”.
In the two works, the factor base is now defined by an n’-dimensional variety, where n’ is between 1 and n. One sets m to be about n/n’, and for a given point P, which is a given combination of the input elements, one searches for a relation of the form P1 + … + P m = P with Pi in the factor base.
By the structure of the systems of equations, one can expect that one can solve one system in a time of exp(O(mn)) · log(q)O(1). (A rigorous variant of this statement is employed in my works.) The two papers we are concerned with here deal with the DLP in elliptic curves in characteristic 2. So, here one wants to solve systems over F2. Now for a system in n variables x1, …, xn over F2, one also has the “field equations” xi2 = xi. These can be inserted into the system. Another description of the same observation is: We want to solve a system of equations over a boolean ring instead of a polynomial ring. The big question is now this:
What happens to the complexity if we insert the field equations?
One answer to this question was given in Bardet, Faugere, Salvy, Yang in Asymptotic Behavior of the Degree of Regularity of Semi-Regular Polynomial Systems (MEGA 2005). On the basis of some heuristic arguments it is argued in this paper that for “most systems”, the complexity drops, but it does not drop in a dramatic way.
Now, the new papers give some indication that for the particular systems employed here the drop is more dramatic. Let us first discuss the paper presented at Eurocrypt: As said the analysis is heuristic, but the authors were very careful to make no unfounded claims. There is a parameter, α in the paper, and one has n’ =α, m=n1-α. The system solving relies on a dedicated method for the particular systems.
In the heuristic analysis it is assumed that α ≥ 1/2. The analysis then indicates that independently of α the complexity to solve one system with the given method is upper bounded by 2ω/2 · n, where ω is the constant for the linear algebra. This heuristic upper bound for the complexity just to solve one system of equations is worse than the complexity for a brute force attack on the DLP. In fact, it is even worse than the time needed to solve one system by brute force. This is clearly disappointing. On the other hand the result holds independent of α. And clearly, it is much better than the bound exp(O(mn)) which holds without any assumption. And it is important to note that it is, well, an upper bound.
The total expected running time is then minimized if the factor base is minimized, and this is the case for α = 1/2. The total expected running time is then 2(ω/2 +o(1)) · n. Of course, this is not yet a major breakthrough to the ECDLP in characteristic 2. In fact, it is not even a minor breakthrough. But nonetheless the paper is interesting and might lead to further developments.
In the second paper a more bold assumption is made. On the basis of this assumption, the subexponential expected running time indicated in the beginning is obtained. The assumption can be stated as follows: Usually, in the application of Gröbner base algorithms like F4 employed with a “normal” strategy (“normal” is a technical term here, it means that one always considers the S-polynomials of smallest degree), one sees the following: If the degree drops during the computation for the first time, the highest degree is not much higher than this degree. This observation clearly holds for most randomly generated systems, and there are strong heuristic arguments why it should hold for such systems.
Now, in this paper it is observed that one has a degree drop almost immediately, so if one makes the indicated assumption, one obtains a very favorable expected running time. The big question is here of course if the assumption does hold for the special systems used here. Experiments are reported which assert that the assumption is correct. It is however very difficult to conduct experiments, and therefore the parameters are quite small in the experiments. All in all it is not clear whether the assumption holds. It might hold or it might not. Maybe it fails but a weaker statement holds. This is all very unclear at the present time.
In conclusion, we have here interesting works on the ECDLP in characteristic 2 (and possibly also in other small characteristic). Both works show that the field of solving systems of equations over small fields is of great relevance for the security of elliptic curve cryptography over such fields. And both works indicate that the particular systems obtained by the summation polynomials might be easier so solve than “random” systems.
Further progress might come from applying different and maybe more dedicated algorithms to the particular systems.
Even if some of the heuristic assumptions can be removed or at least supported by stronger arguments, there is still the question of applicability. My personal opinion is that it should be really hard to make the ideas of the two papers practical. Clearly there is no immediate threat to ECC in small characteristic.
So there is still a lot of work to be done here. Of course this is a buzzword. But still, it’s true – as always of course.
– Claus Diem