Paper 2019/1056

Adventures in Supersingularland

Sarah Arpin, Catalina Camacho-Navarro, Kristin Lauter, Joelle Lim, Kristina Nelson, Travis Scholl, and Jana Sotáková

Abstract

In this paper, we study isogeny graphs of supersingular elliptic curves. Supersingular isogeny graphs were introduced as a hard problem into cryptography by Charles, Goren, and Lauter for the construction of cryptographic hash functions. These are large expander graphs, and the hard problem is to find an efficient algorithm for routing, or path-finding, between two vertices of the graph. We consider four aspects of supersingular isogeny graphs, study each thoroughly and, where appropriate, discuss how they relate to one another. First, we consider two related graphs that help us understand the structure: the `spine' $\mathcal{S}$, which is the subgraph of $\mathcal{G}_\ell(\overline{\mathbb{F}_p})$ given by the $j$-invariants in $\mathbb{F}_p$, and the graph $\mathcal{G}_\ell(\mathbb{F}_p)$, in which both curves and isogenies must be defined over $\mathbb{F}_p$. We show how to pass from the latter to the former. The graph $\mathcal{S}$ is relevant for cryptanalysis because routing between vertices in $\mathbb{F}_p$ is easier than in the full isogeny graph. The $\mathbb{F}_p$-vertices are typically assumed to be randomly distributed in the graph, which is far from true. We provide an analysis of the distances of connected components of $\mathcal{S}$. Next, we study the involution on $\mathcal{G}_\ell(\overline{\mathbb{F}_p})$ that is given by the Frobenius of $\mathbb{F}_p$ and give heuristics on how often shortest paths between two conjugate $j$-invariants are preserved by this involution (mirror paths). We also study the related question of what proportion of conjugate $j$-invariants are $\ell$-isogenous for $\ell = 2,3$. We conclude with experimental data on the diameters of supersingular isogeny graphs when $\ell = 2$ and compare this with previous results on diameters of LPS graphs and random Ramanujan graphs.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
number theoryisogeny-based cryptography
Contact author(s)
ja sotakova @ gmail com
Sarah Arpin @ colorado edu
krstnm nlsn @ gmail com
joelle-lim @ berkeley edu
History
2019-09-18: received
Short URL
https://ia.cr/2019/1056
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1056,
      author = {Sarah Arpin and Catalina Camacho-Navarro and Kristin Lauter and Joelle Lim and Kristina Nelson and Travis Scholl and Jana Sotáková},
      title = {Adventures in Supersingularland},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1056},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1056}},
      url = {https://eprint.iacr.org/2019/1056}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.