Isogenies and the supersingular graph
An isogeny is a map from one elliptic curve to another that respects addition. On supersingular curves they form a small, tightly connected graph, and every isogeny-based scheme, from SIDH to SQIsign, is built on the difficulty of finding paths in it.
- Prime used here
- p = 431 = 24 · 33 − 1, the prime of Costello's tutorial
- The graph
- 37 supersingular curves over F4312, 54 distinct 2-isogeny edges, diameter 7
- Checked at build time
- The modular polynomial, the vertex count, Velu's formulas as a homomorphism on 20 random pairs of points, and the curve's group order
What an isogeny is
An isogeny φ: E → E' is a non-constant map between elliptic curves, given by rational functions, that sends the identity to the identity. It is then automatically a group homomorphism: φ(P + Q) = φ(P) + φ(Q). Its kernel is a finite subgroup of E, and for the separable isogenies used in cryptography the degree of φ is the size of that kernel.
Conversely, every finite subgroup G of E is the kernel of an isogeny, unique up to isomorphism of the target, and Vélu's formulas compute it. For a kernel of order 2, generated by a point (x0, 0), they are short:
φ(x, y) = ( x + t/(x − x0), y·(1 − t/(x − x0)2) ) Vélu's formulas for a 2-isogeny from y2 = x3 + ax + b.
Worked over F4312 = F431(i), with i2 = −1: the curve y2 = x3 + (177 + 214i)x + (131 + 19i) has j-invariant 118 + 209i and a 2-torsion point with x0 = 152 + 55i. Then t = 74 + 378i and w = 371 + 324i, so the target curve is y2 = x3 + (238 + 48i)x + (120 + 337i), with j-invariant 315 + 299i. The point U = (180 + 238i, 22 + 72i) maps to (94 + 321i, 297 + 170i). The build checks that φ(U + V) = φ(U) + φ(V) for 20 random pairs of points.
Curves up to isomorphism
Many equations describe the same curve. Over an algebraically closed field, two curves are isomorphic exactly when they have the same j-invariant, j = 1728·4a3/(4a3 + 27b2). So an isogeny graph takes j-invariants as vertices, and joins two of them when an isogeny of the chosen degree connects the curves. The modular polynomial Φ2(X, Y) records exactly this for degree 2: Φ2(j, j') = 0 if and only if there is a 2-isogeny between curves with those j-invariants. Finding the neighbours of j means finding the roots of the cubic Φ2(j, Y).
The supersingular graph
A supersingular curve over a field of characteristic p is one with no points of order p. There are few of them: every one is defined over Fp2, and there are ⌊p/12⌋ + ε of them, with ε between 0 and 2 depending on p mod 12. For p = 431 that is 35 + 2 = 37, and the code that builds this page finds exactly that many by starting at j = 1728 and following roots of Φ2.
Every vertex has three 2-isogenies leaving it, counted with multiplicity, so the graph is 3-regular; the vertices j = 4, 242 have an isogeny back to themselves. Pizer showed that these graphs are Ramanujan: optimal expanders, in which a random walk reaches an almost uniformly random vertex after O(log p) steps. The layers below show the expansion from j = 1728: the frontier roughly doubles at each step until the graph runs out, and every vertex is within 7 steps.
| Distance from 1728 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| Vertices | 1 | 1 | 2 | 4 | 6 | 10 | 8 | 5 |
21 of the 37 j-invariants lie in the subfield F431: 0, 4, 19, 61, 67, 102, 107, 125, 143, 150, 189, 234, 241, 242, 316, 319, 356, 358, 381, 419, 422. These are the curves defined over Fp, the setting of CSIDH, where the isogenies form a commutative group action instead of a graph walk.
Walks as keys
A walk of e steps is an isogeny of degree 2e. Here is one of 6 steps, the highlighted path in the figure:
Publishing the endpoint and keeping the walk secret is the core of every isogeny key. With 37 vertices anyone can recover a path; with p near 2256 the graph has about 2252 vertices, and finding a path between two given curves is the supersingular isogeny path problem. The best classical algorithm, by Wesolowski in 2026, takes time and memory p1/3+o(1). Knowing the endomorphism ring of the endpoints makes paths easy to find, and the two problems are equivalent; this is the Deuring correspondence at work, and it is what SQIsign's signatures prove knowledge of.
The starting curve y2 = x3 + x has exactly 186,624 = 4322 points over F4312, counted point by point at build time. Its group is (Z/432Z)2, which contains every point of order 24 and 33. That is why SIDH used primes of the form 2a3b − 1: so that walks of 2- and 3-isogenies could be computed from rational torsion points. Publishing the images of those points is what the 2022 attacks exploited.
Primary sources
- L. De Feo, "Mathematics of isogeny based cryptography" (2017)
- C. Costello, "Supersingular isogeny key exchange for beginners", SAC 2019
- A. K. Pizer, "Ramanujan graphs and Hecke operators", Bulletin of the AMS 23 (1990)
- D. Charles, E. Goren and K. Lauter, "Cryptographic hash functions from expander graphs", Journal of Cryptology 22 (2009)
- B. Wesolowski, "The supersingular isogeny problem in time and memory p1/3+o(1)" (2026)