CryptoDB
Radical Isogenies
NOTE: imports for ToSC and TCHES are no longer functioning.
Authors: | |
---|---|
Download: | |
Presentation: | Slides |
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. |
Video from ASIACRYPT 2020
BibTeX
@article{asiacrypt-2020-30700, title={Radical Isogenies}, booktitle={Advances in Cryptology - ASIACRYPT 2020}, publisher={Springer}, doi={10.1007/978-3-030-64834-3_17}, author={Wouter Castryck and Thomas Decru and Frederik Vercauteren}, year=2020 }