Supersingular isogeny graph

In mathematics, the supersingular isogeny graphs are a class of expander graphs that arise in computational number theory and have been applied in elliptic-curve cryptography. Their vertices represent supersingular elliptic curves over finite fields and their edges represent isogenies between curves.
Definition and properties.
A supersingular isogeny graph is determined by choosing a large prime number formula_1 and a small prime number formula_2, and considering the class of all supersingular elliptic curves defined over the finite field formula_3. There are approximately formula_4 such curves, each two of which can be related by isogenies. The vertices in the supersingular isogeny graph represent these curves (or more concretely, their -invariants, elements of formula_3) and the edges represent isogenies of degree formula_2 between two curves.
The supersingular isogeny graphs are formula_7-regular graphs, meaning that each vertex has exactly formula_7 neighbors. They were proven by Pizer to be Ramanujan graphs, graphs with optimal expansion properties for their degree. The proof is based on Pierre Deligne's proof of the Ramanujan–Petersson conjecture.
Cryptographic applications.
One proposal for a cryptographic 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.
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 formula_2 parameter) to develop a key exchange primitive analogous to Diffie–Hellman key exchange, called supersingular isogeny key exchange.
Additional cryptographic methods based on these graphs include signature schemes and public-key cryptography. They have been suggested as a form of post-quantum cryptography: , there are no known subexponential-time methods for breaking these schemes, even on quantum computers.