Cryptology ePrint Archive: Report 2020/341

Faster computation of isogenies of large prime degree

Daniel J. Bernstein and Luca De Feo and Antonin Leroux and Benjamin Smith

Abstract: Let $\mathcal{E}/\mathbb{F}_q$ be an elliptic curve, and $P$ a point in $\mathcal{E}(\mathbb{F}_q)$ of prime order $\ell$. Vélu's formulae let us compute a quotient curve $\mathcal{E}' = \mathcal{E}/\langle{P}\rangle$ and rational maps defining a quotient isogeny $\phi: \mathcal{E} \to \mathcal{E}'$ in $\widetilde{O}(\ell)$ $\mathbb{F}_q$-operations, where the $\widetilde{O}$ is uniform in $q$. This article shows how to compute $\mathcal{E}'$, and $\phi(Q)$ for $Q$ in $\mathcal{E}(\mathbb{F}_q)$, using only $\widetilde{O}(\sqrt{\ell})$ $\mathbb{F}_q$-operations, where the $\widetilde{O}$ is again uniform in $q$. As an application, this article speeds up some computations used in the isogeny-based cryptosystems CSIDH and CSURF.

Category / Keywords: implementation / isogenies; elliptic curve cryptography; number theory; public key cryptography

Date: received 21 Mar 2020, last revised 23 Mar 2020

Contact author: authorcontact-velusqrt at box cr yp to

Available format(s): PDF | BibTeX Citation

Version: 20200323:183508 (All versions of this report)

Short URL: ia.cr/2020/341


[ Cryptology ePrint archive ]