Paper 2025/226

Improved Subfield Curve Search For Specific Field Characteristics

Abstract

Isogeny-based cryptography relies its security on the hardness of the supersingular isogeny problem: finding an isogeny between two supersingular curves defined over a quadratic field extension of $\mathbb{F}_p$. The Delfs-Galbraith algorithm is one of the most efficient procedures for solving the supersingular isogeny problem with a time complexity of $\mathcal{\tilde{O}}(p^{1/2})$ operations. The bottleneck of the Delfs-Galbraith algorithm is the so-called subfield curve search (i.e., finding an isogenous supersingular elliptic curve defined over the prime field), which determines the time complexity of the aforementioned algorithm. Given that, for efficiency, most recent isogeny-based constructions propose using finite fields with field characteristics equal to $p = 2^a \cdot f - 1$ for some positive integers $a$ and $f$. This work primary focuses on primes of that particular form and presents two heuristic algorithms for finding subfield curves with a time complexity of $\mathcal{O}(p^{1/2})$ operations and a memory complexity polynomial in $\log_2{p}$. We show how to adapt these algorithms to primes of the form $p = d^a \cdot f - 1$ with $d$ being a small integer, with a particular focus on $d=12$. We provide concrete time-complexity bounds for both kinds of primes $p = 2^a\cdot f - 1$ and $p = {12}^a \cdot f - 1$. Our algorithms exploit the existence of large $d^a$-torsion points and extend the subfield root detection algorithm of Corte-Real Santos, Costello, and Shi (Crypto, 2022) to a projective scenario where one can work with the curve coefficients instead of their explicit j-invariants. When considering the bit complexity $\mathcal{O}\left( (\log_2{p})^{\kappa} p^{1/2}\right)$ of the subfield curve searching algorithms, our results suggest a smaller value of $\kappa = \log_{3}{5} \approx 1.465$ compared to the state of the art value of $\kappa=2$. We discuss how this lower bit complexity affects current isogeny-based constructions. We highlight that our algorithms easily extend to primes of the form $p =2^a \cdot f + 1$, $p =4 \cdot d_1 \cdot d_2 \cdots d_n - 1$ for small odd primes $d_i$'s, and primes such that $p - 1$ and $p + 1$ are $B$-smooth for some integer $B$.

Note: Refactor of the manuscript. Experiments have been moved to Appendix, and Discussion on the bit complexity estimates was added. Fixed typos. Added discussion on other cryptographic interest primes (e.g., CSIDH primes).