Paper 2019/110

Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves

Suhri Kim, Kisoon Yoon, Young-Ho Park, and Seokhie Hong

Abstract

In this paper, we present an efficient method to compute arbitrary odd-degree isogenies on Edwards curves. By using the $w$-coordinate, we optimized the isogeny formula on Edwards curves by Moody and Shumow. We demonstrate that Edwards curves have an additional benefit when recovering the coefficient of the image curve during isogeny computation. For $\ell$-degree isogeny where $\ell=2s+1$, our isogeny formula on Edwards curves outperforms Montgomery curves when $s \geq 2$. To better represent the performance improvements when $w$-coordinate is used, we implement CSIDH using our isogeny formula. Our implementation is about 20\% faster than the previous implementation. The result of our work opens the door for the usage of Edwards curves in isogeny-based cryptography, especially for CSIDH which requires higher degree isogenies.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
IsogenyPost-quantum cryptographyMontgomery curvesEdwards curvesSIDHCSIDH
Contact author(s)
suhrikim @ gmail com
History
2019-12-07: last of 2 revisions
2019-02-05: received
See all versions
Short URL
https://ia.cr/2019/110
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/110,
      author = {Suhri Kim and Kisoon Yoon and Young-Ho Park and Seokhie Hong},
      title = {Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2019/110},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/110}},
      url = {https://eprint.iacr.org/2019/110}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.