There have been quite a few papers on isogeny crypto posted in the last few months. Here is a brief summary of some of them. I thank the members of my research group for fruitful discussions about these papers.
- Improved torsion point attacks on SIDH variants by Victoria de Quehen, Péter Kutas, Chris Leonardi, Chloe Martindale, Lorenz Panny, Christophe Petit and Katherine E. Stange.
This is a greatly revised and expanded version of an earlier paper by a subset of the authors. I am writing about the March 2021 version.
The paper builds on an idea of Petit (published at ASIACRYPT 2017) to exploit the fact that SIDH gives the image of torsion points. To be precise, suppose is an elliptic curve over with known endomorphism ring (for simplicity let’s take ). Let be an elliptic curve such that there is an isogeny of degree . Suppose we are also given where generate the subgroup of points of order on . The attacker wants to know . The general approach is to choose a suitable endomorphism on such that the isogeny from to itself has degree divisible by . One can then compute this isogeny and hence work back to determine . Two specific technical improvements in this paper over Petit’s work are the use of the dual isogeny and the Frobenius map.
The paper contains a number of results, but the main headline result is to give a polynomial-time attack on “over-stretched” SIDH, where (Petit’s original paper needed the stronger condition ). This is an important result, but it has no impact on standard implementations of SIDH (such as the SIKE submission to NIST), which have . However, the paper is a warning about non-standard variants of SIDH, and the paper discusses several such situations.
- The SQALE of CSIDH: Square-root Vélu Quantum-resistant isogeny Action with Low Exponents by Jorge Chávez-Saab, Jesús-Javier Chi-Domínguez, Samuel Jaques and Francisco Rodríguez-Henríquez.
The CSIDH approach to isogeny crypto is very appealing for crypto constructions and has attracted a lot of interest, however the problem is that it is attackable using Kuperberg’s quantum hidden-shift algorithm. Several works, in particular the two EUROCRYPT 2020 papers by Peikert and Bonnetain-Schrottenloher, have seriously challenged the proposed CSIDH parameters and suggested they do not meet the minimum required post-quantum security levels. So is CSIDH doomed?
The paper analyses a natural approach to rescue CSIDH, by using a much larger prime (and hence much larger class group) but by choosing private keys from a small subset of the class group, namely the ideals of the form with for small . (A similar proposal was made by myself and Luca De Feo in our SeaSign paper, in the context of lossy keys.)
The paper is mostly about Kuperberg’s quantum algorithm and its analysis. The paper gives arguments that suggest Kuperberg’s algorithm is not applicable to this variant of the problem. The analysis seems plausible, though I am not expert.
The big question is whether this saves CSIDH. For the proposed parameters, the prime is at least 4000 bits, so that protocol messages in key exchange are now at least 4000 bits. This is much worse than the originally suggested 512 bits. The timings are of the order of a few seconds for each operation, which again is much worse than desired. In conclusion, CSIDH may be saved, but it does lose some of its advantages over lattices (e.g., small keys and messages).
- One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols, by Péter Kutas, Simon-Philipp Merz, Christophe Petit and Charlotte Weitkämper (accepted to EUROCRYPT 2021).
This paper relates to both the papers already discussed. It constructs a group action in the SIDH setting, which opens the door to a Kuperberg-type sub-exponential quantum attack on SIDH. Again let be the elliptic curve over with . Let be an endomorphism of . Let be a certain multiplicative subgroup of . We need to act on some set. Let be a subgroup of of order . The action of group element is defined to be . So is acting on a set of elliptic curves (essentially a set of -invariants). Computing the group action is easy when is known, but the difficulty is to compute the group action on the challenge curve in the SIDH protocol (when is not known). To do this, the authors use torsion point information, as already discussed in item 1 above. So suppose we are given where has kernel of order and where generate the subgroup of order . The attack requires . Since SIDH with such parameters can already be broken in classical polynomial time by Petit (or the first paper discussed above), one would not use Kuperberg’s algorithm in this case. Hence this paper does not weaken SIDH. Instead the merit of the paper is to explain how group actions can be introduced in the SIDH setting, which contradicts the conventional wisdom that “SIDH is not based on group actions”.
— Steven Galbraith