Isogeny Cryptography and the Death of SIKE: A Laptop Breaks a NIST Candidate in an Hour

This article has three layers:

1. The intuition: walking through a maze of curves
2. Real-world use: a timeline of SIKE's rise and fall, and where isogeny cryptography stands today (CSIDH, SQIsign)
3. The mathematics: what an isogeny is, Vélu's formulas, the structure of SIDH, why the extra leaked information is fatal and a worked example over $\mathbb{F}_{13}$

Layer 1: The Intuition

1.1 A maze of curves

In the article on elliptic curves, we "walk $k$ steps" on one curve. Isogeny cryptography changes the stage:

• Each "room" is an entire elliptic curve;
• Rooms are connected by doors, and the doors are isogenies (maps that send points on one curve to points on another while preserving addition);
• All the rooms and doors form a huge maze (the isogeny graph), with about $p/12$ rooms, where $p$ has hundreds of digits.

The hard problem: given a starting room and an ending room, find the path between them.

1.2 Exchanging keys like Diffie–Hellman

The idea of SIDH (Supersingular Isogeny Diffie–Hellman) closely resembles Diffie–Hellman:

1. Alice and Bob start from the same public room, and each secretly walks a path;
2. Each publishes their ending room;
3. Each then starts from the other's ending room and "walks again" along their own secret route;
4. Both arrive at the same room (strictly speaking, isomorphic curves), and this is the shared key.

The trouble is in step 3: so that the other side can "walk again along their own route", SIDH must also publish some auxiliary points (where its route sent certain points). These auxiliary points eventually doomed the whole scheme.

1.3 Why it was once so promising

• The shortest keys: among all post-quantum schemes, SIKE's public key was only about 330 bytes, against about 800 bytes for Kyber and hundreds of KB for Classic McEliece;
• Mathematical elegance: it continued the elliptic curve technology stack;
• Ten years without a break.

Layer 2: Real-World Use

2.1 The rise and fall of SIKE

The core tool of the attack is a 1997 theorem by Ernst Kani on "gluing two elliptic curves into an abelian surface". An old result in algebraic geometry suddenly became a key 25 years later.

2.2 The lessons

• The evidence for security was only "nobody has broken it": SIDH was studied for ten years and looked very solid, but it relied on a special problem (with auxiliary points thrown in), not the widely studied "pure" isogeny problem.
• Hybrid deployment saved the day: the Cloudflare and Google trials were all "classical ECDH + SIKE" hybrids, so even with SIKE broken, connections still had the classical algorithm as a backstop. This is exactly why "Post-Quantum Cryptography" emphasizes hybrid schemes.
• Cryptographic diversity: NIST keeps hash-based and code-based schemes alongside lattice schemes, precisely to prevent "one mathematical structure collapsing and taking everything with it".

2.3 Is isogeny cryptography still alive?

It is. The attack only targets SIDH's "public auxiliary points" design:

Layer 3: The Mathematics

3.1 What an isogeny is

An isogeny from elliptic curve $E_1$ to $E_2$ is a non-constant map $\phi: E_1 \to E_2$ such that:

• It is given by rational functions: $\phi(x, y) = \big(r_1(x, y),\ r_2(x, y)\big)$;
• It sends the point at infinity to the point at infinity.

It can be proved that such a map is automatically a group homomorphism: $\phi(P + Q) = \phi(P) + \phi(Q)$. Its kernel $\ker\phi$ is a finite subgroup of $E_1$.

Vélu's formulas: conversely, for any finite subgroup $G$ of $E_1$, there is an isogeny with kernel $G$, and explicit formulas compute the target curve $E_2$, written $E_1 / G$. This is entirely analogous to the abstract algebra fact that "a normal subgroup $N$ gives a quotient group $G/N$ and a natural homomorphism $G \to G/N$".

Tate's theorem: over $\mathbb{F}_q$, an isogeny between $E_1$ and $E_2$ exists if and only if they have the same number of points.

3.2 A worked example: a 2-isogeny

For a curve of the form $E: y^2 = x^3 + ax^2 + bx$, the point $(0, 0)$ has order $2$. The isogeny with kernel $\{O, (0, 0)\}$ has a neat formula:

$$E' : y^2 = x^3 - 2a\,x^2 + (a^2 - 4b)\,x,\qquad \phi(x, y) = \left(\frac{y^2}{x^2},\ \frac{y\,(b - x^2)}{x^2}\right).$$

3.3 The structure of SIDH (simplified)

• Take a prime $p = 2^{e_A} 3^{e_B} - 1$, and a supersingular elliptic curve $E_0$ over $\mathbb{F}_{p^2}$.
• Alice's secret is a cyclic subgroup $\langle A \rangle$ of $E_0$ of order $2^{e_A}$, and she computes $E_A = E_0 / \langle A \rangle$, which amounts to walking $e_A$ steps in the 2-isogeny graph. Bob likewise walks in the 3-isogeny graph.
• So that the other side can "reproduce" her subgroup on $E_A$, Alice must also publish the images $\phi_A(P_B), \phi_A(Q_B)$ of Bob's basis points $P_B, Q_B$ under her isogeny $\phi_A$.
• Finally both arrive at $E_0 / \langle A, B \rangle$, and take its $j$-invariant as the shared key.

3.4 Why the auxiliary points are fatal

Publishing $\phi_A(P_B), \phi_A(Q_B)$ tells an attacker the values of the secret isogeny $\phi_A$ on an entire $3^{e_B}$-torsion subgroup.

The key insight of Castryck and Decru: using Kani's theorem, $\phi_A$ and another known isogeny can be "assembled" into a higher-dimensional isogeny on the product of two curves $E \times E'$. Only when a guess is correct does the target of this higher-dimensional isogeny "split" into a product of two elliptic curves, and checking whether it splits is easy. So an attacker can guess Alice's secret path step by step, trying only a few possibilities at each step.

Later, Robert proved that with these auxiliary points, any isogeny can be reconstructed in polynomial time.

Summary