Cryptology ePrint Archive: Report 2020/1108

Radical isogenies

Wouter Castryck and 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.

Category / Keywords: public-key cryptography / post-quantum cryptography, isogenies, Tate pairing, CSIDH

Original Publication (in the same form): IACR-ASIACRYPT-2020

Date: received 14 Sep 2020

Contact author: wouter castryck at kuleuven be, thomas decru@kuleuven be, frederik vercauteren@kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20200915:113000 (All versions of this report)

Short URL: ia.cr/2020/1108


[ Cryptology ePrint archive ]