Adding Level Structure to Supersingular Elliptic Curve Isogeny Graphs

Arpin, Sarah

Journal de théorie des nombres de Bordeaux, Tome 36 (2024) no. 2, pp. 405-443

In this paper, we add the information of level structure to supersingular elliptic curves and study these objects with the motivation of isogeny-based cryptography. Supersingular elliptic curves with level structure map to Eichler orders in a quaternion algebra, just as supersingular elliptic curves map to maximal orders in a quaternion algebra via the classical Deuring correspondence. We study this map and the Eichler orders themselves. We also look at isogeny graphs of supersingular elliptic curves with level structure, and how they relate to graphs of Eichler orders.

Dans cet article, motivés par la cryptographie à base d’isogénies, nous étudions les courbes elliptiques supersingulières munies d’une structure de niveau. De la même manière que la correspondance classique de Deuring associe à une courbe elliptique supersingulière un ordre maximal dans une algèbre de quaternions, on associe à une courbe elliptique supersingulière avec une structure de niveau un ordre d’Eichler. Nous étudions cette correspondance et les ordres d’Eichler eux-mêmes. Nous examinons également les graphes d’isogénies des courbes elliptiques supersingulières avec structure de niveau et leur lien avec les graphes des ordres d’Eichler.

Classification : 11G20, 11T71
Keywords: supersingular, level structure, elliptic curves, isogeny graphs

[1] $p$-adic dynamics of Hecke operators on modular curves, J. Théor. Nombres Bordeaux, Volume 33 (2021) no. 2, pp. 387-431 | DOI | Numdam | Zbl

[2] Arpin, Sarah; Camacho-Navarro, Catalina; Lauter, Kristin; Lim, Joelle; Nelson, Kristina; Scholl, Travis; Sotáková, Jana Adventures in Supersingularland, Exp. Math., Volume 32 (2021) no. 2, pp. 1-28 | DOI

[3] Arpin, Sarah; Chen, Mingjie; Lauter, Kristin; Scheidler, Renate; Stange, Katherine E.; Tran, Ha T. N. Orientations and cycles in supersingular isogeny graphs (2022) | arXiv

[4] Arpin, Sarah; Chen, Mingjie; Lauter, Kristin; Scheidler, Renate; Stange, Katherine E.; Tran, Ha T. N. Orienteering with one endomorphism, Matematica, Volume 2 (2023) no. 3, pp. 523-582 | MR | DOI | Zbl

[5] Bosma, Wieb; Cannon, John; Playoust, Catherine The Magma algebra system. I. The user language, J. Symb. Comput., Volume 24 (1997) no. 3-4, pp. 235-265 Computational algebra and number theory (London, 1993) | DOI | MR | Zbl

[6] Castryck, Wouter; Decru, Thomas An efficient key recovery attack on SIDH, Advances in Cryptology—EUROCRYPT 2023. Part V (Lecture Notes in Computer Science), Volume 14008, Springer, 2023, pp. 423-447 | DOI | MR | Zbl

[7] Castryck, Wouter; Lange, Tanja; Martindale, Chloe; Panny, Lorenz; Renes, Joost CSIDH: an efficient post-quantum commutative group action, Advances in Cryptology—ASIACRYPT 2018. Part III (Lecture Notes in Computer Science), Volume 11274, Springer, 2018, pp. 395-427 | DOI | MR | Zbl

[8] Charles, Denis X.; Goren, Eyal Z.; Lauter, Kristin Cryptographic hash functions from expander graphs, J. Cryptology, Volume 22 (2009) no. 1, pp. 93-113 | DOI | MR | Zbl

[9] Chenu, Mathilde; Smith, Benjamin Higher-degree supersingular group actions, Math. Cryptol., Volume 1 (2022) no. 2, pp. 85-101

[10] Codogni, Giulio; Lido, Guido Spectral Theory of Isogeny Graphs (2023) | arXiv

[11] Colò, Leonardo; Kohel, David Orienting supersingular isogeny graphs, J. Math. Cryptol., Volume 14 (2020) no. 1, pp. 414-437 | MR | DOI | Zbl

[12] De Feo, Luca; Jao, David; Plût, Jérôme Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, J. Math. Cryptol., Volume 8 (2014) no. 3, pp. 209-247 | DOI | MR | Zbl

[13] Delfs, Christina; Galbraith, Steven D. Computing isogenies between supersingular elliptic curves over ${𝔽}_p$, Des. Codes Cryptography, Volume 78 (2016) no. 2, pp. 425-440 | DOI | MR | Zbl

[14] Deuring, Max Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, Abh. Math. Semin. Hansische Univ., Volume 14 (1941), pp. 197-272 | MR | DOI | Zbl

[15] Eichler, Martin Zur Zahlentheorie der Quaternionen-Algebren, J. Reine Angew. Math., Volume 195 (1955), pp. 127-151 | DOI | MR | Zbl

[16] Eichler, Martin The basis problem for modular forms and the traces of the Hecke operators, Modular functions of one variable, I (Proc. Internat. Summer School, Univ. Antwerp, Antwerp, 1972) (Lecture Notes in Mathematics), Volume 320, Springer (1973), pp. 75-151 | MR | Zbl

[17] Eisentraeger, Kirsten; Hallgren, Sean; Leonardi, Chris; Morrison, Travis; Park, Jennifer Computing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs, ANTS XIV. Proceedings of the fourteenth algorithmic number theory symposium (The Open Book Series), Volume 4, Mathematical Sciences Publishers, 2020, pp. 215-232 | Zbl

[18] Feo, Luca De; Kohel, David; Leroux, Antonin; Petit, Christophe; Wesolowski, Benjamin SQISign: compact post-quantum signatures from quaternions and isogenies, Advances in Cryptology—ASIACRYPT 2020. Part I (Lecture Notes in Computer Science), Volume 12491, Springer, 2020, pp. 64-93 | MR | Zbl

[19] Kohel, David Endomorphism rings of elliptic curves over finite fields, Ph. D. Thesis, University of California, Berkely (1996)

[20] Kohel, David; Lauter, Kristin; Petit, Christophe; Tignol, Jean-Pierre On the quaternion $\ell$-isogeny path problem, Cryptology ePrint Archive, Report 2014/505, 2014 (https://eprint.iacr.org/2014/505)

[21] Love, Jonathan; Boneh, Dan Supersingular curves with small noninteger endomorphisms, ANTS XIV—Proceedings of the Fourteenth Algorithmic Number Theory Symposium (The Open Book Series), Volume 4, Mathematical Sciences Publishers (2020), pp. 7-22 | DOI | MR | Zbl

[22] Maino, Luciano; Martindale, Chloe An attack on SIDH with arbitrary starting curve, Cryptology ePrint Archive, Paper 2022/1026, 2022 (https://eprint.iacr.org/2022/1026)

[23] Maino, Luciano; Martindale, Chloe; Panny, Lorenz; Pope, Giacomo; Wesolowski, Benjamin A direct key recovery attack on SIDH, Advances in Cryptology—EUROCRYPT 2023. Part V (Lecture Notes in Computer Science), Volume 14008, Springer, 2023, pp. 448-471 | DOI | MR | Zbl

[24] Onuki, Hiroshi On oriented supersingular elliptic curves, Finite Fields Appl., Volume 69 (2021), 101777, 19 pages | MR | Zbl

[25] Page, Aurel; Wesolowski, Benjamin The supersingular Endomorphism Ring and One Endomorphism problems are equivalent, Cryptology ePrint Archive, Paper 2023/1399, 2023 (https://eprint.iacr.org/2023/1399)

[26] Pizer, Arnold Type Numbers of Eichler Orders, J. Reine Angew. Math., Volume 264 (1973), pp. 76-102 | MR | Zbl

[27] Ribet, Kenneth A. Bimodules and Abelian Surfaces, Algebraic Number Theory — in honor of K. Iwasawa (Advanced Studies in Pure Mathematics), Volume 17, Academic Press Inc.; Kinokuniya Company Ltd., 1989, pp. 359-407 | DOI | Zbl

[28] Robert, Damien Breaking SIDH in polynomial time, Cryptology ePrint Archive, Paper 2022/1038, 2022 (https://eprint.iacr.org/2022/1038) | MR

[29] Roda, Megan Supersingular isogeny graphs with level N structure and path problems on ordinary isogeny graphs, 2019 (Master’s thesis, McGill University)

[30] The Sage Developers SageMath, the Sage Mathematics Software System (Version 8.7) (2019) (https://www.sagemath.org)

[31] Silverman, Joseph H. The Arithmetic of Elliptic Curves, 2nd Edition, Springer, 2009 | MR | DOI

[32] Voight, John Quaternion algebras, Graduate Texts in Mathematics, 288, Springer, 2021, xxiii+885 pages | DOI | MR

[33] Wesolowski, Benjamin Orientations and the Supersingular Endomorphism Ring Problem, Advances in Cryptology—EUROCRYPT 2022 (Dunkelman, Orr; Dziembowski, Stefan, eds.), Springer (2022), pp. 345-371 | MR | DOI | Zbl