15
$\begingroup$

Wouter Castryck and Thomas Decru recently broke SIDH.

From the abstract:

We present an efficient key recovery attack on the Supersingular Isogeny Diffie-Hellman protocol (SIDH), based on a "glue-and-split" theorem due to Kani.

The referenced Kani work is:

Ernst Kani, The number of curves of genus two with elliptic differentials, Journal für die reine und angewandte Mathematik 485, pp. 93–121 (1997), available at https://www.mast.queensu.ca/~kani/papers/numgenl.pdf

I have two questions:

  1. Does it mean the end of isogeny-based cryptography?

  2. Why so late? 1997 to 2022?

$\endgroup$
2
  • 1
    $\begingroup$ it is very common for mathematical results to find applications much much later. I am not an expert on the technical details, so I will wait for more commentary. $\endgroup$
    – kodlu
    Jul 31, 2022 at 19:15
  • $\begingroup$ For getting an overview about which isogeny-based systems exist and their differences, I'd recommend to watch Luca De Feo's invited talk from RealWorldCrypto2021. $\endgroup$
    – j.p.
    Aug 1, 2022 at 6:59

1 Answer 1

16
$\begingroup$
  1. It's early days to assess the full implications yet, but there is an excellent blog by Stephen Galbraith that seems to indicate that this does not currently apply to all isogeny-based schemes (in particular CSIDH and SQIsign). He writes:

Does it break CSIDH or other isogeny cryptosystems?

No. The attack very specifically relies on two things: (1) that the degree of the secret isogeny is known; (2) the attacker is provided with the auxiliary points. Hence the attack does not seem to break CSIDH or SQISign.

This does not rule out other attacks on these systems (including Chris Peikert's quantum attack in He Gives C-Sieves on the CSIDH). It seems pretty clear than SIKE is dead in the water though (a random "level 5" parameter set has been broken in under one day on a single core).

  1. The topic of isogeny-based cryptography is still relatively arcane with not many experts. The mathematical breadth of literature on isogenies is much broader than this community. There's also considerable use of results slightly outside of elliptic curve isogenies to more general isogenies. Again, Galbraith writes:

Why was it only discovered now?

The theoretical foundations of the attack are described in a paper by Kani from 1997 (and also some useful tools are in a paper by Howe, Leprévost and Poonen from 2000). So in some sense the attack could have been noticed at any time. But a key point is that this is not an attack one is going to discover by thinking only about isogenies between elliptic curves. The attack deeply exploits Richelot isogenies and products of elliptic curves and I doubt the attack can be expressed meaningfull without that language. This is the power of generalisation and extension. So what was necessary to find the attack was to have a community of scholars studying “esoteric” subjects like extending isogeny crypto to abelian surfaces.

$\endgroup$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.