In mathematics, thesupersingular isogeny graphs are a class ofexpander graphs that arise incomputational number theory and have been applied inelliptic-curve cryptography. Their vertices representsupersingular elliptic curves overfinite fields and their edges representisogenies between curves.

A supersingular isogeny graph is determined by choosing a largeprime number${\displaystyle p}$ and a small prime number${\displaystyle \ell }$, and considering the class of allsupersingular elliptic curves defined over thefinite field${\displaystyle {\mathbb{F}}_{p^2}}$. There are approximately${\displaystyle (p+1)/12}$ such curves, each two of which can be related by isogenies. The vertices in the supersingular isogeny graph represent these curves (or more concretely, theirj-invariants, elements of${\displaystyle {\mathbb{F}}_{p^2}}$) and the edges represent isogenies of degree${\displaystyle \ell }$ between two curves.^[1][2][3]

The supersingular isogeny graphs are${\displaystyle \ell +1}$-regular graphs, meaning that each vertex has exactly${\displaystyle \ell +1}$ neighbors. They were proven by Pizer to beRamanujan graphs, graphs with optimalexpansion properties for their degree.^[1][2][4][5] The proof is based onPierre Deligne's proof of theRamanujan–Petersson conjecture.^[4]

One proposal for acryptographic hash function involves starting from a fixed vertex of a supersingular isogeny graph, using the bits of the binary representation of an input value to determine a sequence of edges to follow in a walk in the graph, and using the identity of the vertex reached at the end of the walk as the hash value for the input. The security of the proposed hashing scheme rests on the assumption that it is difficult to find paths in this graph that connect arbitrary pairs of vertices.^[1]

It has also been proposed to use walks in two supersingular isogeny graphs with the same vertex set but different edge sets (defined using different choices of the${\displaystyle \ell }$ parameter) to develop a key exchange primitive analogous toDiffie–Hellman key exchange, calledsupersingular isogeny key exchange,^[2] suggested as a form ofpost-quantum cryptography.^[6] However, a leading variant of supersingular isogeny key exchange was broken in 2022 using non-quantum methods.^[7]

• Application-specific graphs
• Computational number theory
• Elliptic curve cryptography
• Regular graphs

• Articles with short description
• Short description matches Wikidata