International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Wouter Castryck

ORCID: 0000-0002-0191-5216

Publications

Year
Venue
Title
2023
EUROCRYPT
An efficient key recovery attack on SIDH
Wouter Castryck Thomas Decru
We present an efficient key recovery attack on the Supersingular Isogeny Diffie-Hellman protocol (SIDH). The attack is based on Kani's "reducibility criterion" for isogenies from products of elliptic curves and strongly relies on the torsion point images that Alice and Bob exchange during the protocol. If we assume knowledge of the endomorphism ring of the starting curve then the classical running time is polynomial in the input size (heuristically), apart from the factorization of a small number of integers that only depend on the system parameters. The attack is particularly fast and easy to implement if one of the parties uses 2-isogenies and the starting curve comes equipped with a non-scalar endomorphism of very small degree; this is the case for SIKE, the instantiation of SIDH that recently advanced to the fourth round of NIST's standardization effort for post-quantum cryptography. Our Magma implementation breaks SIKEp434, which aims at security level 1, in about ten minutes on a single core.
2023
CRYPTO
Weak instances of class group action based cryptography via self-pairings
In this paper we study non-trivial self-pairings with cyclic domains that are compatible with isogenies between elliptic curves oriented by an imaginary quadratic order $\mathcal{O}$. We prove that the order $m$ of such a self-pairing necessarily satisfies $m \mid \Delta_{\mathcal{O}}$ (and even $2m \mid \Delta_{\mathcal{O}} $ if $4 \mid \Delta_{\mathcal{O}}$ and $4m \mid \Delta_{\mathcal{O}}$ if $8 \mid \Delta_{\mathcal{O}}$) and is not a multiple of the field characteristic. Conversely, for each $m$ satisfying these necessary conditions, we construct a family of non-trivial cyclic self-pairings of order $m$ that are compatible with oriented isogenies, based on generalized Weil and Tate pairings. As an application, we identify weak instances of class group actions on elliptic curves assuming the degree of the secret isogeny is known. More in detail, we show that if $m^2 \mid \Delta_{\mathcal{O}}$ for some prime power $m$ then given two primitively $\mathcal{O}$-oriented elliptic curves $(E, \iota)$ and $(E',\iota') = [\mathfrak{a}](E,\iota)$ connected by an unknown invertible ideal $\mathfrak{a} \subseteq \mathcal{O}$, we can recover $\mathfrak{a}$ essentially at the cost of a discrete logarithm computation in a group of order $m^2$, assuming the norm of $\mathfrak{a}$ is given and is smaller than $m^2$. We give concrete instances, involving ordinary elliptic curves over finite fields, where this turns into a polynomial time attack. Finally, we show that these self-pairings simplify known results on the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves.
2023
ASIACRYPT
A polynomial time attack on instances of M-SIDH and FESTA
Wouter Castryck Frederik Vercauteren
The recent devastating attacks on SIDH rely on the fact that the protocol reveals the images $\varphi(P)$ and $\varphi(Q)$ of the secret isogeny $\varphi : E_0 \rightarrow E$ on a basis $\{P, Q\}$ of the $N$-torsion subgroup $E_0[N]$ where $N^2 > \deg(\varphi)$. To thwart this attack, two recent proposals, M-SIDH and FESTA, proceed by only revealing the images upto unknown scalars $\lambda_1, \lambda_2 \in \mathbb{Z}_N^\times$, i.e., only $\lambda_1 \varphi(P)$ and $\lambda_2 \varphi(Q)$ are revealed, where $\lambda_1 = \lambda_2$ for M-SIDH and $\lambda_1 = \lambda_2^{-1}$ for FESTA. Similar information is leaked in CSIDH since $\varphi$ maps the eigenspaces of Frobenius on $E_0$ to the corresponding eigenspaces on $E$. In this paper, we introduce a new polynomial time attack that generalizes the well known "lollipop" attack and analyze how it applies to M-SIDH, FESTA and CSIDH. We show that M-SIDH can be broken in polynomial time whenever $E_0$ or $E$ is $\mathbb{F}_p$-rational, even when the endomorphism rings of $E_0$ and $E$ are unknown. This can be generalized to the case where the starting (or end) curve is not $\mathbb{F}_p$-rational, but is connected to its Frobenius conjugate by an isogeny of small degree. For FESTA, where the curve $E_0$ is already $\mathbb{F}_p$-rational, we obtain a polynomial time attack under the added requirement that at least one of the basis points $P, Q$ spans an eigenspace of Frobenius, of an endomorphism of low degree, or of a composition of both. We note that the current implementation of FESTA does not choose such a basis. Since it is always possible to construct an endomorphism, typically of large degree, with either $P, Q$ an eigenvector, we conclude that FESTA with overstretched parameters is insecure. Although the information leaked in CSIDH is very similar to FESTA, we show that our attack does not reveal any new information about the secret isogeny, i.e., we only learn that it is $\mathbb{F}_p$-rational, which is a priori knowledge. Finally, we analyze if and how it would be possible to backdoor M-SIDH and FESTA by choosing system parameters that look inconspicuous, but in fact reduce to the special cases above via a secret isogeny chosen by the adversary.
2022
ASIACRYPT
Horizontal racewalking using radical isogenies 📺
We address three main open problems concerning the use of radical isogenies, as presented by Castryck, Decru and Vercauteren at Asiacrypt 2020, in the computation of long chains of isogenies of fixed, small degree between elliptic curves over finite fields. Firstly, we present an interpolation method for finding radical isogeny formulae in a given degree N, which by-passes the need for factoring division polynomials over large function fields. Using this method, we are able to push the range for which we have formulae at our disposal from N ≤ 13 to N ≤ 37. Secondly, using a combination of known techniques and ad-hoc manipulations, we derived optimized versions of these formulae for N ≤ 19, with some instances performing more than twice as fast as their counterparts from 2020. Thirdly, we solve the problem of understanding the correct choice of radical when walking along the surface between supersingular elliptic curves over Fp with p ≡ 7 mod 8; this is non-trivial for even N and was only settled for N = 4 by Onuki and Moriya at PKC 2022. We give a conjectural statement for all even N and prove it for N ≤ 14. The speed-ups obtained from these techniques are substantial: using 16-isogenies, the computation of long chains of 2-isogenies over 512-bit prime fields can be improved by a factor 3, and the previous implementation of CSIDH using radical isogenies can be sped up by about 12%.
2022
JOFC
Breaking the Decisional Diffie–Hellman Problem for Class Group Actions Using Genus Theory: Extended Version
In this paper, we use genus theory to analyze the hardness of the decisional Diffie–Hellman problem for ideal class groups of imaginary quadratic orders acting on sets of elliptic curves through isogenies (DDH–CGA). Such actions are used in the Couveignes–Rostovtsev–Stolbunov protocol and in CSIDH. Concretely, genus theory equips every imaginary quadratic order $$\mathcal {O}$$ O with a set of assigned characters $$\chi : {\text {cl}}(\mathcal {O}) \rightarrow \{ \pm 1\}$$ χ : cl ( O ) → { ± 1 } , and for each such character and every secret ideal class $$[\mathfrak {a}]$$ [ a ] connecting two public elliptic curves E and $$E' = [\mathfrak {a}] \star E$$ E ′ = [ a ] ⋆ E , we show how to compute $$\chi ([\mathfrak {a}])$$ χ ( [ a ] ) given only E and $$E'$$ E ′ , i.e., without knowledge of $$[\mathfrak {a}]$$ [ a ] . In practice, this breaks DDH–CGA as soon as the class number is even, which is true for a density 1 subset of all imaginary quadratic orders. For instance, our attack works very efficiently for all supersingular elliptic curves over $$\mathbb {F}_p$$ F p with $$p \equiv 1 \bmod 4$$ p ≡ 1 mod 4 . Our method relies on computing Tate pairings and walking down isogeny volcanoes. We also show that these ideas carry over, at least partly, to abelian varieties of arbitrary dimension. This is an extended version of the paper that was presented at Crypto 2020.
2020
EUROCRYPT
Rational isogenies from irrational endomorphisms 📺
In this paper, we introduce a polynomial-time algorithm to compute a connecting $\mathcal{O}$-ideal between two supersingular elliptic curves over $\mathbb{F}_p$ with common $\mathbb{F}_p$-endomorphism ring $\mathcal{O}$, given a description of their full endomorphism rings. This algorithm provides a reduction of the security of the CSIDH cryptosystem to the problem of computing endomorphism rings of supersingular elliptic curves. A similar reduction for SIDH appeared at Asiacrypt 2016, but relies on totally different techniques. Furthermore, we also show that any supersingular elliptic curve constructed using the complex-multiplication method can be located precisely in the supersingular isogeny graph by explicitly deriving a path to a known base curve. This result prohibits the use of such curves as a building block for a hash function into the supersingular isogeny graph.
2020
CRYPTO
Breaking the decisional Diffie-Hellman problem for class group actions using genus theory
In this paper, we use genus theory to analyze the hardness of the decisional Diffie--Hellman problem (DDH) for ideal class groups of imaginary quadratic orders, acting on sets of elliptic curves through isogenies; such actions are used in the Couveignes--Rostovtsev--Stolbunov protocol and in CSIDH. Concretely, genus theory equips every imaginary quadratic order $\mathcal{O}$ with a set of assigned characters $\chi : \text{cl}(\mathcal{O}) \to \{ \pm 1 \}$, and for each such character and every secret ideal class $[\mathfrak{a}]$ connecting two public elliptic curves $E$ and $E' = [\mathfrak{a}] \star E$, we show how to compute $\chi([\mathfrak{a}])$ given only $E$ and $E'$, i.e., without knowledge of $[\mathfrak{a}]$. In practice, this breaks DDH as soon as the class number is even, which is true for a density $1$ subset of all imaginary quadratic orders. For instance, our attack works very efficiently for all supersingular elliptic curves over $\mathbb{F}_p$ with $p \equiv 1 \bmod 4$. Our method relies on computing Tate pairings and walking down isogeny volcanoes.
2020
ASIACRYPT
Radical Isogenies 📺
This paper introduces a new approach to computing isogenies called ``radical isogenies'' and a corresponding method to compute chains of $N$-isogenies that is very efficient for small $N$. The method is fully deterministic and completely avoids generating $N$-torsion points. It is based on explicit formulae for the coordinates of an $N$-torsion point $P'$ on the codomain of a cyclic $N$-isogeny $\varphi : E \to E'$, such that composing $\varphi$ with $E' \to E' / \langle P' \rangle$ yields a cyclic $N^2$-isogeny. These formulae are simple algebraic expressions in the coefficients of $E$, the coordinates of a generator $P$ of $\ker \varphi$, and an $N$th root $\sqrtN{\rho}$, where the radicand $\rho$ itself is given by an easily computable algebraic expression in the coefficients of $E$ and the coordinates of $P$. The formulae can be iterated and are particularly useful when computing chains of $N$-isogenies over a finite field $\F_q$ with $\gcd(q-1, N) = 1$, where taking an $N$th root is a simple exponentiation. Compared to the state-of-the-art, our method results in an order of magnitude speed-up for $N \leq 13$; for larger $N$, the advantage disappears due to the increasing complexity of the formulae. When applied to CSIDH, we obtain a speed-up of about $19 \%$ over the implementation by Bernstein, De Feo, Leroux and Smith for the CSURF-512 parameters.
2018
EUROCRYPT
2018
ASIACRYPT
CSIDH: An Efficient Post-Quantum Commutative Group Action
We propose an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes–Rostovtsev–Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field $$\mathbb F_p$$, rather than to ordinary elliptic curves. The Diffie–Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at a conjectured AES-128 security level, matching NIST’s post-quantum security category I.
2017
CHES
Faster Homomorphic Function Evaluation Using Non-integral Base Encoding
In this paper we present an encoding method for real numbers tailored for homomorphic function evaluation. The choice of the degree of the polynomial modulus used in all popular somewhat homomorphic encryption schemes is dominated by security considerations, while with the current encoding techniques the correctness requirement allows for much smaller values. We introduce a generic encoding method using expansions with respect to a non-integral base, which exploits this large degree at the benefit of reducing the growth of the coefficients when performing homomorphic operations. This allows one to choose a smaller plaintext coefficient modulus which results in a significant reduction of the running time. We illustrate our approach by applying this encoding in the setting of homomorphic electricity load forecasting for the smart grid which results in a speed-up by a factor 13 compared to previous work, where encoding was done using balanced ternary expansions.
2016
EUROCRYPT

Program Committees

Crypto 2024
Asiacrypt 2023
Eurocrypt 2021
Asiacrypt 2021