## ECDLP in less than square-root time

As an apology for my “April Fool’s” blog post, I thought I would present a summary of what is known about algorithms for ECDLP that run in asymptotic time less than the square-root time of Pollard rho.

Let $q = p^n$ and let $E$ be an elliptic curve over $\mathbb{F}_q$. One can solve the ECDLP in $E( \mathbb{F}_q )$ in $O( \sqrt{q} ) = O( p^{n/2} )$ group operations. With large storage this is deterministic and rigorous (baby-step-giant-step algorithm), but requires $O( \sqrt{q} ) = O( p^{n/2} )$ group elements of storage. With Pollard rho the algorithm is randomised and the running time claim is heuristic and average-case, but the storage is low.

Can we do better?

The rest of this article lists some approaches that give ECDLP algorithms with running time better than $O( \sqrt{q} )$ group operations. None of these results are new, and most of them are very well known. None of them have any impact on currently used elliptic curve cryptosystems, so please do not panic. Full details and references can be found in a recent survey paper I wrote with Pierrick Gaudry.

1. One can always “unbalance” the baby-step-giant-step algorithm. By using $O(M)$ precomputation and storage one can solve an instance of the ECDLP in an “online” time of $O( q/M )$ group operations. For example, taking $M = q^{2/3}$ we have an algorithm that solves each individual instance of the ECDLP in $O( q^{1/3} )$ group operations.

This approach is usually completely impractical, especially due to the storage requirement. But the concept can make sense if one is going to be solving a very large number of instances of the ECDLP in the same (relatively small) group, and it demonstrates that the $O( \sqrt{q} )$ bound is not absolute.

2. A similar idea can be done for Pollard rho. The precomputation is still enormous, but at least the storage stays small. Bernstein and Lange have analysed this approach (see the papers Computing small discrete logarithms faster and Non-uniform cracks in the concrete). Bernstein and Lange explain that with $O( q^{2/3} )$ precomputation one has can solve individual ECDLP instances in $O( q^{1/3} )$ group operations.

Again, for practical applications this is not necessarily a serious concern. But in systems where many users work in the same group one should be careful to set security levels that take into account such a scenario (for example, recall the Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice paper, which has too many authors to write down here).

3. Brown-Gallant and Cheon have considered variants of the ECDLP where one is given $P, aP, a^dP$ where $P$ is a point of order $r$ and $d \mid (r-1)$. (I assume that $r \approx q$.) They show one can solve this variant of the ECDLP (i.e., compute $a$) in $O( \max\{ \sqrt{r/d}, \sqrt{d} \} )$ group operations. Taking $d \approx \sqrt{r}$ gives an algorithm with $O( r^{1/4} )$ group operations. There are also algorithms for the case when $d \mid (r+1)$, but they need more intermediate group elements.

These methods require that $r \pm 1$ has a factor of the appropriate size and that auxiliary points such as $a^d P$ are available. Hence, these methods are not a threat to elliptic curve cryptosystems as presently used.

4. Semaev introduced summation polynomials in 2004. Gaudry and Diem were quick to realise that they could be combined with Weil descent. Gaudry focussed on the case of $E( \mathbb{F}_{p^n} )$ where $n$ is fixed and $p$ goes to infinity. His approach, combined with a “double-large-prime” strategy leads to an algorithm with running time $O( p^{2 - 2/n} )$ operations (ignoring log terms). The constant in the running time depends exponentially (at least) in $n$.

Taking $n = 3$ we have an algorithm with running time $O( p^{1.333} )$ operations, which is better than the $O( p^{1.5} )$ operations of Pollard rho, and the gap grows as $n$ grows. Hence, it is well known that one can beat Pollard rho for curves over such fields, at least asymptotically. Due to this algorithm, elliptic curves $E( \mathbb{F}_{p^n} )$ for “intermediate” values of $n$ are no longer used for elliptic curve cryptography.

Returning to my recent hoax: Is there a $O( q^{1/24} )$ ECDLP algorithm? Yes indeed: When $n \ge 47$ then the running time of Gaudry’s algorithm on $E( \mathbb{F}_{p^n} )$ is asymptotically better than $O( p^{n/24} )$. But the constants are terrible and I am confident that no-one is ever going to perform an experiment of Gaudry’s algorithm in $E( \mathbb{F}_{p^{47}} )$ that beats Pollard rho. I also remark that such curves have never been suggested for ECC in practice.

Diem showed an even stronger result: that there are families of finite fields $\mathbb{F}_{p^n}$ for which the ECDLP is subexponential time. But there are no practical implications of this method to elliptic curve cryptosystems.

5. Several recent papers have suggested improved results for ECDLP on elliptic curves over extension fields. These methods are all based on summation polynomials.

The papers about ECDLP in characteristic two have been discussed in these two blog posts. These ideas potentially give some speedups to the summation polynomial algorithms, but there is currently little theoretical or experimental evidence to support these claims. The methods do not apply to elliptic curves over prime fields.

Most recently, the paper Algebraic approaches for the Elliptic Curve Discrete Logarithm Problem over prime fields by Christophe Petit, Michiel Kosters and Ange Messeng was published at PKC 2016. This paper has some interesting and original ideas, and it does apply to elliptic curves over prime fields. But there seem to be no serious implications at present for the use of elliptic curves in practice. From a theoretical point of view, the method is unlikely to perform as well as the methods for characterstic 2 fields (of prime degree), and those methods have not been established yet to beat Pollard rho, so there is currently no evidence that the method in the PKC 2016 paper can beat Pollard rho either. Table 4 of the Petit-Kosters-Messeng paper reports on experiments: the new algorithm solves the ECDLP over a 22-bit finite field in around 5000 seconds, compared with Magma’s implementation of baby-step-giant-step which solves the same problem in 0.01 seconds.

— Steven Galbraith