Summation polynomials and elliptic-curve index calculus
Index calculus reduced finite-field discrete logarithms to subexponential time. Whether the same can be done for elliptic curves is the central open question in ECC hardness, and summation polynomials are the sharpest tool anyone has aimed at it. Over extension fields they work. Over prime fields, after twenty years, they do not.
- Problem
- ECDLP on E/Fqn
- Cost
- Õ(q2−2/n) for fixed n > 1 (Gaudry); subexponential for suitable growing families (Diem)
- Bottleneck
- Gröbner-basis solving of the decomposition system
- Affects
- Curves over extension fields with a usable subfield structure
- Does not affect
- Prime-field curves — P-256, secp256k1, Curve25519
Why index calculus is the question
In Fp×, index calculus is devastating: pick a factor base of small primes, find many relations among their logarithms, solve the resulting sparse linear system, and the discrete logarithm becomes subexponential. This is why a finite-field Diffie–Hellman modulus must be 3072 bits to match a 256-bit curve.
The method needs two ingredients: a notion of an element being smooth, and cheap relations among smooth elements. A group of points on an elliptic curve has neither by default. There is no factorisation, so there is no smoothness; the only structure is the group law. Making index calculus work on a curve means manufacturing both.
Semaev's construction
Semaev supplies the missing notion of a relation. The m-th summation polynomial Sm is the polynomial in m variables whose vanishing characterises x-coordinates of points summing to the identity:
For E: y2 = x3 + ax + b the third one is explicit, and it is just the group law with the y-coordinates eliminated by resultant:
Higher ones come from resultants of lower ones, Sm+1 = ResX(Sm, S3), and the degree in each variable doubles each time: deg Sm = 2m−2 per variable. That doubling is the whole story of the method's cost.
The factor base, and why it needs an extension field
Gaudry's insight is that over Fqn there is a natural factor base with no analogue over a prime field: the points whose x-coordinate lies in the subfield Fq. That set has about q elements inside a group of size qn, which is a genuine sub-object to decompose against.
Relation search then proceeds by Weil restriction. For a random point R = aP + bQ, ask whether it decomposes as a sum of n factor-base points:
- Impose Sn+1(x1, …, xn, x(R)) = 0 with each xi constrained to the subfield Fq.
- Write each xi in a basis of Fqn over Fq; the single equation becomes n equations over Fq in n unknowns.
- Solve that system with a Gröbner-basis engine. A solution is a relation; no solution means try another R.
- Collect slightly more than q relations, then solve the sparse linear system over ℤ/nℤ for the factor-base logarithms.
Counting relations gives the asymptotic: for fixed n, the total is Õ(q2−2/n) group operations, which beats rho's qn/2 once n ≥ 3. Diem pushed this further, showing that for suitable families in which n grows with q the problem becomes subexponential in the size of the group. These are real results about real elliptic curves, and they are the reason "ECDLP is exponential" is a claim about chosen parameters rather than a theorem about curves.
The Gröbner bottleneck
Hidden inside step three is where all the difficulty lives. The decomposition system has n equations in n variables, of degree 2n−1, and solving it with F4/F5 costs something governed by the degree of regularity reached during the computation — a quantity that is not known in advance and, for these particular systems, is not reliably predicted by the generic-system heuristics.
Two research threads try to control it. Symmetrisation rewrites the system in the elementary symmetric functions of the xi, since the decomposition is unordered, cutting the degree substantially; over binary fields Faugère, Perret, Petit and Renault exploited the additional structure of the field equations. The first fall degree — the degree at which non-trivial degree falls first occur — became the standard proxy for predicting feasibility, and a body of work argues both that it is a good predictor and that it is not.
The boundary
For a curve over a prime field Fp there is no proper subfield, so Gaudry's factor base does not exist. Every attempt to substitute something else — points whose x-coordinate lies in a chosen interval, in a small-degree image, or in a set defined by a low-weight representation — has failed to produce enough relations cheaply enough to beat √p. No published attack on the prime-field ECDLP improves on generic methods.
So the practical reading is narrow and specific:
- Prime-field curves — P-256, P-384, secp256k1, Curve25519 — are unaffected. Their security level remains the rho bound.
- Curves over Fqn with small n > 1 need their security assessed against Õ(q2−2/n), not against the group size.
- Binary curves over F2m with m prime resist this and Weil descent, which is why the standardised binary degrees are prime.
- The open question — whether any factor base works over a prime field — is unresolved, not settled in the negative. It is worth tracking rather than filing away.
Primary sources
- I. Semaev, "Summation polynomials and the discrete logarithm problem on elliptic curves" (2004)
- P. Gaudry, "Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem", Journal of Symbolic Computation 44 (2009)
- C. Diem, "On the discrete logarithm problem in elliptic curves", Compositio Mathematica 147 (2011)
- J.-C. Faugère, L. Perret, C. Petit and G. Renault, "Improving the complexity of index calculus algorithms in elliptic curves over binary fields", EUROCRYPT 2012
- C. Petit and J.-J. Quisquater, "On polynomial systems arising from a Weil descent", ASIACRYPT 2012
- S. D. Galbraith and P. Gaudry, "Recent progress on the elliptic curve discrete logarithm problem", Designs, Codes and Cryptography 78 (2016)