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:

- An efficient key recovery attack on SIDH (preliminary version) by Wouter Castryck and Thomas Decru. Posted July 30.
- An attack on SIDH with arbitrary starting curve by Luciano Maino and Chloe Martindale. Posted August 8.
- Breaking SIDH in polynomial time by Damien Robert. Posted August 10.

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.

- I put up a note Kani for beginners to explain in an elementary way that Kani’s “isogeny diamonds” are the same as SIDH squares, and to give some intuition for what Kani’s theorem says.
- Rémy Oudompheng posted A note on implementing direct isogeny determination in the Castryck-Decru SIKE attack and Benjamin Wesolowski posted Understanding and improving the Castryck-Decru attack on SIDH . Both notes explain an improvement to the attack. The main idea seems also to have been had by Christophe Petit and Maino-Martindale.
- The sage code has been updated with these techniques, allowing it to break some instances in under a minute.
- Tomoki Moriya has posted https://eprint.iacr.org/2022/1019, which gives a possible fix for SIDH. Much less efficient and practical though.

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 and isogenies of degree and of degree , together with some auxiliary points. Assume .

The most natural way to break SIDH is to compute on points of order , from which one can then determine 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 . Then we can write 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 are congruent to 1 modulo 4, in which case we can write where are integers. [Note added 15/8/2022 thanks to Daniel Bernstein: To do this we need to factor , which is polynomial-time for quantum computers or subexponential-time classically. The 4 squares case is polynomial-time classically.] Let . Then where is the identity matrix. Hence defines an isogeny for any elliptic curve . Specifically . The dual isogeny corresponds to the transpose . We have as a map from to itself. We will apply this map to both and .

The secret isogeny is and we can extend this to a map from as . Note that commutes with , since is a group homomorphism.

We can define an isogeny on the 4-dimensional Abelian variety , by . The dual isogeny is and one can check where 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 acts on . Since we can also compute how acts on . Hence we can compute how acts on . Since it means we compute .

Now, knowing 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 on any point. So, we compute on a basis for and hence compute on and break SIDH.

The full attack works with an 8-dimensional Abelian variety . 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 instead, simply by brute-forcing an extra small 3-power isogeny so that .

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