eprint 2016/003 by Nicolas Courtois

Nicolas Courtois has posted the paper On Splitting a Point with Summation Polynomials in Binary Elliptic Curves on eprint. The original paper is from January 3rd, but it was updated on January 4 and again on January 5. Probably there will be further updates in the future.

The paper ends with the strong statement “Our conjecture is however that there exists an algorithm for solving the full DL problem on binary elliptic curves with running time of order of 2^{n/3}.”

The context of the paper is index calculus algorithms for the ECDLP. The basic problem in these algorithms is writing an arbitrary point R as a sum P_1 + \cdots + P_k of points that all lie in some “factor base”. This is sometimes called “splitting” a point or “decomposing” a point. The recent work in this area, as summarised in these blog posts, is based on Semaev’s summation polynomials, Weil descent, and Groebner basis algorithms. A problem with this approach is that it is very hard to determine the asymptotic running time of the Groebner basis algorithms, in part because the memory costs are enormous.

This idea does not apply to elliptic curves over prime fields \mathbb{F}_p, and the security of these curves is not affected by any work in this area. For elliptic curves over extension fields \mathbb{F}_{p^n}, for certain values of n, this approach can definitely lead to a faster algorithm than Pollard rho.
However one particularly awkward case is elliptic curves over \mathbb{F}_{2^n} where n is prime, and it is still an open question whether the ECDLP can be solved faster than Pollard rho for such curves. The situation was recently surveyed by Pierrick Gaudry and myself.

Rather than using Groebner basis methods, Nicolas Courtois considers a different approach to solving the point decomposition problem. His approach combines exhaustive search with solving linear equations. To demonstrate the applicability of this idea he gives methods to decompose points as a sum of 2 or 3 points. I have not had time to check the technical parts of the paper in detail yet, but the methods seem to be practical and do not require very large amounts of memory. This work gives insight into the potential for such techniques as part of an index calculus algorithm, and it will be very interesting to see how these ideas develop for decompositions into sums of 4 or more points.

The proposed decomposition algorithms all run in exponential time (e.g., 2^{n/3} steps). It is not immediately clear (to me anyway) that the problem of decomposing a point into a sum of 2 or 3 points should be hard. There is not a direct relationship between point decomposition and ECDLP. For example, if one is given an ECDLP oracle then I don’t see how to use it to solve point decomposition efficiently. So ECDLP could be easy and yet point decomposition hard. On the other hand, decomposing a point as a sum of two points in a factor base of size 2^{n/2} could be polynomial-time and yet, due to the size of the factor base and the cost of the linear algebra stage, the index calculus algorithm would still be slower than Pollard rho.

The paper makes two claims as a consequence of the decomposition algorithms:

  1. Violation of the ideal group model for binary curves.

    The author suggests that his results already show that elliptic curves do not behave like “ideal groups”. In my opinion, it is unclear how to formalise the point decomposition problem in terms of generic algorithms. I tend to think of the generic group model as a “representation independent” model. A generic algorithm has access to group operations and nothing more. A factor base is not a “generic” object, as it depends on the representation. So I am not sure that this comment really has any meaning.

  2. Conjecture of a cube-root-time algorithm for ECDLP on binary elliptic curves.

    It would be very interesting if this claim is true, and I look forward to the future research on this topic. It is certainly an important and interesting problem to consider new approaches to the point decomposition problem.

    At the moment however, there is no evidence to support the claim. The January 5 version of the paper has three decomposition methods.
    The first decomposes to points in a factor base of size 2^{n/2} and so an index calculus algorithm based on this method would have storage cost proportional to 2^{n/2} and be slower than baby-step-giant-step and Pollard rho.
    The second method decomposes in time O( 2^{n/3} ) into a sum of three points in a factor base of size 2^{n/3}. Since we need O( 2^{n/3} ) relations we need to perform the decomposition method O( 2^{n/3} ) times, giving a total complexity of O( 2^{2n/3} ) to solve an instance of the ECDLP, which is worse than Pollard rho.
    The final proposal is an algorithm to decompose a point as a sum of two points in a factor base of size 2^{n/3} and again the decomposition takes time O( 2^{n/3} ), giving an algorithm to solve ECDLP with time O( 2^{2n/3} ).

I conclude by re-stating that it is an important and interesting problem to consider algorithms for the point decomposition problem that are not based on Groebner basis method. The new ideas by Courtois are to be welcomed, and I look forward to future work on this problem.

— Steven Galbraith

This entry was posted in Uncategorized. Bookmark the permalink.

1 Response to eprint 2016/003 by Nicolas Courtois

  1. Pingback: ECDLP in less than square-root time | ellipticnews

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s