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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s