Degree of regularity of Weil-descent systems from Semaev summation polynomials: does $D_{reg}=m^2-m+1+o(1)$?

The index-calculus approach to the elliptic curve discrete logarithm problem (ECDLP) over binary fields $\mathbb{F}_{2^n}$ reduces its point-decomposition step to Gröbner-basis solving of the polynomial system obtained by Weil descent of Semaev's $(m+1)$-th summation polynomial along a factor-base subspace. The cost of that step is governed by the degree of regularity $D_{reg}$, while everything actually proven concerns the first fall degree $D_{ff}$: Kousidis and Wiemers proved $D_{ff}\le m^2-m+1$ for all $m\ge 3$ and asked (their Equation (4.1)) whether $D_{reg}=m^2-m+1+o(1)$ as $n\to\infty$ in the index-calculus parameter regimes — the sharpened form of Petit–Quisquater's first-fall-degree assumption. The question is open in both directions: no unconditional lower bound on $D_{reg}$ for these systems is known beyond the generic $D_{ff}\le D_{reg}$ heuristic, sharpness of the $D_{ff}$ bound for $m\ge 3$ is conjectural, and the $m=2$ case already exhibits a $D_{reg}-D_{ff}$ gap that grows with $n$. No resolution is known in the literature to date. The answer determines whether the subexponential complexity of binary-field ECDLP index calculus can be made unconditional, or whether the underlying heuristic fails.

Background

The elliptic curve discrete logarithm problem (ECDLP) asks, given points $P$ and $Q=kP$ on an elliptic curve $E$ over a finite field, to recover the integer $k$. For generic curves no subexponential algorithm is known, and ECDLP hardness underpins elliptic-curve cryptography. Over binary fields $\mathbb{F}_{2^n}$, an index-calculus attack was proposed by Semaev (2004) and developed by Gaudry, Diem, Petit–Quisquater and others: fix a factor base, i.e. a linear subspace $W\subseteq\mathbb{F}_{2^n}$ of dimension $n'$, and search for decompositions of the target point $R$ as a sum $P_1+\cdots+P_m$ of points whose $x$-coordinates lie in $W$. Each decomposition yields a linear relation among logarithms; sufficiently many relations solve the ECDLP by linear algebra.

Semaev's summation polynomials make decomposition algebraic: $S_{m+1}(x_1,\ldots,x_{m+1})$ vanishes exactly when there exist points on $E$ with those $x$-coordinates summing to zero. Substituting $x_i=\sum_j y_{ij}\nu_j$ with respect to an $\mathbb{F}_2$-basis $\nu_1,\ldots,\nu_{n'}$ of $W$, fixing $x_{m+1}=c$ (an $x$-coordinate of the target), and expanding over a basis $1,z,\ldots,z^{n-1}$ of $\mathbb{F}_{2^n}$ produces $n$ polynomials $s_0,\ldots,s_{n-1}$ in the $mn'$ variables $y_{ij}$ (a Weil descent, i.e. a restriction of scalars from $\mathbb{F}_{2^n}$ to $\mathbb{F}_2$), taken modulo the field equations $y_{ij}^2=y_{ij}$ that express Boolean values.

The bottleneck is the Gröbner basis computation — computing a Gröbner basis, a canonical generating set of the ideal spanned by the system from which the solutions are recovered, by Faugère's F4/F5 algorithms, which organize the computation as exact linear algebra on large matrices of polynomial multiples. Its cost is governed by the degree of regularity $D_{reg}$ — in this literature, the highest step degree reached during the Gröbner basis computation; roughly, the cost behaves like $(mn')^{\omega D_{reg}}$ with $\omega$ the linear-algebra exponent. Predicting $D_{reg}$ is intractable in general, so practitioners use the first fall degree $D_{ff}$ (formalized by Hodges–Petit–Schlather): the smallest degree at which nontrivial algebraic combinations of the system produce a polynomial of strictly lower degree. Generically $D_{ff}\le D_{reg}$, and the first fall degree assumption (Petit–Quisquater's Assumption 2) asserts $D_{reg}=D_{ff}+o(1)$. Under it, Petit–Quisquater derived a subexponential complexity $O(2^{c\log(n)(n^{2/3}+1)})$ for binary-field ECDLP with $m\approx n^{1/3}$, $n'\approx n^{2/3}$, $c=2^{\omega/3}$, beating generic $O(2^{n/2})$ algorithms for $n$ beyond roughly 2000 — conditional entirely on that assumption.

Kousidis and Wiemers improved the proven first fall degree bound for the Weil-descended Semaev systems from $D_{ff}\le m^2+1$ (Petit–Quisquater, via Hodges–Petit–Schlather) to $D_{ff}\le m^2-m+1$ for all $m\ge 3$, by identifying the highest-degree homogeneous part of the system: it is induced by the monomial $(x_1\cdots x_m)^{2^{m-1}-1}\cdot x_{m+1}$ of $S_{m+1}$ and has degree $m^2-m$ in the Boolean variables, so a fall occurs at latest one degree higher. They conjecture this bound is sharp for $m\ge 3$ but do not prove it. Their experiments (the F4 implementation of the Magma computer algebra system, on random ordinary — i.e. non-supersingular — curves and random factor bases) show $D_{ff}=D_{reg}=7$ for $m=3$ up to $n=21$ and $D_{ff}=D_{reg}=13$ for $m=4$ up to $n=16$; computations for $m\ge 3$ are blocked by time and memory. The case $m=2$ is different and cautionary: Kosters and Yeo proved that the Weil descent of $S_3$ has $D_{ff}=2$ for ordinary curves (a linear relation induced by the field trace — the map $\mathrm{Tr}:\mathbb{F}_{2^n}\to\mathbb{F}_2$ with $\mathrm{Tr}(x)=x+x^2+x^4+\cdots+x^{2^{n-1}}$ — forces an immediate fall), while the observed $D_{reg}$ climbs with $n$ (4 for $17\le n\le 36$, at least 5 from $n\approx 37$), so the gap $D_{reg}-D_{ff}$ appears to depend on $n$.

Two theoretical programs border the question without settling it. The last fall degree framework of Huang–Kosters–Yang–Yeo proves that Gröbner computations terminate at the last fall degree and bounds it independently of $n$ for zero-dimensional Weil descent systems (systems with only finitely many solutions; this suffices to rigorously break HFE-type schemes — HFE, Hidden Field Equations, is a multivariate public-key cryptosystem), but the summation-polynomial systems without field equations are not zero-dimensional, so the method does not apply; those authors explicitly warn that the degree of regularity of these systems might depend on $n$. Huang–Petit–Shinohara–Takagi showed that generalized first-fall-degree assumptions hold in some parameter regimes (with practical timing gains) while in others they would imply polynomial-time Gröbner solutions of NP-complete problems, which they consider very unlikely. What remains unresolved is precisely whether the degree of regularity of the Weil-descent Semaev systems follows the first fall degree asymptotically.

Problem Statement

Let $E$ be an ordinary elliptic curve over $\mathbb{F}_{2^n}$, let $S_{m+1}$ be Semaev's $(m+1)$-th summation polynomial (the polynomial in the $x$-coordinates of $m+1$ points whose vanishing expresses that the points sum to zero), let $W\subseteq\mathbb{F}_{2^n}$ be a factor-base subspace of dimension $n'\ge m$ with basis $\nu_1,\ldots,\nu_{n'}$, let $c\in\mathbb{F}_{2^n}\setminus\{0\}$, and let $s_0,\ldots,s_{n-1}\in\mathbb{F}_2[y_{11},\ldots,y_{mn'}]/(y_{11}^2-y_{11},\ldots,y_{mn'}^2-y_{mn'})$ be the system obtained by Weil descent of $S_{m+1}(x_1,\ldots,x_m,c)$ along $W$. For $m\ge 3$, determine the asymptotic behavior of the degree of regularity $D_{reg}$ (the highest step degree occurring in the F4/F5 Gröbner basis computation on this system) as $n\to\infty$ in the parameter regimes relevant to index calculus, where $m=m(n)$ grows with $n$ (in the complexity analysis, $m\approx n^{1/3}$ and $n'\approx n^{2/3}$). Specifically: does

$$D_{reg}=m^2-m+1+o(1)$$

hold?

This single objective — establishing the asymptotic Gröbner complexity of the point-decomposition step — comprises the constitutive sub-questions identified by the source, each of which contributes to the main equality: (a) proving any nontrivial unconditional lower bound on $D_{reg}$ for these systems (a bound exceeding $m^2-m+1+o(1)$ along a regime refutes the equality; a bound of the form $m^2-m+1-O(1)$ supports it); (b) determining whether the proven first fall degree bound $D_{ff}\le m^2-m+1$ is sharp for all $m\ge 3$, as Kousidis and Wiemers conjecture; and (c) establishing the complementary upper bound on $D_{reg}$, which an affirmative answer additionally requires since no such bound is known. Sub-question (b) concerns the first fall degree $D_{ff}$, a different object from $D_{reg}$: it is independent supporting progress and does not by itself settle the equality, which requires both a lower bound and a matching upper bound on $D_{reg}$. An affirmative resolution makes the sharpened subexponential complexity $O(2^{c\log(n)(n^{2/3}-n^{1/3}+1)})$ of the index-calculus ECDLP algorithm over binary fields unconditional (turning point against generic $O(2^{n/2})$ algorithms near $n\approx 1250$); a negative resolution refutes the first-fall-degree assumption for these systems. Computational studies extending the $D_{ff}$ and $D_{reg}$ experiments to $m\ge 5$ and larger $n$ are admissible as supporting evidence but do not by themselves settle the asymptotic claim.

References

1. Stavros Kousidis and 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; arXiv:1906.05594. https://doi.org/10.1515/jmc-2017-0022
2. Christophe Petit and Jean-Jacques Quisquater, "On Polynomial Systems Arising from a Weil Descent", Advances in Cryptology – ASIACRYPT 2012, Lecture Notes in Computer Science, pp. 451-466, 2012. DOI: 10.1007/978-3-642-34961-4_28. https://doi.org/10.1007/978-3-642-34961-4_28
3. Timothy J. Hodges, Christophe Petit, and Jacob Schlather, "First fall degree and Weil descent", Finite Fields and Their Applications 30:155-177, 2014. DOI: 10.1016/j.ffa.2014.07.001. https://doi.org/10.1016/j.ffa.2014.07.001
4. Michiel Kosters and Sze Ling Yeo, "Notes on summation polynomials", arXiv:1503.08001, 2015. https://arxiv.org/abs/1503.08001
5. Ming-Deh A. Huang, Michiel Kosters, Yun Yang, and Sze Ling Yeo, "On the last fall degree of zero-dimensional Weil descent systems", arXiv:1505.02532, 2015 (revised 2018). https://arxiv.org/abs/1505.02532
6. Ming-Deh A. Huang, Michiel Kosters, and Sze Ling Yeo, "Last Fall Degree, HFE, and Weil Descent Attacks on ECDLP", Advances in Cryptology – CRYPTO 2015, Lecture Notes in Computer Science, pp. 581-600, 2015. DOI: 10.1007/978-3-662-47989-6_28. https://doi.org/10.1007/978-3-662-47989-6_28
7. Yun-Ju Huang, Christophe Petit, Naoyuki Shinohara, and Tsuyoshi Takagi, "On Generalized First Fall Degree Assumptions", IACR Cryptology ePrint Archive, Report 2015/358, 2015. https://eprint.iacr.org/2015/358
8. Igor Semaev, "Summation polynomials and the discrete logarithm problem on elliptic curves", IACR Cryptology ePrint Archive, Report 2004/031, 2004. https://eprint.iacr.org/2004/031
9. Igor Semaev, "New algorithm for the discrete logarithm problem on elliptic curves", arXiv:1504.01175, 2015. https://arxiv.org/abs/1504.01175
10. 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
11. Steven D. Galbraith and 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
12. Kazuhiro Yokoyama, Masaya Yasuda, Yasushi Takahashi, and Jun Kogure, "Complexity bounds on Semaev's naive index calculus method for ECDLP", Journal of Mathematical Cryptology 14(1):460-485, 2020. DOI: 10.1515/jmc-2019-0029. https://doi.org/10.1515/jmc-2019-0029
13. Monika Trimoska, Sorina Ionica, and Gilles Dequen, "A SAT-Based Approach for Index Calculus on Binary Elliptic Curves", Progress in Cryptology – AFRICACRYPT 2020, Lecture Notes in Computer Science, pp. 214-235, 2020. DOI: 10.1007/978-3-030-51938-4_11. https://doi.org/10.1007/978-3-030-51938-4_11
14. Ming-Deh A. Huang, "On the last fall degree of Weil descent polynomial systems", arXiv:2103.07282, 2021. https://arxiv.org/abs/2103.07282
15. Ming-Deh A. Huang, "Last fall degree of semi-local polynomial systems", arXiv:2311.02804, 2023. https://arxiv.org/abs/2311.02804
16. Shuhei Nakamura, "Formal Power Series on Algebraic Cryptanalysis", arXiv:2007.14729, 2020. https://arxiv.org/abs/2007.14729