Communications in Cryptology IACR CiC

Computing Orientations from the Endomorphism Ring of Supersingular Curves and Applications

Authors

Jonathan Komada Eriksen, Antonin Leroux
Jonathan Komada Eriksen ORCID
Norwegian University of Science and Technology, Trondheim, Norway
jonathan dot k dot eriksen at ntnu dot no
Antonin Leroux ORCID
DGA-MI, France
Université de Rennes, France
antonin dot leroux at polytechnique dot org

Abstract

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.

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
[BKM+24]
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
[CK20]
Leonardo Colò and David Kohel. Orienting supersingular isogeny graphs. J. Math. Cryptol., 14(1):414–437, 2020. DOI: 10.1515/JMC-2019-0034
[CLM+18]
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
[CPV20]
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
[DFKL+20]
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
[EHL+18]
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
[FdSGF+21]
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
[FFK+23]
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
[KLPT14]
David Kohel, Kristin E. Lauter, Christophe Petit, and Jean-Pierre Tignol. On the quaternion $\ell$-isogeny path problem. LMS J. Comput. Math., 17(Theory):418–432, 2014. DOI: 10.1112/S1461157014000151
[Koh96]
D. Kohel. Endomorphism rings of elliptic curves over finite fields. PhD thesis, University of California at Berkeley, 1996.
[LB20]
Jonathan Love and Dan Boneh. Supersingular curves with small noninteger endomorphisms. Open Book Series, 4(1):7–22, 2020. DOI: 10.2140/obs.2020.4.7
[Ler22a]
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
[Ler22b]
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
[Onu21]
Hiroshi Onuki. On oriented supersingular elliptic curves. Finite Fields Their Appl., 69:101777, 2021. DOI: 10.1016/J.FFA.2020.101777
[PR23]
Aurel Page and Damien Robert. Introducing Clapoti(s): Evaluating the isogeny class group action in polynomial time. IACR Cryptol. ePrint Arch., 2023.
[{The}22]
The Sage Developers. SageMath, the Sage Mathematics Software System (version 9.7). , 2022.
[Voi18]
John Voight. Quaternion Algebras. Springer Graduate Texts in Mathematics series 2018.
[Wes22]
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
[Wig07]
Carl Severin Wigert. Sur l'ordre de grandeur du nombre des diviseurs d'un entier. Almqvist & Wiksell 1907.

PDFPDF Open access

History
Submitted: 2024-06-14
Accepted: 2024-09-02
Published: 2024-10-07
How to cite

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.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.