Rigorous complexity of index calculus for the elliptic curve discrete logarithm problem over fixed small-degree extension fields

Gaudry's index calculus for abelian varieties of small dimension (2009) yields, via Weil restriction, an attack on the elliptic curve discrete logarithm problem (ECDLP) over $\mathbb{F}_{q^n}$ whose claimed cost $\tilde{O}(q^{2-2/n})$ for fixed extension degree $n\ge 3$ beats the generic $\tilde{O}(q^{n/2})$ of Pollard's rho method - but the bound is explicitly heuristic, resting on unproven assumptions about the genericity of the hyperplane-section factor base, the $1/n!$ decomposition probability of random points, the polynomial-in-$\log q$ Groebner-basis solving of the symmetrized Semaev summation-polynomial systems (whose degrees grow like $2^{n(n-1)}$ in $n$), and the double-large-prime relation-elimination combinatorics. Later literature rigorized the picture only when the extension degree grows with $q$ (Diem's unconditional subexponential algorithms), sharpened but did not settle the Groebner-degree heuristics (the first-fall-degree conjectures, partly doubted), and found no practical crossover with Pollard rho. The open problem is to determine the true fixed-$n$ complexity: prove the heuristic bound - or any unconditional exponent below $n/2$ - for the ECDLP over $\mathbb{F}_{q^n}$, or prove that one of its load-bearing heuristics fails on an explicit family of inputs.

Background

The elliptic curve discrete logarithm problem (ECDLP) asks, given points $P$ and $Q$ on an elliptic curve $E$ over a finite field with $Q$ in the cyclic subgroup generated by $P$, for an integer $a$ with $Q=aP$. An elliptic curve is a smooth projective curve of genus 1 whose rational points carry an abelian group law, and the ECDLP is the security foundation of elliptic-curve cryptography. In a group of size $N$, generic collision-search algorithms - most prominently Pollard's rho method, which wanders pseudo-randomly through the group until two walks collide - solve the problem in expected time about $\sqrt{N}$, and no generic algorithm can do asymptotically better.

Index calculus beats generic algorithms in groups like $\mathbb{F}_p^*$ by writing random group elements as products of elements of a small 'factor base', collecting multiplicative 'relations', and solving a linear system; no factor base with the required structure is known for elliptic curves over prime fields. Semaev (2004) proposed one: the $m$-th summation polynomial $S_m$ of $E$ satisfies $S_m(x_1,\dots,x_m)=0$ exactly when there are points $P_i=(x_i,y_i)$ on $E$ with $P_1+\cdots+P_m=0$; $S_m$ is symmetric and has degree $2^{m-2}$ in each variable. Gaudry (2009) turned this into a general index calculus for the discrete logarithm problem on any abelian variety $A$ of dimension $n$ over $\mathbb{F}_q$ (an abelian variety is a projective algebraic group; elliptic curves and Jacobians of curves - the divisor-class groups representing curve points - are the main examples) given in an explicit coordinate representation. After a random linear change of coordinates, the factor base $\mathcal{F}$ is the set of $\mathbb{F}_q$-rational points of $A$ lying in $n-1$ coordinate hyperplanes - an algebraic curve expected to have about $q$ points - and a relation is a decomposition $aP+bQ=P_1+\cdots+P_n$ with all $P_i$ in $\mathcal{F}$.

Applied to the Weil restriction of an elliptic curve over an extension field (Weil restriction 'descends' $E/\mathbb{F}_{q^n}$ to an abelian variety of dimension $n$ over $\mathbb{F}_q$; the factor base becomes the points of $E(\mathbb{F}_{q^n})$ whose $x$-coordinate lies in $\mathbb{F}_q$), and with the $y$-coordinates eliminated using Semaev's polynomials, each decomposition attempt becomes a system of $n$ polynomial equations over $\mathbb{F}_q$ in $n$ elementary-symmetric unknowns, solved by a Groebner basis computation - the standard commutative-algebra tool that triangularizes polynomial systems, whose cost is governed by the largest polynomial degree reached during the computation (the 'degree of regularity'). Gaudry's Heuristic Result 4 states that for each fixed $n\ge 2$ the ECDLP over $\mathbb{F}_{q^n}$ is solvable in heuristic time $\tilde{O}(q^{2-2/n})$ - for example $\tilde{O}(q^{4/3})$ over $\mathbb{F}_{q^3}$, versus $\tilde{O}(q^{n/2})$ for Pollard's rho - after a large-prime variant (Thériault's large-prime variation, refined to the double-large-prime trick by Gaudry, Thomé, Thériault and Diem) splits off part of the factor base as 'large primes' and eliminates them pairwise, rebalancing the $\tilde{O}(q)$ relation search against the $\tilde{O}(q^2)$ sparse linear algebra.

The claimed complexity is explicitly heuristic, resting on four unproven assumptions. (i) Genericity: after the random coordinate change, the factor-base curve is, with high probability, absolutely irreducible and not contained in a proper abelian subvariety, with $\#\mathcal{F}(\mathbb{F}_q)=q+O(\sqrt q)$ points - Bertini-type irreducibility theorems hold over algebraically closed fields, not finite fields, so no proof is available. (ii) Decomposition probability: a random group element is a sum of $n$ factor-base points with probability asymptotic to $1/n!$. (iii) System solving: the symmetrized systems are solvable in time polynomial in $\log q$ with a constant depending only on the family - while the systems' generic degrees explode with $n$ (equations of degree up to $2^{n-1}$, final univariate elimination of degree about $2^{n(n-1)}$), so beyond generic degree counting nothing is proven about the Groebner complexity for these structured systems. (iv) Large primes: the double-large-prime elimination behaves like an idealized random combinatorial process. The analysis is also restricted to families where the dimension $n$, the number of auxiliary coordinates, and the defining-equation degrees are uniformly bounded; the paper estimates that for $n=3$ the method overtakes Pollard's rho only beyond $q\approx 2^{65}$.

The heuristic is known to be partly vindicated in a different asymptotic regime: Diem proved unconditionally that the ECDLP over $\mathbb{F}_{q^n}$ is solvable in subexponential expected time whenever $n\to\infty$ with $n/\log q\to 0$ (2011), and later for $n/\log^2 q\to 0$ and for intermediate ranges $a\log^{1/3}q\le n\le b\log q$ (2013). But those algorithms and analyses are tailored to growing $n$; for fixed small $n$ they yield only an unspecified polynomial $q^{O(1)}$ bound that neither recovers the exponent $2-2/n$ nor beats Pollard's $q^{n/2}$. A 2015 survey by Galbraith and Gaudry records the state of the art: for fixed $n$ the $\tilde{O}(q^{2-2/n})$ bound is still a heuristic, the Groebner-complexity assumptions (such as the first-fall-degree assumption, an often-observed but unproven proxy for the degree of regularity) remain unsettled and contested, and none of the approaches is practical at cryptographic sizes. Whether the fixed-degree complexity can be proven at all - or whether some heuristic genuinely fails - is the open problem stated below.

Problem Statement

Determine the true asymptotic complexity of the ECDLP over $\mathbb{F}_{q^n}$ for fixed extension degree $n\ge 3$ by proving or refuting Gaudry's heuristic index-calculus claim. Concretely: prove, or disprove, that for each fixed $n\ge 3$ there is a randomized index-calculus algorithm which, given any elliptic curve $E$ over $\mathbb{F}_{q^n}$ (in Weierstrass form) and any instance $Q=aP$ in $E(\mathbb{F}_{q^n})$, computes $a$ in expected time $\tilde{O}(q^{2-2/n})$ as $q\to\infty$, uniformly over all curves in the family. The four ingredients below are the load-bearing heuristics of that one algorithm and jointly support this single complexity theorem; a complete affirmative answer must replace each by an unconditional statement:

(1) after the algorithm's random linear change of coordinates, the factor base is, with probability bounded away from $0$, an absolutely irreducible curve not contained in any proper abelian subvariety of the Weil restriction, with $\#\mathcal{F}(\mathbb{F}_q)=q+O(\sqrt q)$ rational points;

(2) a uniformly random element of $E(\mathbb{F}_{q^n})$ admits a decomposition into $n$ factor-base points with probability asymptotic to $1/n!$;

(3) the symmetrized Weil-restricted Semaev system defining the decomposition is solvable in time polynomial in $\log q$, with a constant depending only on $n$ - in particular, a proven bound on the degree of regularity (equivalently the first or last fall degree) for these structured systems, in place of the current degree-counting heuristics;

(4) the double-large-prime elimination step produces a full-rank relation system within the claimed time bound.

An unconditional proof that for fixed $n\ge 3$ some, possibly different, algorithm solves the ECDLP over $\mathbb{F}_{q^n}$ in expected time $\tilde{O}(q^c)$ with any proven exponent $c<n/2$ equally resolves the scientific question of whether index calculus provably beats generic algorithms in the fixed-degree regime. A disproof must exhibit an explicit infinite family of inputs on which one of the load-bearing heuristics fails asymptotically - for example families where every coordinate randomization yields a degenerate factor base, or where the decomposition probability is asymptotically smaller than $1/n!$, or where the systems' solving degree grows without bound in $\log q$ - together with a proof that this failure invalidates the claimed complexity. Taming the degree explosion $2^{n(n-1)}$ in $n$ is part of the question to the extent it is required for (3). The same question may be posed, more broadly, for the general abelian-variety setting of Gaudry's Heuristic Result 3 and for families whose representation parameters are not uniformly bounded; the fixed-$n$, bounded-parameter elliptic-curve case above is its sharp core. The purely practical crossover with Pollard's rho at cryptographic sizes is an engineering matter tracked in the literature and is not part of the mathematical completion boundary.

References

1. Pierrick Gaudry, 'Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem', Journal of Symbolic Computation 44(12):1690-1702, 2009. DOI: 10.1016/j.jsc.2008.08.005, https://doi.org/10.1016/j.jsc.2008.08.005
2. Igor Semaev, 'Summation polynomials and the discrete logarithm problem on elliptic curves', IACR Cryptology ePrint Archive 2004/031, 2004. https://eprint.iacr.org/2004/031
3. J. M. Pollard, 'Monte Carlo methods for index computation (mod p)', Mathematics of Computation 32:918-924, 1978. DOI: 10.1090/S0025-5718-1978-0491431-9, https://doi.org/10.1090/S0025-5718-1978-0491431-9
4. Nicolas Thériault, 'Index calculus attack for hyperelliptic curves of small genus', Advances in Cryptology - ASIACRYPT 2003, Lecture Notes in Computer Science, pp. 75-92, 2003. DOI: 10.1007/978-3-540-40061-5_5, https://doi.org/10.1007/978-3-540-40061-5_5
5. Pierrick Gaudry, Emmanuel Thomé, Nicolas Thériault, Claus Diem, 'A double large prime variation for small genus hyperelliptic index calculus', Mathematics of Computation 76(257):475-492, 2007. DOI: 10.1090/S0025-5718-06-01900-4, https://doi.org/10.1090/S0025-5718-06-01900-4
6. Claus Diem, 'On the discrete logarithm problem in elliptic curves', Compositio Mathematica 147(1):75-104, 2011. DOI: 10.1112/S0010437X10005075, https://doi.org/10.1112/S0010437X10005075
7. Claus Diem, 'On the discrete logarithm problem in elliptic curves II', Algebra & Number Theory 7(6):1281-1323, 2013. DOI: 10.2140/ant.2013.7.1281, https://doi.org/10.2140/ant.2013.7.1281
8. Song Tian, Kunpeng Wang, Bao Li, Wei Yu, 'A Note on Diem's Proof', Information Security and Cryptology (Inscrypt 2014), Lecture Notes in Computer Science, pp. 463-471, 2015. DOI: 10.1007/978-3-319-16745-9_25, https://doi.org/10.1007/978-3-319-16745-9_25
9. Antoine Joux, Vanessa Vitse, 'Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields', Journal of Cryptology 26(1):119-143, 2013 (online 2011). DOI: 10.1007/s00145-011-9116-z, https://doi.org/10.1007/s00145-011-9116-z
10. Steven D. Galbraith, Pierrick Gaudry, 'Recent progress on the elliptic curve discrete logarithm problem', Designs, Codes and Cryptography 78(1):51-72, 2016 (survey, online 2015). DOI: 10.1007/s10623-015-0146-7, https://doi.org/10.1007/s10623-015-0146-7 (also IACR ePrint 2015/1022, https://eprint.iacr.org/2015/1022)
11. Jean-Charles Faugère, Ludovic Perret, Christophe Petit, Guénaël Renault, 'Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields', Advances in Cryptology - EUROCRYPT 2012, Lecture Notes in Computer Science, pp. 27-44, 2012. DOI: 10.1007/978-3-642-29011-4_4, https://doi.org/10.1007/978-3-642-29011-4_4
12. Jean-Charles Faugère, Pierrick Gaudry, Louise Huot, Guénaël Renault, 'Using Symmetries in the Index Calculus for Elliptic Curves Discrete Logarithm', Journal of Cryptology 27(4):595-635, 2014 (online 2013). DOI: 10.1007/s00145-013-9158-5, https://doi.org/10.1007/s00145-013-9158-5
13. Steven D. Galbraith, Shishay W. Gebregiyorgis, 'Summation Polynomial Algorithms for Elliptic Curves in Characteristic Two', Progress in Cryptology - INDOCRYPT 2014, Lecture Notes in Computer Science, pp. 409-427, 2014. DOI: 10.1007/978-3-319-13039-2_24, https://doi.org/10.1007/978-3-319-13039-2_24 (also IACR ePrint 2014/806, https://eprint.iacr.org/2014/806)
14. Christophe Petit, Jean-Jacques Quisquater, 'On Polynomial Systems Arising from a Weil Descent', IACR Cryptology ePrint Archive 2012/146, 2012. https://eprint.iacr.org/2012/146
15. Igor Semaev, 'New algorithm for the discrete logarithm problem on elliptic curves', arXiv:1504.01175, 2015. https://arxiv.org/abs/1504.01175 (also IACR ePrint 2015/310)
16. Yun-Ju Huang, Christophe Petit, Naoyuki Shinohara, Tsuyoshi Takagi, 'On Generalized First Fall Degree Assumptions', IACR Cryptology ePrint Archive 2015/358, 2015. https://eprint.iacr.org/2015/358
17. Michiel Kosters, Sze Ling Yeo, 'Notes on summation polynomials', arXiv:1503.08001, 2015. https://arxiv.org/abs/1503.08001
18. Stavros Kousidis, Andreas Wiemers, 'On the first fall degree of summation polynomials', Journal of Mathematical Cryptology 13(3-4):229-237, 2019. DOI: 10.1515/jmc-2017-0022, https://doi.org/10.1515/jmc-2017-0022 (also arXiv:1906.05594, https://arxiv.org/abs/1906.05594)
19. Ming-Deh A. Huang, Michiel Kosters, Yun Yang, Sze Ling Yeo, 'On the last fall degree of zero-dimensional Weil descent systems', arXiv:1505.02532, 2015. https://arxiv.org/abs/1505.02532
20. Gary McGuire, Daniela Mueller, 'A New Index Calculus Algorithm for the Elliptic Curve Discrete Logarithm Problem and Summation Polynomial Evaluation', IACR Cryptology ePrint Archive 2017/1262, 2017. https://eprint.iacr.org/2017/1262
21. Monika Trimoska, Sorina Ionica, Gilles Dequen, 'A SAT-based approach for index calculus on binary elliptic curves', IACR Cryptology ePrint Archive 2019/313, 2019 (last updated 2020). https://eprint.iacr.org/2019/313
22. Robert Granger, Frederik Vercauteren, 'On the Discrete Logarithm Problem on Algebraic Tori', Advances in Cryptology - CRYPTO 2005, Lecture Notes in Computer Science, pp. 66-85, 2005. DOI: 10.1007/11535218_5, https://doi.org/10.1007/11535218_5
23. Koh-ichi Nagao, 'Decomposed Attack for the Jacobian of a Hyperelliptic Curve over an Extension Field', IACR Cryptology ePrint Archive 2007/112, 2007. https://eprint.iacr.org/2007/112
24. Roger Oyono, Nicolas Thériault, 'Index calculus algorithm for non-planar curves', Finite Fields and Their Applications 90:102227, 2023. DOI: 10.1016/j.ffa.2023.102227, https://doi.org/10.1016/j.ffa.2023.102227
25. David R. Kohel, Igor E. Shparlinski, 'On Exponential Sums and Group Generators for Elliptic Curves over Finite Fields', Algorithmic Number Theory (ANTS-IV), Lecture Notes in Computer Science, pp. 395-404, 2000. DOI: 10.1007/10722028_24, https://doi.org/10.1007/10722028_24
26. Jianjun Hu, 'A New Method for Solving Discrete Logarithm Based on Index Calculus', IACR Cryptology ePrint Archive 2025/015, 2025. https://eprint.iacr.org/2025/015