In mathematics, the supersingular isogeny graphs are a class of expander graphs that arise in

computational number theory In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of computational methods for investigating and solving problems in number theory and arithmetic geometry, including algorithms ...

and have been applied in elliptic-curve cryptography. Their vertices represent supersingular elliptic curves over finite fields and their edges represent

isogenies In mathematics, localization of a category consists of adding to a category inverse morphisms for some collection of morphisms, constraining them to become isomorphisms. This is formally similar to the process of localization of a ring; it in genera ...

between curves.

Definition and properties

A supersingular isogeny graph is determined by choosing a large prime number

p

and a small prime number

\ell

, and considering the class of all supersingular elliptic curves defined over the finite field

\mathbb_

. There are approximately

(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, their -invariants, elements of

\mathbb_

) and the edges represent isogenies of degree

\ell

between two curves. The supersingular isogeny graphs are

\ell+1

- regular graphs, meaning that each vertex has exactly

\ell+1

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 In mathematics, the Ramanujan conjecture, due to , states that Ramanujan's tau function given by the Fourier coefficients of the cusp form of weight :\Delta(z)= \sum_\tau(n)q^n=q\prod_\left (1-q^n \right)^ = q-24q^2+252q^3- 1472q^4 + 4830q^5-\ ...

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

\ell

parameter) to develop a key exchange primitive analogous to

Diffie–Hellman key exchange Diffie–Hellman key exchangeSynonyms of Diffie–Hellman key exchange include: * Diffie–Hellman–Merkle key exchange * Diffie–Hellman key agreement * Diffie–Hellman key establishment * Diffie–Hellman key negotiation * Exponential key exc ...

, called supersingular isogeny key exchange, suggested as a form of post-quantum cryptography. However, a leading variant of supersingular isogeny key exchange was broken in 2022 using non-quantum methods.

References

{{reflist, refs= {{citation , last1 = Charles , first1 = Denis X. , last2 = Lauter , first2 = Kristin E. , author2-link = Kristin Lauter , last3 = Goren , first3 = Eyal Z. , doi = 10.1007/s00145-007-9002-x , issue = 1 , journal = Journal of Cryptology , mr = 2496385 , pages = 93–113 , title = Cryptographic hash functions from expander graphs , url = https://eprint.iacr.org/2006/021.pdf , volume = 22 , year = 2009, s2cid = 6417679 {{citation , last1 = Eisenträger , first1 = Kirsten , author1-link = Kirsten Eisenträger , last2 = Hallgren , first2 = Sean , last3 = Lauter , first3 = Kristin , author3-link = Kristin Lauter , last4 = Morrison , first4 = Travis , last5 = Petit , first5 = Christophe , contribution = Supersingular isogeny graphs and endomorphism rings: Reductions and solutions , contribution-url = https://eprint.iacr.org/2018/371.pdf , doi = 10.1007/978-3-319-78372-7_11 , editor1-first = Jesper Buus , editor1-last = Nielsen , editor2-first = Vincent , editor2-last = Rijmen , editor2-link = Vincent Rijmen , mr = 3794837 , pages = 329–368 , publisher = Springer , location = Cham , series = Lecture Notes in Computer Science , title = Advances in Cryptology – EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018, Proceedings, Part III , volume = 10822 , year = 2018, url = http://pure-oai.bham.ac.uk/ws/files/47705132/Supersingular.pdf {{citation , last1 = De Feo , first1 = Luca , last2 = Jao , first2 = David , last3 = Plût , first3 = Jérôme , doi = 10.1515/jmc-2012-0015 , issue = 3 , journal = Journal of Mathematical Cryptology , mr = 3259113 , pages = 209–247 , title = Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies , url = https://eprint.iacr.org/2011/506.pdf , volume = 8 , year = 2014, s2cid = 10873244 {{citation, url=https://arstechnica.com/information-technology/2022/08/sike-once-a-post-quantum-encryption-contender-is-koed-in-nist-smackdown/, magazine=Ars Technica, title=Post-quantum encryption contender is taken out by single-core PC and 1 hour: Leave it to mathematicians to muck up what looked like an impressive new algorithm, first=Dan, last=Goodin, date=August 2, 2022 {{citation , last = Mestre , first = J.-F. , contribution = La méthode des graphes. Exemples et applications , mr = 891898 , pages = 217–242 , publisher = Nagoya University , title = Proceedings of the international conference on class numbers and fundamental units of algebraic number fields (Katata, 1986) , year = 1986 {{citation , last = Pizer , first = Arnold K. , doi = 10.1090/S0273-0979-1990-15918-X , issue = 1 , journal = Bulletin of the American Mathematical Society , mr = 1027904 , pages = 127–137 , series = New Series , title = Ramanujan graphs and Hecke operators , volume = 23 , year = 1990, doi-access = free {{citation , last = Pizer , first = Arnold K. , contribution = Ramanujan graphs , mr = 1486836 , pages = 159–178 , publisher = American Mathematical Society , series = AMS/IP Stud. Adv. Math. , title = Computational perspectives on number theory (Chicago, IL, 1995) , volume = 7 , year = 1998 Application-specific graphs Computational number theory Elliptic curve cryptography Regular graphs