## 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.