Paper 2020/1108
Radical isogenies
Wouter Castryck, Thomas Decru, and Frederik Vercauteren
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 $\sqrt[N]{\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 $\mathbb{F}_q$ with $\gcd(q1, N) = 1$, where taking an $N$th root is a simple exponentiation. Compared to the stateoftheart, our method results in an order of magnitude speedup 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 speedup of about $19 \%$ over the implementation by Bernstein, De Feo, Leroux and Smith for the CSURF512 parameters.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published by the IACR in ASIACRYPT 2020
 Keywords
 postquantum cryptographyisogeniesTate pairingCSIDH
 Contact author(s)

wouter castryck @ kuleuven be
thomas decru @ kuleuven be
frederik vercauteren @ kuleuven be  History
 20210603: last of 2 revisions
 20200915: received
 See all versions
 Short URL
 https://ia.cr/2020/1108
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1108, author = {Wouter Castryck and Thomas Decru and Frederik Vercauteren}, title = {Radical isogenies}, howpublished = {Cryptology ePrint Archive, Paper 2020/1108}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/1108}}, url = {https://eprint.iacr.org/2020/1108} }