Attacks on SIDH/SIKE

You may feel like you are having trouble keeping up with the news on SIDH/SIKE. So am I! I hope this blog post doesn’t instantly become obsolete due to new advances.

To recall, there are now three preprints giving attacks on SIDH:

The first two are parallel independent works that apply a theorem due to Kani to break SIDH in some special cases. One of the special cases was the NIST submission SIKE, meaning that SIKE was able to be broken easily on a laptop. The most recent paper by Damien Robert is influenced by the previous two works, and extends the attack to work in a much more general case. This now breaks SIDH completely in all cases.

I will summarise Damien Robert’s work below, but first a few other updates.

Now to sketch the idea by Damien Robert. For consistency with my previous blog post I use some of the Castryck-Decru notation.

Recall that in SIDH we have a base curve $E_0$ and isogenies $\phi_A : E_0 \to E_A$ of degree $2^a$ and $\phi_B : E_0 \to E_B$ of degree $3^b$, together with some auxiliary points. Assume $2^a > 3^b$.

The most natural way to break SIDH is to compute $\phi_B$ on points of order $3^b$, from which one can then determine $\ker( \phi_B )$ and SIDH is broken. (This is the goal of the torsion-point attacks by Petit et al, it is also the idea for the improvement to the original attack by Rémy Oudompheng and others that I mentioned above.) This is what Damien Robert’s attack does too.

Let $c = 2^a - 3^b$. Then we can write $c$ as a sum of four squares. In this post I will take the simpler case when all prime factors of the square-free part of $c$ are congruent to 1 modulo 4, in which case we can write $c = a_1^2 + a_2^2$ where $a_1, a_2$ are integers. [Note added 15/8/2022 thanks to Daniel Bernstein: To do this we need to factor $c$, which is polynomial-time for quantum computers or subexponential-time classically. The 4 squares case is polynomial-time classically.] Let $M = (\begin{matrix} a_1 & a_2 \\ -a_2 & a_1 \end{matrix})$. Then $M^t M = (a_1^2 + a_2^2) I_2 = c I_2$ where $I_2$ is the $2 \times 2$ identity matrix. Hence $M$ defines an isogeny $\alpha : E^2 \to E^2$ for any elliptic curve $E$. Specifically $\alpha(X,Y) = ( [a_1]X + [a_2]Y, [-a_2]X + [a_1] Y )$. The dual isogeny $\hat{\alpha}$ corresponds to the transpose $M^t$. We have $\hat{\alpha}\alpha = [c]$ as a map from $E^2$ to itself. We will apply this map to both $E_0$ and $E_B$.

The secret isogeny is $\phi_B : E_0 \to E_B$ and we can extend this to a map from $E_0^2 \to E_B^2$ as $\phi_B( X, Y ) = ( \phi_B( X ), \phi_B( Y ) )$. Note that $\phi_B$ commutes with $\alpha$, since $\phi_B$ is a group homomorphism.

We can define an isogeny $F$ on the 4-dimensional Abelian variety ${\bf A} = E_0^2 \times E_B^2$, by $F = (\begin{matrix} \alpha & \hat{\phi}_B \\ -\phi_B & \hat{\alpha} \end{matrix})$. The dual isogeny is $\hat{F} = (\begin{matrix} \hat{\alpha} & -\hat{\phi}_B \\ \phi_B & \alpha \end{matrix})$ and one can check $\hat{F} F = (c + 3^b) I_4 = 2^a I_4$ where $I_4$ is the identity map (or identity matrix if you want to view these as matrices).

Now, from the auxiliary points in SIDH we know how $\phi_B$ acts on $E_0[ 2^a ]$. Since $\hat{\phi}_B \phi_B = [ 3^b]$ we can also compute how $\hat{\phi}_B$ acts on $E_B[ 2^a ]$. Hence we can compute how $F$ acts on ${\bf A}[2^a]$. Since $\ker(F) \subseteq {\bf A}[2^a]$ it means we compute $\ker(F)$.

Now, knowing $\ker(F)$ we can use fancy methods to compute isogenies on high-dimensional Abelian varieties (and Damien Robert is a leading expert on this topic) and hence compute $F$ on any point. So, we compute $F$ on a basis for ${\bf A}[ 3^b]$ and hence compute $\phi_B$ on $E_0[ 3^b]$ and break SIDH.

The full attack works with an 8-dimensional Abelian variety ${\bf A} = E_0^4 \times E_B^4$. I am not aware of any implementation of the attack as yet, but I look forward to seeing one. The attack can also be set up to compute the isogeny $\phi_A$ instead, simply by brute-forcing an extra small 3-power isogeny so that $3^b > 2^a$.

As with my earlier blog post, I want to emphasise that this attack is only possible due to decades of research on computing isogenies of general Abelian varieties. This work was not primarily motivated by cryptographic applications but by the drive to generalization in pure mathematics.

— Steven Galbraith

This entry was posted in Uncategorized. Bookmark the permalink.