Paper 2020/341

Faster computation of isogenies of large prime degree

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

Abstract

Let E/Fq be an elliptic curve, and P a point in E(Fq) of prime order . Vélu's formulae let us compute a quotient curve E=E/P and rational maps defining a quotient isogeny ϕ:EE in O~() Fq-operations, where the O~ is uniform in q. This article shows how to compute E, and ϕ(Q) for Q in E(Fq), using only O~() Fq-operations, where the O~ is again uniform in q. As an application, this article speeds up some computations used in the isogeny-based cryptosystems CSIDH and CSURF.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
isogenieselliptic curve cryptographynumber theorypublic key cryptography
Contact author(s)
authorcontact-velusqrt @ box cr yp to
History
2020-03-23: last of 2 revisions
2020-03-22: received
See all versions
Short URL
https://ia.cr/2020/341
License
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2020/341}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.