## CryptoDB

### Wouter Castryck

#### Publications

**Year**

**Venue**

**Title**

2022

ASIACRYPT

Horizontal racewalking using radical isogenies
📺
Abstract

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%.

2020

EUROCRYPT

Rational isogenies from irrational endomorphisms
📺
Abstract

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
★
Abstract

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
📺
Abstract

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

ASIACRYPT

CSIDH: An Efficient Post-Quantum Commutative Group Action
Abstract

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
Abstract

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.

#### Program Committees

- Eurocrypt 2021
- Asiacrypt 2021

#### Coauthors

- Charlotte Bonte (1)
- Carl Bootland (1)
- Joppe W. Bos (1)
- Thomas Decru (2)
- Marc Houben (1)
- Ilia Iliashenko (3)
- Tanja Lange (1)
- Chloe Martindale (1)
- Lorenz Panny (2)
- Joost Renes (1)
- Jana Sotáková (1)
- Frederik Vercauteren (7)