This work introduces several algorithms related to the computation of orientations in endomorphism rings of supersingular elliptic curves. This problem is at the heart of several results regarding the security of oriented-curves in isogeny-based cryptography. Under the Deuring correspondence, it can be expressed purely in terms of quaternion and boils down to representing integers by ternary quadratic forms. Our main contribution is to show that there exist efficient algorithms to solve this problem for quadratic orders of discriminant up to . Our approach improves upon previous results by increasing this bound from to and removing some heuristics. We introduce several variants of our new algorithm and provide a careful analysis of their asymptotic running time (without heuristic when it is possible). The best proven asymptotic complexity of one of our variants is in average. The best heuristic variant has a complexity of for big enough . We then introduce several results regarding the computation of ideals between oriented orders. The first application of this is a simplification of the known reduction from vectorization to computing the endomorphism ring, removing the assumption on the factorization of the discriminant. As a second application, we relate the problem of computing fixed-degree isogenies between supersingular curves to the problem of computing orientations in endomorphism rings, and we show that for a large range of degree , our new algorithms improve on the state-of-the-art, and in important special cases, the range of degree for which there exist a polynomial-time algorithm is increased. In the most special case we consider, when both curves are oriented by a small degree endomorphism, we show heuristically that our techniques allow the computation of isogenies of any degree, assuming they exist.
References
[ACD+24]
Sarah Arpin, James Clements, Pierrick Dartois, Jonathan Komada Eriksen, Péter Kutas, and Benjamin Wesolowski. Finding orientations of supersingular elliptic curves and quaternion orders. Designs, Codes and Cryptography, 2024. DOI: 10.1007/s10623-024-01435-5
Benjamin Bencina, Péter Kutas, Simon-Philipp Merz, Christophe Petit, Miha Stopar, and Charlotte Weitkämper. Improved Algorithms for Finding Fixed-Degree Isogenies Between Supersingular Elliptic Curves. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part V, volume 14924 of Lecture Notes in Computer Science, pages 183–217. 2024. Springer. DOI: 10.1007/978-3-031-68388-6_8
Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes. CSIDH: An Efficient Post-Quantum Commutative Group Action. In Thomas Peyrin and Steven D. Galbraith, editors, Advances in Cryptology - ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part III, volume 11274 of Lecture Notes in Computer Science, pages 395–427. 2018. Springer. DOI: 10.1007/978-3-030-03332-3_15
Wouter Castryck, Lorenz Panny, and Frederik Vercauteren. Rational Isogenies from Irrational Endomorphisms. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part II, volume 12106 of Lecture Notes in Computer Science, pages 523–548. 2020. Springer. DOI: 10.1007/978-3-030-45724-2_18
Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit, and Benjamin Wesolowski. SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies. In Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part I, volume 12491 of Lecture Notes in Computer Science, pages 64–93. 2020. Springer. DOI: 10.1007/978-3-030-64837-4_3
Kirsten Eisenträger, Sean Hallgren, Kristin E. Lauter, Travis Morrison, and Christophe Petit. Supersingular Isogeny Graphs and Endomorphism Rings: Reductions and Solutions. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part III, volume 10822 of Lecture Notes in Computer Science, pages 329–368. 2018. Springer. DOI: 10.1007/978-3-319-78372-7_11
Luca De Feo, Cyprien Delpech de Saint Guilhem, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Christophe Petit, Javier Silva, and Benjamin Wesolowski. Séta: Supersingular Encryption from Torsion Attacks. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part IV, volume 13093 of Lecture Notes in Computer Science, pages 249–278. 2021. Springer. DOI: 10.1007/978-3-030-92068-5_9
Luca De Feo, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Simon-Philipp Merz, Lorenz Panny, and Benjamin Wesolowski. SCALLOP: Scaling the CSI-FiSh. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, Public-Key Cryptography - PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Atlanta, GA, USA, May 7-10, 2023, Proceedings, Part I, volume 13940 of Lecture Notes in Computer Science, pages 345–375. 2023. Springer. DOI: 10.1007/978-3-031-31368-4_13
David Kohel, Kristin E. Lauter, Christophe Petit, and Jean-Pierre Tignol. On the quaternion -isogeny path problem. LMS J. Comput. Math., 17(Theory):418–432, 2014. DOI: 10.1112/S1461157014000151
Antonin Leroux. An Effective Lower Bound on the Number of Orientable Supersingular Elliptic Curves. In Benjamin Smith and Huapeng Wu, editors, Selected Areas in Cryptography - 29th International Conference, SAC 2022, Windsor, ON, Canada, August 24-26, 2022, Revised Selected Papers, volume 13742 of Lecture Notes in Computer Science, pages 263–281. 2022. Springer. DOI: 10.1007/978-3-031-58411-4_12
Antonin Leroux. A New Isogeny Representation and Applications to Cryptography. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part II, volume 13792 of Lecture Notes in Computer Science, pages 3–35. 2022. Springer. DOI: 10.1007/978-3-031-22966-4_1
Benjamin Wesolowski. Orientations and the Supersingular Endomorphism Ring Problem. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part III, volume 13277 of Lecture Notes in Computer Science, pages 345–371. 2022. Springer. DOI: 10.1007/978-3-031-07082-2_13
Jonathan Komada Eriksen and Antonin Leroux, Computing Orientations from the Endomorphism Ring of Supersingular Curves and Applications. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ae0fhbmo.
@article{CiC-1-3-5,
author = "Eriksen, Jonathan Komada and Leroux, Antonin",
journal = "{IACR} {C}ommunications in {C}ryptology",
publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
title = "Computing Orientations from the Endomorphism Ring of Supersingular Curves and Applications",
volume = "1",
number = "3",
date = "2024-10-07",
year = "2024",
issn = "3006-5496",
doi = "10.62056/ae0fhbmo"
}
TY - JOUR
AU - Eriksen, Jonathan
AU - Leroux, Antonin
PY - 2024
TI - Computing Orientations from the Endomorphism Ring of Supersingular Curves and Applications
JF - IACR Communications in Cryptology
JA - CIC
VL - 1
IS - 3
DO - 10.62056/ae0fhbmo
UR - https://doi.org/10.62056/ae0fhbmo
AB - <p> This work introduces several algorithms related to the computation of orientations in endomorphism rings of supersingular elliptic curves. This problem is at the heart of several results regarding the security of oriented-curves in isogeny-based cryptography. Under the Deuring correspondence, it can be expressed purely in terms of quaternion and boils down to representing integers by ternary quadratic forms. Our main contribution is to show that there exist efficient algorithms to solve this problem for quadratic orders of discriminant $n$ up to $O(p^{4/3})$. Our approach improves upon previous results by increasing this bound from $O(p)$ to $O(p^{4/3})$ and removing some heuristics. We introduce several variants of our new algorithm and provide a careful analysis of their asymptotic running time (without heuristic when it is possible). The best proven asymptotic complexity of one of our variants is $O(n^{3/4}/p)$ in average. The best heuristic variant has a complexity of $O(p^{1/3})$ for big enough $n$. We then introduce several results regarding the computation of ideals between oriented orders. The first application of this is a simplification of the known reduction from vectorization to computing the endomorphism ring, removing the assumption on the factorization of the discriminant. As a second application, we relate the problem of computing fixed-degree isogenies between supersingular curves to the problem of computing orientations in endomorphism rings, and we show that for a large range of degree $d$, our new algorithms improve on the state-of-the-art, and in important special cases, the range of degree $d$ for which there exist a polynomial-time algorithm is increased. In the most special case we consider, when both curves are oriented by a small degree endomorphism, we show heuristically that our techniques allow the computation of isogenies of any degree, assuming they exist. </p>
ER -
Jonathan Komada Eriksen and Antonin Leroux, Computing Orientations from the Endomorphism Ring of Supersingular Curves and Applications. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ae0fhbmo.
Known citations
We do not crawl the web, so we are only able to identify
citations from papers that are registered with a DOI in
crossref.org and the publisher reports their citations to
crossref, and crossref can identify a DOI from the
reference. That includes (most) articles from Springer and
many from ACM, but it excludes citations from USENIX because
they don't issue DOIs. It also excludes citations from arxiv
and eprint. You may find more citations in
Google Scholar.