Constructing and Breaking SIDH

Preliminaries: Elliptic Curves

Fix a field $\mathbb{K}$ with $\mathrm{char}\,\mathbb{K}\neq 2,3$. An algebraic closure of $\mathbb{K}$ is denoted $\overline{\mathbb{K}}$ and is a field extension of $\mathbb{K}$ where every non-constant polynomial with coefficients in $\overline{\mathbb{K}}$ has a root in $\overline{\mathbb{K}}$.

An elliptic curve can be represented by a short Weierstrass equation

$$E:\quad y^2 = x^3 + a x + b,\qquad a,b\in \mathbb{K}.$$

Such a curve is smooth (nonsingular) if and only if the discriminant

$$\Delta \;=\; -16(4a^3+27b^2)$$

is nonzero, which simplifies to the condition $4a^3+27b^2\neq 0$. The $j$-invariant of the curve, which will play a central role in the protocol, is defined as

$$j(E) = 1728\frac{4a^3}{4a^3+27b^2}.$$

Supersingular Curves

Assume $\mathrm{char}\,\mathbb{K}=p>0$. We call $E$ supersingular if the only point satisfying $pP=O$ is $P=O$, equivalently, there are no nonzero $p$-torsion points over $\overline{\mathbb{K}}$. Otherwise the curve is ordinary.

Why supersingular curves.
A practical advantage of supersingular curves is that all supersingular $j$-invariants lie in $\mathbb{F}_{p^2}$. Consequently, we can perform arithmetic entirely over the quadratic field $\mathbb{F}_{p^2}$, avoiding computations in higher extensions which are more expensive.

The $\ell$-torsion subgroup

For $\ell\ge1$, the $\ell$-torsion subgroup consists of all points annihilated by multiplication by $\ell$:

$$E[\ell ] \;=\; \{P\in E(\overline{\mathbb{K}}): \ell P=O\}.$$

Let $K$ be a field with $\operatorname{char}K=p$ and $E/K$ an elliptic curve. Denote by $E[p]$ the $p$-torsion subgroup. Then

$$E[p](\overline K)\ \cong\ \{O\}\quad\text{or}\quad E[p](\overline K)\ \cong\ \mathbb{Z}/p\mathbb{Z}.$$

Equivalently,

$$E \text{ is supersingular } \Longleftrightarrow E[p](\overline K)=\{O\},$$

while for ordinary curves one has $E[p](\overline K)\cong \mathbb{Z}/p\mathbb{Z}$.

Example

Let's find the 2-torsion subgroup for the curve $y^2 = x^3 + x + 3$ defined over $\mathbb{F}_5$. The definition of a 2-torsion subgroup is

$$E[2] \;=\; \{P\in E(\overline{\mathbb{F}_5}): 2P=O\}.$$

If we visualize this, the 2-torsion points are the intersections on the x-axis

so to find these points we need to solve for $x^3 + x + 3 = 0$

### Field and curve

F = GF(5)
E = EllipticCurve(F, [0, 0, 0, 1, 3])     # y^2 = x^3 + 1*x + 3

### --- 2-torsion criterion (char ≠ 2): points with y=0 and x roots of f(x)=x^3 + x + 3

R.<x> = PolynomialRing(F)
f = x^3 + x + 3
print("Over F_5, f factors as:", f.factor())

###  We see only one linear factor (x-1), so only (1,0) is 2-torsion over F_5

P_F5 = E(1,0)
print("Check 2*P_F5 == O?", 2*P_F5 == E(0))

### --- Go to quadratic extension to get full E[2]

K.<u> = GF(5^2)                         ## quadratic extension
EK = E.change_ring(K)
R2.<x> = PolynomialRing(K)
fK = R2(f)
print("Over F_25, f factors as:", fK.factor())

### Collect all 2-torsion points over F_25: the three roots give (x_i, 0), plus O

roots = [r for (r, mult) in fK.roots()]  ## three distinct roots in K (since char!=2 and Δ ≠ 0)
E2 = [EK(0)] + [EK(r, K(0)) for r in roots]
print("E[2] over F_25 has size:", len(E2))
print("E[2] points:")
for Q in E2:
    print(" ", Q)

### Sanity: each nonzero 2-torsion point has order 2

print("Orders of nonzero 2-torsion points:")
for Q in E2[1:]:
    print(Q.order())

After running the code we see that there are 3 non-trivial 2-torsion points along with the point at infinity in the subgroup.

Isogenies

An isogeny $\varphi:E_1\to E_2$ is a non-constant group homomorphism given by rational functions. Such maps are automatically surjective with finite kernel. On short Weierstrass models, after normalizing so that $\varphi(O)=O$, an isogeny takes the affine form

$$\varphi(x,y)=\Big(\frac{f_1(x)}{g_1(x)},\; y\cdot\frac{f_2(x)}{g_2(x)}\Big),$$

where the degree is defined as $\deg\varphi=\max\{\deg f_1,\deg g_1\}$. When $\varphi$ is separable, meaning the derivative $(\tfrac{f_1}{g_1})'$ is not identically zero, the degree equals the size of the kernel: $\deg\varphi=\#\ker\varphi$.

Supersingularity is preserved by isogeny:

$$E_1 \text{ supersingular } \Longleftrightarrow E_2 \text{ supersingular.}$$

Example

Let's look at the isogeny from the elliptic curve $y^2 = x^3 + x + 3$ defined over $\mathbb{F}_5$ to itself defined by the multiplication-by-2 map. The isogeny takes every point $P$ to its double

$$\varphi: P \to 2P$$

### Field and curve

F = GF(5)
E = EllipticCurve(F, [0, 0, 0, 1, 3])     ## y^2 = x^3 + 1*x + 3
### --- Go to quadratic extension

K.<u> = GF(5^2)                         ## quadratic extension
EK = E.change_ring(K)

Xmap, Ymap = EK.multiplication_by_m(2)
print("x(2P) =", Xmap)
print("y(2P) =", Ymap)

So the map for doubling a point is

$$(x,y) \to \big( \dfrac{x^4 - 2x^2 + x + 1}{-x^3 - x + 2}, \dfrac{-2x^6y - xy + y}{-x^6 - 2x^4 - x^3 - x^2 - x + 1} \big)$$

The kernel for this isogeny is exactly the 2-torsion subgroup we saw earlier, the cardinality of which was 4 and that is consistent with the degree of our isogeny.

Composition and Duality

If $\varphi:E\to E'$ and $\psi:E'\to E''$ are isogenies, their composition

$$\psi\circ\varphi:\ E \longrightarrow E''$$

is again an isogeny, and its degree multiplies:

$$\deg(\psi\circ\varphi)=\deg\psi\cdot\deg\varphi.$$

An isomorphism is just an isogeny of degree $1$ whose kernel is $\{O\}$; composing an isomorphism with its inverse is the identity. For a general isogeny $\varphi:E\to E'$ of degree $d>1$, there is no inverse in the usual sense. Instead, there exists a unique dual isogeny $\widehat{\varphi}:E'\to E$ that "acts like" an inverse up to multiplication-by-$d$:

$$\widehat{\varphi}\circ \varphi=[d]\ \text{ on }E,\qquad \varphi\circ \widehat{\varphi}=[d]\ \text{ on }E'.$$

Thus the composition returns to the same curve and its kernel is the full $d$-torsion:

$$\ker(\widehat{\varphi}\circ\varphi)=E[d],\qquad \ker(\varphi\circ\widehat{\varphi})=E'[d].$$

Isomorphisms and the $j$-Invariant

An isomorphism $\psi: E_1 \to E_2$ over $\mathbb{K}$ is an isogeny of degree 1, taking the form

$$(x,y)\longmapsto (u^2x,\;u^3y),\qquad u\in\mathbb{K}^\times.$$

Isomorphisms preserve the $j$-invariant: if $\psi:E_1\to E_2$ is an isomorphism, then $j(E_1)=j(E_2)$. Over an algebraically closed field, the converse holds: two elliptic curves are isomorphic if and only if their $j$-invariants coincide.

The number of supersingular $j$-invariants in characteristic $p$ is

$$s_p \;=\; \Big\lfloor \frac{p}{12}\Big\rfloor + \varepsilon_p, \quad \varepsilon_p\in\{0,1,2\}, \quad s_2=s_3=1,$$

giving approximately $s_p\approx p/12$ such invariants.

Constructing Isogenies from Kernels

In some applications, we know the kernel of a desired isogeny but need to construct the explicit map. Specifically, given an elliptic curve $E$ and a finite subgroup $G \subseteq E$, we wish to compute the isogeny $\varphi: E \to E/G$ whose kernel is precisely $G$.

Vélu's formulas solve this problem. They take as input the coefficients $(a, b)$ defining the curve $E: y^2 = x^3 + ax + b$ and the list of all nonzero points in the subgroup $G$ (or simply a generator when $G$ is cyclic). From this data, Vélu's formulas produce:

1. The rational functions $\varphi(x,y) = (X(x), Y(x,y))$ defining the isogeny, and
2. The coefficients $(a', b')$ of the codomain curve $E/G: y^2 = x^3 + a'x + b'$.

For a cyclic subgroup $\langle P\rangle$ of order $m$, the resulting isogeny

$$\varphi:\ E \longrightarrow E/\langle P\rangle$$

is separable with $\deg\varphi = m = \#\ker\varphi$. This kernel-first approach is fundamental to isogeny-based cryptography, where parties construct secret isogenies by choosing secret kernel generators.

### Base curve over F_5, then extend to F_{5^2} so E[2] is fully defined

F = GF(5)
E = EllipticCurve(F, [0,0,0,1,3])           ## y^2 = x^3 + x + 3
K.<u> = GF(5^2)
EK = E.change_ring(K)

### E[2] points: roots of x^3 + x + 3 with y=0 

R.<x> = PolynomialRing(K)
f = x^3 + x + 3
roots = [r for (r, _) in f.roots()]         ## 3 distinct roots in K
E2_pts = [EK(r, K(0)) for r in roots]       ## the three nonzero 2-torsion points

### Pass a LIST OF GENERATORS for the kernel subgroup (any two independent E[2] points)

phi2 = EllipticCurveIsogeny(EK, E2_pts[:2])               ## uses Vélu with kernel generated by these points
E2cod = phi2.codomain()
print("deg(phi2) =", phi2.degree())         ## should be 4

### Kernel sanity: all of E[2] (including O) maps to O

for Q in [EK(0)] + E2_pts:
    assert phi2(Q) == E2cod(0)
print("Kernel OK (E[2] → O).")

In SageMath the EllipticCurveIsogeny constructor takes as input a starting curve and a point or list of points that generate the kernel and uses Vélu's formulas to construct the isogeny.

The SIDH Protocol

Protocol Parameters

SIDH begins with a prime of the form

$$p = 2^{e_A}3^{e_B} - 1,$$

where $e_A$ and $e_B$ are positive integers chosen such that $2^{e_A} \approx 3^{e_B}$. All computations are performed over the quadratic extension field $\mathbb{F}_{p^2}$.

This prime structure is carefully chosen. For a supersingular curve $E$ defined over $\mathbb{F}_{p^2}$, the number of $\mathbb{F}_{p^2}$-rational points is

$$\#E(\mathbb{F}_{p^2}) = (p+1)^2,$$

and the group structure is

$$E(\mathbb{F}_{p^2}) \cong \mathbb{Z}_{p+1} \times \mathbb{Z}_{p+1}.$$

Since $p+1 = 2^{e_A}3^{e_B}$, the curve contains points of every order dividing $2^{e_A}3^{e_B}$. This enables Alice and Bob to independently traverse their respective isogeny graphs using powers of 2 and 3.

The Isogeny Graphs

The protocol operates on two supersingular isogeny graphs sharing the same vertex set but with different edge structures.

Vertices represent isomorphism classes of supersingular elliptic curves over $\mathbb{F}_{p^2}$, uniquely identified by their $j$-invariants.

Edges are defined by isogenies: for a prime $\ell$ coprime to $p$, an $\ell$-edge connects vertices $[E]$ and $[E']$ if there exists a separable $\ell$-isogeny $\varphi: E \to E'$ over $\mathbb{F}_{p^2}$.

For $\ell \neq p$, the $\ell$-torsion subgroup has structure

$$E[\ell] \cong (\mathbb{Z}/\ell\mathbb{Z})^2,$$

containing exactly $\ell + 1$ cyclic subgroups of order $\ell$. Each cyclic subgroup $G \subseteq E[\ell]$ determines a unique separable isogeny $\varphi_G: E \to E/G$ via Vélu's formulas. Consequently, each vertex in the $\ell$-isogeny graph has exactly $\ell + 1$ neighbors.

For Alice's 2-isogeny graph, each vertex has 3 outgoing edges (with negligible exceptions). For Bob's 3-isogeny graph, each vertex has 4 outgoing edges.

Public Parameters

The protocol requires a fixed supersingular starting curve $E_0$ defined over $\mathbb{F}_{p^2}$ and two pairs of torsion basis points:

$$\{P_A, Q_A\} \subset E_0[2^{e_A}], \qquad \{P_B, Q_B\} \subset E_0[3^{e_B}].$$

These bases generate the torsion subgroups

$$E_0[2^{e_A}] \cong (\mathbb{Z}/2^{e_A}\mathbb{Z})^2, \qquad E_0[3^{e_B}] \cong (\mathbb{Z}/3^{e_B}\mathbb{Z})^2.$$

Key Generation

Alice's key generation:
Alice selects a secret integer $k_A \in \{0, 1, \ldots, 2^{e_A} - 1\}$ and constructs the kernel generator

$$R_A = P_A + [k_A]Q_A.$$

The cyclic subgroup $G_A = \langle R_A \rangle \subset E_0[2^{e_A}]$ has order $2^{e_A}$. Alice computes the isogeny

$$\varphi_A: E_0 \to E_A := E_0/G_A$$

as a composition of $e_A$ successive degree-2 isogenies, effectively traversing $e_A$ edges in the 2-isogeny graph.

Alice's public key is

$$\text{PK}_A = (E_A, \varphi_A(P_B), \varphi_A(Q_B)).$$

The public key includes both the image curve $E_A$ and the images of Bob's torsion basis points under her secret isogeny.

Bob's key generation:
Bob follows the analogous procedure using 3-power isogenies. He selects a secret $k_B \in \{0, 1, \ldots, 3^{e_B} - 1\}$ and constructs

$$R_B = P_B + [k_B]Q_B, \qquad G_B = \langle R_B \rangle \subset E_0[3^{e_B}].$$

Bob computes the isogeny

$$\varphi_B: E_0 \to E_B := E_0/G_B$$

as a composition of $e_B$ successive degree-3 isogenies.

Bob's public key is

$$\text{PK}_B = (E_B, \varphi_B(P_A), \varphi_B(Q_A)).$$

Shared Secret Computation

Alice's computation:
Upon receiving Bob's public key, Alice constructs

$$S'_A = \varphi_B(P_A) + [k_A]\varphi_B(Q_A) = \varphi_B(P_A + [k_A]Q_A) = \varphi_B(R_A),$$

using the fact that isogenies are group homomorphisms. The cyclic subgroup $\langle S'_A \rangle$ equals $\varphi_B(G_A)$, the image of Alice's original kernel under Bob's isogeny.

Alice then computes

$$\phi'_A: E_B \to E_{BA} := E_B / \langle S'_A \rangle.$$

Bob's computation:
Bob performs the symmetric computation, constructing

$$S'_B = \varphi_A(P_B) + [k_B]\varphi_A(Q_B) = \varphi_A(R_B)$$

so that $\langle S'_B \rangle = \varphi_A(G_B)$, and computing

$$\phi'_B: E_A \to E_{AB} := E_A / \langle S'_B \rangle.$$

The shared secret:
A fundamental theorem of isogeny theory guarantees a canonical isomorphism

$$(E_0/G_A)/\varphi_A(G_B) \cong (E_0/G_B)/\varphi_B(G_A),$$

which implies $E_{AB} \cong E_{BA}$ and therefore $j(E_{AB}) = j(E_{BA})$.

The shared secret is the common $j$-invariant:

$$\boxed{\text{Shared secret} = j(E_{AB}) = j(E_{BA})}$$

Both parties arrive at isomorphic curves and compute the same $j$-invariant. The security of SIDH relies on the computational difficulty of determining the isogeny $\varphi_A$ (or $\varphi_B$) from knowledge of $E_0$ and $E_A$ (or $E_B$), a problem believed to be hard even for quantum computers.

Example Walkthrough

For our example we choose the prime to be $p = 2^43^3 -1$, the starting curve $E_0 \text{ is } y^2=x^3 + a_0x^2 + x$ where $a_0 = 329i+ 423$. Next we fix the basis points for Alice and Bob

$$\begin{aligned} P_A := (100i + 248, 304i + 199) \quad Q_A := (426i + 394, 51i + 79) \\ P_B := (358i + 275, 410i + 104) \quad Q_B := (20i + 185, 281i + 239) \end{aligned}$$

Alice generates a secret number $k_A = 11$ and computes the kernel generator point

$$S_A = P_A + [k_A]Q_A = (271i + 79, 153i + 430).$$

This point has order 16 which could express a degree 16 isogeny or a composition of 4 degree 2 isogenies. The latter is favorable for computational purposes so Alice computes the 4 "hops" in the isogeny graph using Vélu's formulas at each step and lands on the image curve which will be her public key (encoded by its Montgomery parameter) along with Bob's basis points under the same secret isogeny

$$PK_A = (\varphi_A(E_0), \varphi_A(P_B), \varphi_A(Q_B)) \\ = (423i + 179,(142i + 183, 119i + 360),(220i + 314, 289i + 10))$$

The below image shows the "hops" Alice takes on the $j$-invariants of her respective curves.

Bob also chooses a secret parameter $k_B = 2$ and computes the corresponding generator point

$$S_B = P_B + [k_B]Q_B = (122i + 309, 291i + 374).$$

which has order 27 meaning Bob can interpret it as a composition of 3 degree 3 isogenies. His public key is also the resulting curve and Alice's basis points under his secret isogeny

$$PK_B = (\varphi_B(E_0), \varphi_B(P_A), \varphi_B(Q_A)) \\ = (273i + 76,(187i + 226, 43i + 360),(325i + 415, 322i + 254))$$

Now for the shared secret computation, Alice takes Bob's codomain curve from his public key as the starting point then calculates the kernel using the image of her basis points that Bob provided

$$S'_A = \varphi_B(P_A) + [k_A]\varphi_B(Q_A) = (125i + 357, 415i + 249).$$

and just like before computes the image curve using the kernel generated by $S'_A$.

Bob goes through the same steps and ends up with

$$S'_B = \varphi_A(P_B) + [k_B]\varphi_A(Q_B) =(393i + 124, 187i + 380).$$

After these steps they both land on the node with $j$-invariant = 243, and this shared secret can be used to derive cryptographic keys.

The Castryck-Decru Attack

The Security Problem and Attack Strategy

The security of SIDH rests on the hardness of the following problem: given two supersingular curves $E_0$ and $E_B=E_0/\langle R_B\rangle$, recover the secret cyclic kernel $\langle R_B\rangle$ that defines the separable isogeny of degree $3^{e_B}$.

When walking along a 3-isogeny path, there are 4 degree-3 choices at the first step. After ruling out the dual edge (which returns to the previous curve), there remain 3 choices at each subsequent step. If an oracle existed that could test whether a proposed next 3-isogeny lies on the secret path, one could recover the entire path by testing the 3 candidates at each level.

The Castryck-Decru attack constructs such an oracle by lifting from elliptic curves (dimension 1) to principally polarized abelian surfaces (dimension 2), where testing whether the surface is a Jacobian versus a product of elliptic curves provides the required signal.

The Oracle Construction

The core idea is based on a theorem by Kani relating isogeny diamonds to products of elliptic curves.

The attack constructs such a diamond in dimension 2 by:

1. Starting with a product of elliptic curves $C \times E_i^{\text{cand}}$
2. Using a $(2^{e_A}, 2^{e_A})$-isogeny that "glues" the product into a genus-2 Jacobian
3. Computing a chain of Richelot $(2,2)$-isogenies (the higher-dimensional analogue of degree-2 isogenies between elliptic curves)
4. Testing whether the final codomain splits back into a product

The key insight is that the final surface is a product of elliptic curves if and only if the candidate 3-isogeny $E_{i-1} \to E_i^{\text{cand}}$ lies on Bob's secret path. This follows from Kani's theorem combined with the specific structure of the diamond.

Since a random principally polarized abelian surface of dimension 2 is a Jacobian with probability approximately $1 - 1/p$, while a product occurs with probability roughly $1/p$, this test reliably distinguishes correct from incorrect candidates.

The Attack Algorithm

The attack recovers Bob's secret isogeny $\varphi_B: E_0 \to E_B = E_0/\langle R_B\rangle$ of degree $3^{e_B}$ by determining it one step at a time. Since Bob computes his isogeny as a composition of $e_B$ successive degree-3 isogenies, the attacker recovers each individual 3-isogeny in the chain using the dimension-2 oracle.

Input

• The starting curve $E_0$
• The image curve $E_B = E_0/\langle R_B\rangle$
• The torsion images $(\varphi_B(P_A), \varphi_B(Q_A))$ from Bob's public key, where $\{P_A, Q_A\}$ generates $E_0[2^{e_A}]$

The Iterative Recovery Process

Bob's secret isogeny is a composition of $e_B$ degree-3 isogenies:

$$\varphi_B = \varphi_{e_B} \circ \varphi_{e_B-1} \circ \cdots \circ \varphi_2 \circ \varphi_1: E_0 \to E_1 \to E_2 \to \cdots \to E_{e_B} = E_B$$

The attack recovers these isogenies sequentially. At step $i$, having already recovered $\varphi_1, \ldots, \varphi_{i-1}$, the attacker knows the current curve $E_{i-1}$ and seeks to determine $\varphi_i: E_{i-1} \to E_i$.

Step $i$: Recovering the next 3-isogeny

1. Identify the candidate edges:
   From curve $E_{i-1}$, there are 4 outgoing 3-isogenies. However, one of these is the dual of the incoming isogeny $\varphi_{i-1}$, which can be ruled out (except at the first step). This leaves 3 candidate edges to test.

2. Construct the auxiliary isogeny:
   The oracle requires an auxiliary isogeny of degree $c = 2^{e_A} - 3^{e_B - i}$. Assuming $E_0$ has a known endomorphism (such as $2i$ satisfying $2i \circ 2i = [-4]$), and assuming $c$ can be written as $c = u^2 + 4v^2$, construct the degree-$c$ endomorphism:

   $$\gamma: E_0 \to C, \quad \gamma = [u] + [v] \circ 2i.$$

   Evaluate $\gamma$ on the generators to obtain:

   $$P_c = \gamma(P_A), \qquad Q_c = \gamma(Q_A) \in C[2^{e_A}].$$

3. Test each candidate:
   For each of the 3 candidate isogenies $\varphi_i^{\text{cand}}: E_{i-1} \to E_i^{\text{cand}}$:

   a. Push the torsion through the candidate path:
   Compute the images of the generators under the composition of the recovered path and the candidate:

   $$P_i^{\text{cand}} = \varphi_i^{\text{cand}} \circ \cdots \circ \varphi_1(P_A), \qquad Q_i^{\text{cand}} = \varphi_i^{\text{cand}} \circ \cdots \circ \varphi_1(Q_A).$$

   b. Form the diamond kernel:
   Consider the $(2^{e_A}, 2^{e_A})$-subgroup of $C \times E_i^{\text{cand}}$ generated by:

   $$\langle (P_c, P_i^{\text{cand}}), (Q_c, Q_i^{\text{cand}}) \rangle.$$

   This subgroup always defines a $(2^{e_A}, 2^{e_A})$-isogeny.

   c. Glue into dimension 2:
   The first step of this $(2^{e_A}, 2^{e_A})$-isogeny is a gluing map that takes the product of elliptic curves $C \times E_i^{\text{cand}}$ to the Jacobian of a genus-2 curve $\text{Jac}(H)$.

   d. Compute the Richelot chain:
   Compose $e_A - 1$ successive Richelot $(2,2)$-isogenies:

   $$\text{Jac}(H_0) \to \text{Jac}(H_1) \to \cdots \to \text{Jac}(H_{e_A-1}) \to A_{e_A}.$$

   e. Test for splitting:
   After the chain of Richelot isogenies, check whether the final $(2,2)$-isogeny splits—that is, whether its codomain $A_{e_A}$ is a product of two elliptic curves rather than a Jacobian of a genus-2 curve.

   The test is straightforward: in the Richelot formulas, a certain determinant $\delta$ appears. The codomain is a product if and only if $\delta = 0$.

   f. Apply Kani's theorem:

   • If $\delta = 0$ (splits): By Kani's theorem, this happens if and only if the candidate $\varphi_i^{\text{cand}}$ lies on the true secret path. The attacker has found the correct next edge.
   • If $\delta \neq 0$ (Jacobian): The candidate is incorrect. Since the probability that a random abelian surface is a product is approximately $1/p$, this test reliably distinguishes correct from incorrect candidates.

4. Advance to the next step:
   Once the unique candidate that makes the diamond split is identified, set $\varphi_i = \varphi_i^{\text{cand}}$ and update the current curve to $E_i$. Proceed to step $i+1$.

Termination and Output

After $e_B$ iterations, the complete chain $\varphi_1 \circ \varphi_2 \circ \cdots \circ \varphi_{e_B}$ has been recovered. This determines Bob's secret isogeny $\varphi_B$ and its kernel $\langle R_B \rangle$.

In terms of Bob's secret key: if Bob's private key is the integer $k_B \in [0, 3^{e_B})$ such that $\ker \varphi_B = \langle P_B + [k_B]Q_B \rangle$, then the attack recovers $k_B$ one base-3 digit at a time.

Why the Auxiliary Information Enables the Attack

A crucial aspect of the attack is its reliance on the torsion point information in SIDH public keys. Recall that Alice's public key includes not just her image curve $E_A$, but also the images $\varphi_A(P_B), \varphi_A(Q_B)$ of Bob's torsion basis.

This auxiliary information is essential for SIDH's key exchange mechanism—without it, Bob cannot compute the shared secret. However, it also provides the attacker with the ability to:

1. Push torsion points through candidate isogeny paths
2. Construct the $(2^{e_A}, 2^{e_A})$-subgroups needed for the gluing maps
3. Build the dimension-2 diamonds that form the oracle

Without this torsion point information, the attack does not apply. This observation led to the development of SIDH variants that attempt to hide or obfuscate the torsion point images, though designing secure and efficient alternatives remains an active area of research.

Generalizations and Variants

The simplified description above assumes:

• The starting curve is $E_0$ itself (no intermediate isogeny to a special curve)
• Each iteration recovers a single 3-isogeny (one base-3 digit at a time)
• The degree $c = 2^{e_A} - 3^{e_B - i}$ has the form $u^2 + 4v^2$

In the more general attack:

• The starting curve $E_0$ may differ from a curve with known endomorphisms, requiring an initial isogeny $\tau: E_0 \to E_{\text{start}}$ where $E_{\text{start}}$ has explicit endomorphisms
• Each iteration may recover multiple 3-isogenies at once (larger steps, recovering multiple base-3 digits), reducing the total number of iterations at the cost of more candidates per iteration
• The construction of the auxiliary isogeny may use different quadratic forms or more sophisticated techniques when $c$ does not have the form $u^2 + 4v^2$

Regardless of these variations, the core logic remains the same: use the dimension-2 oracle to test candidate edges one step at a time until the entire secret path is recovered.

Impact and Aftermath

The Castryck-Decru attack, published in July 2022, completely broke SIDH security. Within hours of the preprint appearing on ePrint, the attack was implemented and verified against SIDH implementations. The attack applies to all standard SIDH parameter sets and cannot be mitigated by simply increasing key sizes.

This development eliminated SIDH as a candidate for post-quantum cryptography standardization. The attack highlighted the danger of including auxiliary information (torsion point images) in isogeny-based protocols, spurring research into alternative designs that either avoid this information or protect it through other means.

Acknowledgements

This write-up closely follows and synthesizes material from the three references listed below.

• “Supersingular isogeny key exchange for beginners”
• “An efficient key recovery attack on SIDH”
• “The supersingular isogeny Diffie–Hellman key exchange”

The author gratefully acknowledges these works for their clear notation, precise statements of facts, and concrete algorithmic descriptions, which this post reproduces and condenses for a cohesive, technically faithful walkthrough of SIDH and its break.