Supersingular Isogeny Key Exchange for Not-Quite Beginners

I recently read a great introductory paper on Supersingular Isogeny Diffie-Hellman (SIDH) by Craig Costello and wanted to summarize just the math of it (with some simplifications) for myself. Hopefully this summary is clear enough to also be useful to people who aren’t myself.

§ Background

We deal with supersingular (we won’t define this word) elliptic curves defined over finite fields of the form $\mathbb{F}_{p^2}$.

For SIDH, we deal only with curves such that $E(\mathbb{F}_{p^2}) \cong \mathbb{Z}_{p+1} \times \mathbb{Z}_{p+1}$. The kernel of the left multiplication map $P \to [a]P$ is of the form $\mathbb{Z}_a \times \mathbb{Z}_a$. We say that a map $\phi: E \to E’$ is an $\ell$-isogeny iff $|\ker \phi| = \ell$. Notice that $\ell$-isogenies only exist for $\ell \mid p+1$. Every $\ell$-isogeny $\phi: E \to E’$ also has an associated $\ell$-isogeny, called the dual isogeny $\psi: E’ \to E$, such that $\phi \circ \psi$ is the left-multiplication map $[\ell]$. Vélu’s formulas tell us that every subgroup $G \leq E$ corresponds to a unique isogeny out of $E$ (to some curve $E’$) with kernel G. They also tell us how to construct an isogeny given its desired kernel.

Claim: On a supersingular curve $E$ of the form above, for any prime $\ell \mid p+1$, there are exactly $\ell+1$ nontrivial $\ell$-isogenies out of $E$.

Proof: Using Vélu’s formulas, it suffices to show that E has exactly $\ell+1$ many subgroups of prime order $\ell$. Firstly, since these are of order $\ell$, they all must be subgroups of $E[\ell] \cong \mathbb{Z}_\ell \times \mathbb{Z}_\ell$. Let $P$ and $Q$ denote the free generators of $E[\ell]$. Consider the family of cyclic subgroups generated by $P + [k]Q$ for $0 \leq k < \ell$. We claim that these are not only distinct, but disjoint. Suppose for distinct $k$, $k’$ that

for some integers $\alpha$, $\beta$. Rearranging,

Since $P$ and $Q$ are linearly independent, both sides of this equation must be the identity. Therefore,

Putting this together with the fact that the RHS is the identity,

we conclude $k \equiv k’\ (\textrm{mod } \ell)$. This gives us a family of $\ell$ many disjoint subgroups. The final subgroup to include is the one generated by $Q$. It is clear that this is also disjoint from the previously mentioned subgroups. Finally, there cannot be any more order $\ell$ subgroups, since we have listed all the possible cyclic subgroups of $\mathbb{Z}_\ell \times \mathbb{Z}_\ell$, and all groups of prime order are cyclic.

A supersingular $\ell$-isogeny graph is a graph whose nodes are $j$-invariants (i.e., elements of $\mathbb{F}_{p^2}$ which are in bijective correspondence with isomorphism classes of elliptic curves) and whose edges represent $\ell$-isogenies between them. Note this is an undirected graph because every $\ell$-isogeny has a dual $\ell$-isogeny going in the other direction. Also, by the above claim, every node has degree $\ell+1$. It turns out that this is an expander graph, which means random walks on it mix quickly. In other words, the diameter of an expander graph on $N$ elements is roughly $\log(N)$. SIDH exploits this property to make its security claims.

§ SIDH

The purpose of SIDH is to compute a shared secret by exchanging public shares. Same idea as Diffie Hellman.

§ Public Parameters

  • A prime $p = 2^{e_A}3^{e_B} - 1$. This way, $p+1$ is divisible by powers of 2 and 3. $e_A$ and $e_B$ are chosen so that $2^{e_A} \approx 3^{e_B}$.
  • A starting curve $E$ defined over $\mathbb{F}_{p^2}$
  • Two points $P_A,Q_A \in E$ such that $\langle P_A, Q_A \rangle \cong \mathbb{Z}_{2^{e_A}} \times \mathbb{Z}_{2^{e_A}}$.
  • Two points $P_B,Q_B \in E$ such that $\langle P_B, Q_B \rangle \cong \mathbb{Z}_{3^{e_B}} \times \mathbb{Z}_{3^{e_B}}$.

§ Protocol

Here’s the gist of the protocol: Alice takes a walk on a 2-isogeny graph and marks her stopping point. Bob takes a walk on a 3-isogeny graph and marks his stopping point. The constraint that $2^{e_A} \approx 3^{e_B}$ means that the number of possible stopping points that Alice can get to is roughly equal to the number of possible stopping points Bob can get to. They then share their stopping points with each other. Then both of them do the same walks as before, but starting at each other’s stopping point. The final endpoints of Alice’s and Bob’s walks are isomorphic (as elliptic curves, since points on the isogeny graph are curves), which means they have the same $j$-invariant.

Concretely, here’s the protocol sequence. Alice initiates:

Alice:

  1. Picks a random secret scalar $0 \leq k_A < 2^{e_A}$ and defines a secret generator $S_A = P_A + [k_A]Q_A$. Note that $S_A$ has order $2^{e_A}$ because $P_A$ and $Q_A$ are linearly independent. By the proof above, all the possible subgroups $\langle S_A\rangle$ are disjoint.
  2. Constructs a $2^{e_A}$-isogeny $\phi_A: E \to E/\langle S_A\rangle$. This is done iteratively by repeatedly constructing 2-isogenies with elements of $\langle S_A\rangle$ in the kernel. The way you do this is by getting a point $R_A = [2^{e_A-1}]S_A$ of order 2. Using Vélu’s formulas, you can construct a $\phi_0: E \to E/\langle R_A\rangle$. Now let $S’_A = \phi_0(S_A)$. Then $S’_A$ has order $2^{e_A-1}$. Let $R’_A = [2^{e_A-2}]S’_A$, … Once you’ve constructed $\phi_0$, …, $\phi_{e_A}$, let $\phi_A$ be the composition of all of these.
  3. Sends Bob $(\phi_A(E), \phi_A(P_B), \phi_A(Q_B))$, where $\phi_A(E)$ is the description of the output curve.

Bob:

  1. Picks a secret $0 < k_B ≤ 3^{e_B}$, lets $S_B = P_B + [k_B]Q_B$, and constructs a $3^{e_B}$-isogeny $\phi_B: E \to E/\langle S_B\rangle$ in the same way as above.
  2. Sends Alice $(\phi_B(E), \phi_B(P_A), \phi_B(Q_A))$

Alice:

  1. Uses the same method to construct $\psi_A: \phi_B(E) \to \phi_B(E)/\langle T_A\rangle$ where
  2. Computes the $j$-invariant of $\psi_A(\phi_B(E))$

Bob:

  1. Same idea as above: Construct $\psi_B: \phi_A(E) \to \phi_A(E)/\langle T_B\rangle$ where
  2. Computes the $j$-invariant of $\psi_B(\phi_A(E))$

End of Protocol

Note that, since $j$-variants of isomorphic curves are equal, and

the computed $j$-invariants are the same. Thus, it makes sense to have the $j$-invariant be the shared secret.

§ An Attack on Static Public Shares

This attack is due to Galbraith, Petit, Shani, and Ti. If Alice keeps reusing the same $k_A$, Bob can determine its value by by initiating $\lceil\log_2(k_A)\rceil$ many SIDH exchanges. Here’s the exploit:

Bob can figure out the bottom bit of $k_A$ by publishing $\phi_B(Q_A) + L_2$ instead of $\phi_B(Q_A)$, where $L_2$ is a point of order 2. If $k_A$ is odd, i.e., if $L_2$ is not killed by $k_A$, then the protocol does not produce agreement, because $T_A + L_2$ is not the image of $S_A$ in Bob’s curve $\phi_B(E)$. If $k_A$ is even, then $L_2$ is killed by $k_A$ and the protocol completes successfully. Thus, the bottom bit is leaked.

Say Bob finds it was even. Now Bob wants to know if $k_A \equiv 0\ (\textrm{mod } 4)$ or $2\ (\textrm{mod } 4)$. Then he sends $\phi_B(Q_A) + L_4$ where $L_4$ is a point of order 4, and uses the same logic. If Bob had found $k_A$ was odd, then he would send $\phi_B(P_A) - L_4$ instead of $\phi_B(P_A)$, and $\phi_B(Q_A) + L_4$ instead of $\phi_B(Q_A)$. So if $k_A$ is $1\ (\textrm{mod } 4)$, then

and the protocol succeeds. Otherwise,

and the protocol fails. Bob can continue like this to recover each successive bit of $k_A$.