Some recent papers in isogeny crypto

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.

1. 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 $E_0$ is an elliptic curve over $\mathbb{F}_p$ with known endomorphism ring (for simplicity let’s take $j(E_0) = 1728$). Let $E_1$ be an elliptic curve such that there is an isogeny $\phi : E_0 \to E_1$ of degree $A$. Suppose we are also given $\phi(P), \phi(Q)$ where $P, Q$ generate the subgroup of points of order $B$ on $E_0$. The attacker wants to know $\phi$. The general approach is to choose a suitable endomorphism $\theta$ on $E_0$ such that the isogeny $\phi \circ \theta \circ \hat{\phi} + d$ from $E_1$ to itself has degree divisible by $B$. One can then compute this isogeny and hence work back to determine $\phi$. 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 $B > pA$ (Petit’s original paper needed the stronger condition $B > A^4$). This is an important result, but it has no impact on standard implementations of SIDH (such as the SIKE submission to NIST), which have $A \approx B \approx \sqrt{p}$. However, the paper is a warning about non-standard variants of SIDH, and the paper discusses several such situations.

1. 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 $\prod_i \ell_i^{e_i}$ with $|e_i| \le m$ for small $m$. (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 $p$ 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).

1. 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 $E_0 : y^2 = x^3 + x$ be the elliptic curve over $\mathbb{F}_p$ with $j(E_0) = 1728$. Let $\iota(x,y) = (-x, iy)$ be an endomorphism of $E_0$. Let $G$ be a certain multiplicative subgroup of $\mathbb{Z}[\iota]$. We need $G$ to act on some set. Let $L$ be a subgroup of $E_0$ of order $A$. The action of group element $\theta=a+b\iota \in G$ is defined to be $E_0 / \theta(L)$. So $G$ is acting on a set of elliptic curves (essentially a set of $j$-invariants). Computing the group action is easy when $L$ is known, but the difficulty is to compute the group action on the challenge curve $E_1 = E/K$ in the SIDH protocol (when $K$ is not known). To do this, the authors use torsion point information, as already discussed in item 1 above. So suppose we are given $E_0, E_1, \phi(P), \phi(Q)$ where $\phi : E_0 \to E_1$ has kernel $K$ of order $A$ and where $P, Q$ generate the subgroup of order $B$. The attack requires $B > p A^4$. 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

This entry was posted in Uncategorized. Bookmark the permalink.