Computing Orientations from the Endomorphism Ring of Supersingular Curves and Applications

Jonathan Komada Eriksen; Antonin Leroux

doi:10.62056/ae0fhbmo

Computing Orientations from the Endomorphism Ring of Supersingular Curves and Applications

Authors

Jonathan Komada Eriksen, Antonin Leroux

Jonathan Komada Eriksen

Norwegian University of Science and Technology, Trondheim, Norway
jonathan dot k dot eriksen at ntnu dot no

Antonin Leroux

DGA-MI, France
Université de Rennes, France
antonin dot leroux at polytechnique dot org

Keywords: Quaternion Algebras Optimal Embeddings Orientations Isogenies

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

Google Scholar ePrint

[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

Google Scholar ePrint

[CK20]

Leonardo Colò and David Kohel. Orienting supersingular isogeny graphs. J. Math. Cryptol., 14(1):414–437, 2020. DOI: 10.1515/JMC-2019-0034

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[Koh96]

D. Kohel. Endomorphism rings of elliptic curves over finite fields. PhD thesis, University of California at Berkeley, 1996.

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[Onu21]

Hiroshi Onuki. On oriented supersingular elliptic curves. Finite Fields Their Appl., 69:101777, 2021. DOI: 10.1016/J.FFA.2020.101777

Google Scholar ePrint

[PR23]

Aurel Page and Damien Robert. Introducing Clapoti(s): Evaluating the isogeny class group action in polynomial time. IACR Cryptol. ePrint Arch., 2023.

Google Scholar ePrint

[{The}22]

The Sage Developers. SageMath, the Sage Mathematics Software System (version 9.7). , 2022.

Google Scholar ePrint

[Voi18]

John Voight. Quaternion Algebras. Springer Graduate Texts in Mathematics series 2018.

Google Scholar ePrint

[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

Google Scholar ePrint

[Wig07]

Carl Severin Wigert. Sur l'ordre de grandeur du nombre des diviseurs d'un entier. Almqvist & Wiksell 1907.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ae0fhbmo

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.

@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.