Paper 2020/341
Faster computation of isogenies of large prime degree
Daniel J. Bernstein, Luca De Feo, 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 isogenybased cryptosystems CSIDH and CSURF.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Preprint. MINOR revision.
 Keywords
 isogenieselliptic curve cryptographynumber theorypublic key cryptography
 Contact author(s)
 authorcontactvelusqrt @ box cr yp to
 History
 20200323: last of 2 revisions
 20200322: received
 See all versions
 Short URL
 https://ia.cr/2020/341
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/341, author = {Daniel J. Bernstein and Luca De Feo and Antonin Leroux and Benjamin Smith}, title = {Faster computation of isogenies of large prime degree}, howpublished = {Cryptology ePrint Archive, Paper 2020/341}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/341}}, url = {https://eprint.iacr.org/2020/341} }