Supersingular isogeny problem solved in less time and memory
The Supersingular Isogeny Problem in Time and Memory $p^{1/3+o(1)}$, Unconditionally
Cryptography and Security
Summary
The paper tackles a math problem involving special mathematical objects called supersingular elliptic curves. The authors provide an algorithm that finds certain transformations on these curves more efficiently—in less time and using less memory—without relying on strong assumptions. This problem is important because solving it also helps with related problems that are key to some areas of cryptography. Their method cleverly uses known patterns of connections between curves and a matching strategy to find the solution.
What this means in practice
- •For cryptographic system designers: Evaluate and adjust cryptographic schemes based on supersingular isogenies considering improved algorithmic attacks with time and memory scaling around p^{1/3}.
- •For software developers working on post-quantum cryptography: Implement and benchmark new isogeny-based cryptographic tools using the improved algorithm to test performance and security trade-offs.
Authors
José Luis Delgado
Abstract
Given a supersingular elliptic curve $E/\mathbb{F}_{p^2}$, the $\mathsf{OneEnd}$ problem asks for a non-scalar endomorphism of $E$. By known reductions, solving this problem also solves the supersingular endomorphism ring and isogeny problems. Wesolowski obtained exponent $1/3$ under an assumption on the factorization of a small degree, whereas the previous unconditional exponent was $2/5$. We give a Las Vegas algorithm, analyzed without a smoothness heuristic, with expected time and memory \[ p^{1/3}\exp\bigl(O(\sqrt{\log p\,\log\log p})\bigr) = p^{1/3+o(1)}. \] The algorithm fixes in advance a family of degrees that are products of small primes. Known counting results provide many isogenies of these degrees from curves to their Frobenius conjugates, and a collision estimate shows that the isogenies occur on sufficiently many distinct curves for a random walk to reach one of them. From such a curve, the algorithm splits a degree into two parts, enumerates two lists of shorter isogenies, and matches their targets to obtain an isogeny to the conjugate, whose composition with Frobenius gives the required endomorphism.