Adding Level Structure to Supersingular Elliptic Curve Isogeny Graphs
Sarah Arpin1
1 Mathematics Institute Universiteit Leiden Leiden, The Netherlands
Journal de théorie des nombres de Bordeaux, Tome 36 (2024) no. 2, pp. 405-443.

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.

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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/jtnb.1283
Classification : 11G20, 11T71
Mots clés : supersingular, level structure, elliptic curves, isogeny graphs
Sarah Arpin 1

1 Mathematics Institute Universiteit Leiden Leiden, The Netherlands
Licence : CC-BY-ND 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{JTNB_2024__36_2_405_0,
     author = {Sarah Arpin},
     title = {Adding {Level} {Structure} to {Supersingular} {Elliptic} {Curve} {Isogeny} {Graphs}},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {405--443},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {36},
     number = {2},
     year = {2024},
     doi = {10.5802/jtnb.1283},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1283/}
}
TY  - JOUR
AU  - Sarah Arpin
TI  - Adding Level Structure to Supersingular Elliptic Curve Isogeny Graphs
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2024
SP  - 405
EP  - 443
VL  - 36
IS  - 2
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1283/
DO  - 10.5802/jtnb.1283
LA  - en
ID  - JTNB_2024__36_2_405_0
ER  - 
%0 Journal Article
%A Sarah Arpin
%T Adding Level Structure to Supersingular Elliptic Curve Isogeny Graphs
%J Journal de théorie des nombres de Bordeaux
%D 2024
%P 405-443
%V 36
%N 2
%I Société Arithmétique de Bordeaux
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1283/
%R 10.5802/jtnb.1283
%G en
%F JTNB_2024__36_2_405_0
Sarah Arpin. Adding Level Structure to Supersingular Elliptic Curve Isogeny Graphs. Journal de théorie des nombres de Bordeaux, Tome 36 (2024) no. 2, pp. 405-443. doi : 10.5802/jtnb.1283. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1283/

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

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

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

[5] Wieb Bosma; John Cannon; Catherine Playoust 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] Wouter Castryck; Thomas Decru 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] Wouter Castryck; Tanja Lange; Chloe Martindale; Lorenz Panny; Joost Renes 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] Denis X. Charles; Eyal Z. Goren; Kristin Lauter Cryptographic hash functions from expander graphs, J. Cryptology, Volume 22 (2009) no. 1, pp. 93-113 | DOI | MR | Zbl

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

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

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

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

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

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

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

[16] Martin Eichler 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] Kirsten Eisentraeger; Sean Hallgren; Chris Leonardi; Travis Morrison; Jennifer Park 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] Luca De Feo; David Kohel; Antonin Leroux; Christophe Petit; Benjamin Wesolowski 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] David Kohel Endomorphism rings of elliptic curves over finite fields, Ph. D. Thesis, University of California, Berkely (1996)

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

[21] Jonathan Love; Dan Boneh 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] Luciano Maino; Chloe Martindale An attack on SIDH with arbitrary starting curve, Cryptology ePrint Archive, Paper 2022/1026, 2022 (https://eprint.iacr.org/2022/1026)

[23] Luciano Maino; Chloe Martindale; Lorenz Panny; Giacomo Pope; Benjamin Wesolowski 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] Hiroshi Onuki On oriented supersingular elliptic curves, Finite Fields Appl., Volume 69 (2021), 101777, 19 pages | Zbl

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

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

[27] Kenneth A. Ribet 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] Damien Robert Breaking SIDH in polynomial time, Cryptology ePrint Archive, Paper 2022/1038, 2022 (https://eprint.iacr.org/2022/1038)

[29] Megan Roda 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] Joseph H. Silverman The Arithmetic of Elliptic Curves, 2nd Edition, Springer, 2009 | DOI

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

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

Cité par Sources :