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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2020
Keywords
post-quantum cryptographyisogeniesTate pairingCSIDH
Contact author(s)
wouter castryck @ kuleuven be
thomas decru @ kuleuven be
frederik vercauteren @ kuleuven be
History
2021-06-03: last of 2 revisions
2020-09-15: received
See all versions
Short URL
https://ia.cr/2020/1108
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.