Adventures in Supersingularland

Abstract

Supersingular Isogeny Graphs were introduced as a source of hard problems in cryptography by Charles, Goren, and Lauter [6] for the construction of cryptographic hash functions and have been used for key exchange SIKE. The security of such systems depends on the difficulty of finding a path between two random vertices. In this article, we study several aspects of the structure of these graphs. First, we study the subgraph given by j-invariants in ${\mathbb{F}}_p$, using the related isogeny graph consisting of only ${\mathbb{F}}_p$-rational curves and isogenies. We prove theorems on how the connected components thereof attach, stack, and fold when mapped into the full graph. The ${\mathbb{F}}_p$-rational vertices are fixed by the Frobenius involution on the graph, and we call the induced graph the spine. Finding paths to the spine is relevant in cryptanalysis. Second, we present numerous computational experiments and heuristics relating to the position of the spine within the whole graph. These include studying the distance of random vertices to the spine, estimates of the diameter of the graph, how often paths are preserved under the Frobenius involution, and what proportion of vertices are conjugate. We compare some of the heuristics with known results on other Ramanujan graphs.

Keywords:

• elliptic curves
• diameters
• supersingular isogeny graphs

Declaration of Interest

No potential conflict of interest was reported by the author(s).

Acknowledgments

This article is the result of a collaboration started at Alice Silverberg’s 60th birthday conference on open questions in cryptography and number theory https://sites.google.com/site/silverberg2018/. We would like to thank Heidi Goodson for her significant contributions to this project. We are grateful to Microsoft Research for hosting the authors for a follow-up visit. We would like to thank Steven Galbraith, Shahed Sharif, and Katherine E. Stange for helpful conversations. We thank the reviewers for their thoughtful and helpful comments, leading to a many improvements in this article. Authors are listed in alphabetical order; see https://www.ams.org/profession/leaders/ culture/CultureStatement04.pdf.

Additional information

Funding

CCN was partially supported by Universidad de Costa Rica. TS was partially supported by Alfred P. Sloan Foundation grant number G-2014-13575. JS was partially supported by the Dutch Research Council (NWO) through Gravitation-grant Quantum Software Consortium - 024.003.037.