Random walks on supersingular isogeny graphs

• Enric Florit Zacarías ^[1]
  1. [1] Universitat de Barcelona

     Universitat de Barcelona

     Barcelona, España

     
• Localización: Reports@SCM: an electronic journal of the Societat Catalana de Matemàtiques, ISSN-e 2385-4227, Vol. 6, Nº. 1, 2021, págs. 23-34
• Idioma: inglés
• Enlaces
  • Texto completo
• Resumen
  • English

    We survey several aspects of supersingular elliptic curves and their isogeny graphs.

    Isogeny graphs have obtained attention for the last fifteen years due to their uses in quantum-resistant cryptographic protocols. Studying them involves looking at elliptic curves, quaternion algebras, and random walks on (almost) regular graphs, among other topics. In particular, we give the tools necessary to state the Ramanujan property, connecting supersingular curves in characteristic p with modular forms of level p. We also explain the hash function of Charles, Lauter and Goren as an example of application.

  • català

    Aquest article dona una visió general de les corbes el·líptiques supersingulars i dels seus grafs d’isogènies. Els grafs d’isogènies han guanyat atenció durant els darrers quinze anys gràcies a les seves aplicacions per construir protocols criptogràfics resistents a atacs quàntics. El seu estudi involucra parlar de corbes el·líptiques, d’àlgebres de quaternions i de passeigs aleatoris sobre grafs (quasi) regulars. En aquest text, donem les eines necessàries per establir la propietat de Ramanujan, que connecta corbes supersingulars en característica p amb formes modulars de nivell p. A mode d’aplicació, expliquem la funció de hash de Charles, Lauter i Goren.

• Referencias bibliográficas
  • D.J. Bernstein, L. De Feo, A. Leroux, B. Smith, Faster computation of isogenies of large prime degree, in: Proceedings of the Fourteenth Algorithmic...
  • D.X. Charles, K.E. Lauter, E.Z. Goren, “Cryptographic hash functions from expander graphs”, J. Cryptology 22(1) (2009), 93–113.
  • K. Conrad, “Modular forms (draft, CTNT 2016)”, https://ctnt-summer.math.uconn .edu/wp-content/uploads/sites/1632/ 2016/02/CTNTmodularforms.pdf.
  • F. Diamond, J. Shurman, A first course in modular forms, Graduate Texts in Mathematics 228, Springer-Verlag, New York, 2005.
  • E. Florit, B. Smith, “Automorphisms and isogeny graphs of abelian varieties, with applications to the superspecial Richelot isogeny graph”,...
  • S.D. Galbraith, C. Petit, J. Silva, “Identification protocols and signature schemes based on supersingular isogeny problems”, J. Cryptology 33(1)...
  • S. Hoory, N. Linial, A. Wigderson, “Expander graphs and their applications”, Bull. Amer. Math. Soc. (N.S.) 43(4) (2006), 439–561.
  • D.R. Kohel, Computing modular curves via quaternions, in: Fourth CANT Conference: Number Theory and Cryptography, University of Sydney, Dec....
  • D. R. Kohel, Hecke module structure of quaternions, in: Class field theory—its centenary and prospect (Tokyo, 1998), Adv. Stud. Pure Math....
  • [10] D.A. Levin, Y. Peres, E.L. Wilmer, Markov chains and mixing times, With a chapter by James G. Propp and David B. Wilson, American Mathematical...
  • [11] J.-F. Mestre, La m´ethode des graphes. Exemples et applications, in: Proceedings of the international conference on class numbers and fundamental...
  • [12] A.K. Pizer, “Ramanujan graphs and Hecke operators”, Bull. Amer. Math. Soc. (N.S.) 23(1) (1990), 127–137.
  • [13] J.H. Silverman, The arithmetic of elliptic curves, Second edition, Graduate Texts in Mathematics 106, Springer, Dordrecht, 2009.
  • [14] J. V´elu, “Isog´enies entre courbes elliptiques”, C. R. Acad. Sci. Paris S´er. A-B 273 (1971), A238–A241.
  • [15] J. Voight, Quaternion algebras, Graduate Texts in Mathematics 288, Springer, Cham, 2021.