Modul:   MAT076  Neuchatel - St.Gallen - Zurich Seminar in Coding Theory and Cryptography

Isogeny graphs with level structure and their spectrum

Vortrag von Dr. Guido Maria Lido

Datum: 15.11.23  Zeit: 15.15 - 16.00  Raum: Y27H25

A familiar object in isogeny based cryptography is the graph whose vertices are supersingular elliptic curves and whose edges are isogenies of fixed degree l. It is immediate to prove that from each vertex there are exactly l+1 outgoing edges, while it is less obvious that such a graph is connected and that it has the Ramanujan property, a property about the spectrum of the adjacency matrix that implies that random walks very soon visit all vertices with the same probability. In our talk we look at a generalization of these graphs, namely graphs whose vertices are pairs (E,T), where E is a supersingular elliptic curve and T is some information on the n-torsion of E (e.g. a basis, a point, a subgroup) for fixed n. It is easy to notice that the secret keys in SIDH are exactly walks in such a generalized isogeny graph, and the public keys are vertices. These graphs can be multipartite, implying that the Ramanujan property is not always satisfied. By studying modular curves over mixed characteristics we relate isogeny graphs to geometric and cohomological objects, which allows us to prove the appropriate modification of the Ramanujan property. The properties of these generalized isogeny graphs are useful for a statistical zero knowledge proof of knowledge of an isogeny, which is part of a work with Basso, Connolly, De Feo, Fouotsa, Morrison, Panny, Patranabis and Wesolowski to generate elliptic curves with unknown endomorphisms.