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. The Delfs-Galbraith algorithm is the most efficient procedure for solving the supersingular isogeny problem with a time complexity of $\tilde{\mathcal{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 base field), which determines the time complexity. 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 focuses on primes of that particular form, and it presents two new 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}$. Such algorithms exploit the existence of large torsion-$2^a$ points and extend the subfield root detection algorithm of Santos, Costello, and Shi (Crypto 2022) to our case study. In addition, it is worth highlighting that these algorithms easily extend to primes of the form $p =2^a \cdot f + 1$ and $p = \ell^a \cdot f - 1$ with $\ell$ being a small integer. This study also examines the usage of radical $3$-isogenies with the proposed extended subfield root detection algorithm. In this context, the results indicate that the radical $3$-isogeny approach is competitive compared with the state-of-the-art algorithms.