Improved Subfield Curve Search For Specific Field Characteristics

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 Fₚ.

The Delfs-Galbraith algorithm is one of the most efficient procedures for solving the supersingular isogeny problem with a time complexity of Õ(√p) 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ᵃ • f - 1 for some positive integers a and f. This work primarily focuses on primes of that particular form and presents two heuristic algorithms for finding subfield curves with a time complexity of O(√p) operations and a memory complexity polynomial in log₂p. We show how to adapt these algorithms to primes of the form p = dᵃ • 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ᵃ • f - 1 and p = (12)ᵃ • f - 1. Our algorithms exploit the existence of large dᵃ-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.

We highlight that our algorithms easily extend to primes of the form p = 2ᵃ • f + 1, p = 4 • d₁ • dₙ ••• dₙ - 1 for small odd primes dᵢ's, and primes such that p - 1 and p + 1 are B-smooth for some integer B.