EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Improved Subfield Curve Search For Specific Field Characteristics

Jesús-Javier Chi-Domínguez

IACR Communications in Cryptology · 03.08.2026 · 3 (2)

DOI: 10.62056/ah5womja5 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IACR Communications in Cryptology, online erschienen am 03.08.2026. Verfasst von Jesús-Javier Chi-Domínguez. Die Arbeit nennt 28 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Chi-Domínguez, J. (2026). Improved Subfield Curve Search For Specific Field Characteristics. IACR Communications in Cryptology, 3(2). https://doi.org/10.62056/ah5womja5

Vancouver

Chi-Domínguez J. Improved Subfield Curve Search For Specific Field Characteristics. IACR Communications in Cryptology. 2026;3(2). doi:10.62056/ah5womja5

BibTeX
@article{ChiDomnguez2026,
  author = {Chi-Domínguez, Jesús-Javier},
  title = {Improved Subfield Curve Search For Specific Field Characteristics},
  journal = {IACR Communications in Cryptology},
  year = {2026},
  volume = {3},
  number = {2},
  doi = {10.62056/ah5womja5}
}
Kostenlos starten →