Paper 2025/226

Improved Subfield Curve Search For Specific Field Characteristics

Jesús-Javier Chi-Domínguez, Technology Innovation Institute
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 O~(p1/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 for some positive integers and . This work focuses on primes of that particular form, and it presents two new algorithms for finding subfield curves with a time complexity of operations and a memory complexity polynomial in . Such algorithms exploit the existence of large torsion- 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 and with being a small integer. This study also examines the usage of radical -isogenies with the proposed extended subfield root detection algorithm. In this context, the results indicate that the radical -isogeny approach is competitive compared with the state-of-the-art algorithms.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Delfs-Galbraith AlgorithmIsogeny-based CryptographySubfield Curve SearchSupersingular Isogeny Problem
Contact author(s)
jesus dominguez @ tii ae
History
2025-02-17: approved
2025-02-14: received
See all versions
Short URL
https://ia.cr/2025/226
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2025/226,
      author = {Jesús-Javier Chi-Domínguez},
      title = {Improved Subfield Curve Search For Specific Field Characteristics},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/226},
      year = {2025},
      url = {https://eprint.iacr.org/2025/226}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.