The supersingular endomorphism ring problem given one endomorphism
Authors
Arthur Herlédan Le Merdy, Benjamin Wesolowski
Arthur Herlédan Le Merdy
ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France
ENS de Lyon, LIP (CNRS, U. Lyon, ENS de Lyon, Inria, UCBL), UMR 5668, Lyon, France
arthur dot herledan_le_merdy at ens-lyon dot fr
ENS de Lyon, LIP (CNRS, U. Lyon, ENS de Lyon, Inria, UCBL), UMR 5668, Lyon, France
arthur dot herledan_le_merdy at ens-lyon dot fr
Benjamin Wesolowski
ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France
Keywords:
Isogeny-based cryptography
Endomorphism ring
Supersingular elliptic curve
Orientation
Class group
Cryptanalysis
Abstract
Given a supersingular elliptic curve E and a non-scalar endomorphism α of E, we prove that the endomorphism ring of E can be computed in classical time about disc(Z[α])^1/4, and in quantum subexponential time, assuming the generalised Riemann hypothesis. Previous results either had higher complexities, or relied on heuristic assumptions.
Along the way, we describe and analyse a general algorithm to divide isogenies in polynomial time, and to solve the Primitivisation problem in polynomial time. Following the attacks on SIDH, isogenies in high dimension are a central ingredient of our results.
References
[ACL+23]
Sarah Arpin, Mingjie Chen, Kristin E. Lauter, Renate Scheidler, Katherine E. Stange, and Ha T. N. Tran. Orienteering with one endomorphism. Matematica, 2(3):523–582, 2023. DOI: 10.1007/s44007-023-00053-2
[ACL+24]
Sarah Arpin, Mingjie Chen, Kristin E. Lauter, Renate Scheidler, Katherine E. Stange, and Ha T. N. Tran. Orientations and cycles in supersingular isogeny graphs. In Research directions in number theory, volume 33 of Assoc. Women Math. Ser., pages 25–86. Springer, Cham 2024. DOI: 10.1007/978-3-031-51677-1_2
[BJS14]
Jean-François Biasse, David Jao, and Anirudh Sankar. A Quantum Algorithm for Computing Isogenies between Supersingular Elliptic Curves. In Willi Meier and Debdeep Mukhopadhyay, editors, Progress in Cryptology - INDOCRYPT 2014: 15th International Conference in Cryptology in India, volume 8885 of Lecture Notes in Computer Science, pages 428–442. December 2014. Springer, Cham. DOI: 10.1007/978-3-319-13039-2_25
[BKV19]
Ward Beullens, Thorsten Kleinjung, and Frederik Vercauteren. CSI-FiSh: Efficient Isogeny Based Signatures Through Class Group Computations. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology – ASIACRYPT 2019, Part I, volume 11921 of Lecture Notes in Computer Science, pages 227–247. December 2019. Springer, Cham. DOI: 10.1007/978-3-030-34578-5_9
[BS12]
Gaetan Bisson and Andrew V. Sutherland. A low-memory algorithm for finding short product representations in finite groups. Designs, Codes and Cryptography, 63(1):1–13, 2012. DOI: 10.1007/s10623-011-9527-8
[BS16]
Jean-François Biasse and Fang Song. Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 893–902. 2016. ACM, New York. DOI: 10.1137/1.9781611974331.ch64
[CD20]
Wouter Castryck and Thomas Decru. CSIDH on the Surface. In Jintai Ding and Jean-Pierre Tillich, editors, Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020, pages 111–129. 2020. Springer, Cham. DOI: 10.1007/978-3-030-44223-1_7
[CD23]
Wouter Castryck and Thomas Decru. An Efficient Key Recovery Attack on SIDH. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, Part V, volume 14008 of Lecture Notes in Computer Science, pages 423–447. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30589-4_15
[CJS14]
Andrew Childs, David Jao, and Vladimir Soukharev. Constructing elliptic curve isogenies in quantum subexponential time. Journal of Mathematical Cryptology, 8(1):1–29, 2014. DOI: 10.1515/jmc-2012-0016
[CK20]
Leonardo Colo and David Kohel. Orienting supersingular isogeny graphs. Journal of Mathematical Cryptology, 14(1):414–437, 2020. Publisher: De Gruyter DOI: 10.1515/jmc-2019-0034
[CLG09]
Denis X Charles, Kristin E Lauter, and Eyal Z Goren. Cryptographic hash functions from expander graphs. Journal of CRYPTOLOGY, 22(1):93–113, 2009. Publisher: Springer DOI: 10.1007/s00145-007-9002-x
[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 Galbraith, editors, Advances in Cryptology – ASIACRYPT 2018, Part III, volume 11274 of Lecture Notes in Computer Science, pages 395–427. December 2018. Springer, Cham. DOI: 10.1007/978-3-030-03332-3_15
[CLP24]
Mingjie Chen, Antonin Leroux, and Lorenz Panny. SCALLOP-HD: Group Action from 2-Dimensional Isogenies. In Qiang Tang and Vanessa Teague, editors, PKC 2024: 27th International Conference on Theory and Practice of Public Key Cryptography, Part III, volume 14603 of Lecture Notes in Computer Science, pages 190–216. April 2024. Springer, Cham. DOI: 10.1007/978-3-031-57725-3_7
[Cou06]
Jean-Marc Couveignes. Hard homogeneous spaces. Cryptology ePrint Archive, 2006.
[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, Part II, volume 12106 of Lecture Notes in Computer Science, pages 523–548. May 2020. Springer, Cham. DOI: 10.1007/978-3-030-45724-2_18
[CS22]
Mathilde Chenu and Benjamin Smith. Higher-degree supersingular group actions. Mathematical Cryptology, 1(2):85–101, March 2022. Publisher: Florida Online Journals
[DDF+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, Part IV, volume 13093 of Lecture Notes in Computer Science, pages 249–278. December 2021. Springer, Cham. DOI: 10.1007/978-3-030-92068-5_9
[DFK+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, PKC 2023: 26th International Conference on Theory and Practice of Public Key Cryptography, Part I, volume 13940 of Lecture Notes in Computer Science, pages 345–375. May 2023. Springer, Cham. DOI: 10.1007/978-3-031-31368-4_13
[DG16]
Christina Delfs and Steven D. Galbraith. Computing isogenies between supersingular elliptic curves over $\mathbb{F}_p$. Designs, Codes and Cryptography, 78(2):425–440, 2016. DOI: 10.1007/s10623-014-0010-1
[DKL+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, Part I, volume 12491 of Lecture Notes in Computer Science, pages 64–93. December 2020. Springer, Cham. DOI: 10.1007/978-3-030-64837-4_3
[DLRW24]
Pierrick Dartois, Antonin Leroux, Damien Robert, and Benjamin Wesolowski. SQIsignHD: New Dimensions in Cryptography. In Marc Joye and Gregor Leander, editors, Advances in Cryptology – EUROCRYPT 2024, Part I, volume 14651 of Lecture Notes in Computer Science, pages 3–32. May 2024. Springer, Cham. DOI: 10.1007/978-3-031-58716-0_1
[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, Part III, volume 10822 of Lecture Notes in Computer Science, pages 329–368. 2018. Springer, Cham. DOI: 10.1007/978-3-319-78372-7_11
[EHL+20]
Kirsten Eisenträger, Sean Hallgren, Chris Leonardi, Travis Morrison, and Jennifer Park. Computing endomorphism rings of supersingular elliptic curves and connections to path-finding in isogeny graphs. Open Book Series, 4(1):215–232, 2020. Publisher: Mathematical Sciences Publishers DOI: 10.2140/obs.2020.4.215
[Kan97]
Ernst Kani. The number of curves of genus two with elliptic differentials.. Journal für die reine und angewandte Mathematik, 485:93–122, 1997. DOI: 10.1515/crll.1997.485.93
[Koh96]
David Russell Kohel. Endomorphism rings of elliptic curves over finite fields. ProQuest LLC, Ann Arbor, MI 1996. Thesis (Ph.D.)–University of California, Berkeley
[Kup05]
Greg Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM Journal on Computing, 35(1):170–188, 2005. Publisher: SIAM DOI: 10.1137/S0097539703436345
[LR12]
David Lubicz and Damien Robert. Computing isogenies between abelian varieties. Compositio Mathematica, 148(5):1483–1515, 2012. Publisher: London Mathematical Society DOI: 10.1112/S0010437X12000243
[LR23]
David Lubicz and Damien Robert. Fast change of level and applications to isogenies. Research in Number Theory, 9(1):7, 2023. Publisher: Springer DOI: 10.1007/s40993-022-00407-9
[Mil86]
James S Milne. Abelian varieties. Arithmetic geometry, 1986. Publisher: Springer
[MMP+23]
Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, and Benjamin Wesolowski. A Direct Key Recovery Attack on SIDH. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, Part V, volume 14008 of Lecture Notes in Computer Science, pages 448–471. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30589-4_16
[Mum70]
David Mumford. Abelian Varieties. Oxford University Press, London 1970.
[Onu21]
Hiroshi Onuki. On oriented supersingular elliptic curves. Finite Fields and Their Applications, 69:101777, 2021. Publisher: Elsevier DOI: 10.1016/j.ffa.2020.101777
[Pom87]
Carl Pomerance. Fast, rigorous factorization and discrete logarithm algorithms. In Discrete algorithms and complexity (Kyoto, 1986), volume 15 of Perspect. Comput., pages 119–143. Academic Press, Boston, MA 1987.
[PR23]
Aurel Page and Damien Robert. Introducing Clapoti (s): Evaluating the isogeny class group action in polynomial time. Cryptology ePrint Archive, 2023.
[PT18]
Paul Pollack and Enrique Treviño. Finding the Four Squares in Lagrange's Theorem.. Integers, 18(A15):7–17, 2018.
[PW24]
Aurel Page and Benjamin Wesolowski. The Supersingular Endomorphism Ring and One Endomorphism Problems are Equivalent. In Marc Joye and Gregor Leander, editors, Advances in Cryptology – EUROCRYPT 2024, Part VI, volume 14656 of Lecture Notes in Computer Science, pages 388–417. May 2024. Springer, Cham. DOI: 10.1007/978-3-031-58751-1_14
[Rob21]
Damien Robert. Efficient algorithms for abelian varieties and their moduli spaces. PhD thesis, Université de Bordeaux (UB), 2021.
[Rob22a]
Damien Robert. Evaluating isogenies in polylogarithmic time. Cryptology ePrint Archive, 2022.
[Rob22b]
Damien Robert. Some applications of higher dimensional isogenies to elliptic curves (preliminary version). Cryptology ePrint Archive, 2022.
[Rob23]
Damien Robert. Breaking SIDH in Polynomial Time. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, Part V, volume 14008 of Lecture Notes in Computer Science, pages 472–503. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30589-4_17
[Rob24]
Damien Robert. On the efficient representation of isogenies (a survey). Cryptology ePrint Archive, 2024.
[RS06]
Alexander Rostovtsev and Anton Stolbunov. Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, 2006.
[Sil86]
Joseph H. Silverman. The arithmetic of elliptic curves, volume 106 of Graduate texts in mathematics. Graduate texts in mathematics. Springer 1986. DOI: 10.1007/978-1-4757-1920-8
[Voi21]
John Voight. Quaternion algebras. Springer Nature 2021.
[Vé71]
Jacques Vélu. Isogénies entre courbes elliptiques. C. R. Acad. Sc. Paris, Série A, t. 273:238–241, 1971.
[Wes22a]
Benjamin Wesolowski. Orientations and the Supersingular Endomorphism Ring Problem. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology – EUROCRYPT 2022, Part III, volume 13277 of Lecture Notes in Computer Science, pages 345–371. 2022. Springer, Cham. DOI: 10.1007/978-3-031-07082-2_13
[Wes22b]
Benjamin Wesolowski. The supersingular isogeny path and endomorphism ring problems are equivalent. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1100–1111. 2022. IEEE. DOI: 10.1109/FOCS52979.2021.00109
[Wes24]
Benjamin Wesolowski. Random Walks in Number-theoretic Cryptology. PhD thesis, ENS Lyon, 2024.
[Zar74]
Ju G Zarhin. A remark on endomorphisms of abelian varieties over function fields of finite characteristic. Mathematics of the USSR-Izvestiya, 8(3):477, 1974. Publisher: IOP Publishing DOI: 10.1070/IM1974v008n03ABEH002115
PDF
History
Submitted: 2024-10-09
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
Arthur Herlédan Le Merdy and Benjamin Wesolowski, The supersingular endomorphism ring problem given one endomorphism. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/akgyivrzn.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.