eprint 2016/704

Nicolas Courtois has recently uploaded to eprint the paper High Saturation Complete Graph Approach for EC Point Decomposition and ECDL Problem of over 80 pages about ECDLP.

The paper is written in an unusual style. It is a bit like a research notebook, containing sketches of ideas, rather than a polished mathematics paper.

The paper is mainly about the point decomposition problem, which is the fundamental problem behind all recent work on index calculus algorithms (see: these blog
posts). Precisely this problem is: Given a point R and a factor base F write R = P_1 + ... + P_M for P_i \in F.

The standard approach these days is to use summation polynomials: We find solutions x_1,\dots, x_M to the Semaev summation polynomial S_{M+1}( x_1, \dots, x_M, x(R)) = 0 and then compute the corresponding points. Currently these methods have not had any practical impact on the security of elliptic curve cryptography.

The preprint contains several ideas, whose relevance and impact are yet to be fully determined.

One idea is a way to generate a lot of equations without adding too many new variables. Courtois chooses K random elliptic curve points S_1,...,S_K (where K is any natural number) and defines new variables
Z_{i,j} = x( P_i + S_j )
for 1 \le i \le M, 1 \le j \le K.
Courtois then notes that if j_1,...,j_M \in \{1,...,K\} and R = P_1 + ... + P_M then
R + \sum_{i=1}^M S_{j_i} = (P_1 + S_{j_1}) + ... + (P_M + S_{j_M})
Hence we have
S_{M+1} \left( R + \sum_{i=1}^M S_{j_i}, Z_{1,j_1}, ..., Z_{M, j_M} \right) = 0.
There are K^M choices for (j_1,...,j_M), so we get a system of K^M equations in the KM variables Z_{i,j}. On the one hand, we now have a greatly over-determined system, and so it should be easier to solve than traditional systems. On the other hand, the system has too many solutions as the variables Z_{i,j} are unconstrained.

Hence the next problem is to add constraints to the system to reduce the number of solutions. If one can find suitable constraints then one should be able to define a corresponding notion of factor base. Some ideas are sketched in the paper, in particular in Section 18.2, but I have not yet formed an opinion about well these ideas will work. The paper only considers elliptic curves over prime fields \mathbb{F}_p, but similar ideas might be used for curves over other fields.

There are several other ideas in the paper, including some new polynomial equations that might be used to play a similar role to the summation polynomials.

Overall, the paper contains some interesting ideas that are not yet fully developed. Currently the paper does not describe a complete index calculus algorithm and it is difficult for me to determine whether or not the methods are likely to lead to an improvement over existing techniques. No precise complexity statements are made in the paper.

I hope that other researchers will investigate these ideas. I look forward to following the development of work on this topic.

— Steven Galbraith

This entry was posted in Uncategorized. Bookmark the permalink.

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