Paper 2019/843
How to Construct CSIDH on Edwards Curves
Tomoki Moriya, Hiroshi Onuki, and Tsuyoshi Takagi
Abstract
CSIDH is an isogenybased key exchange protocol proposed by Castryck \textit{et al.} in 2018. It is based on the ideal class group action on $\mathbb{F}_p$isomorphism classes of Montgomery curves. The original CSIDH algorithm requires a calculation over $\mathbb{F}_p$ by representing points as $x$coordinate over Montgomery curves. There is a special coordinate on Edwards curves (the $w$coordinate) to calculate group operations and isogenies. If we try to calculate the class group action on Edwards curves by using the $w$coordinate in a similar way on Montgomery curves, we have to consider points defined over $\mathbb{F}_{p^4}$. Therefore, it is not a trivial task to calculate the class group action on Edwards curves with $w$coordinates over only $\mathbb{F}_p$. In this paper, we prove some theorems about the properties of Edwards curves. By these theorems, we construct the new CSIDH algorithm on Edwards curves with $w$coordinates over $\mathbb{F}_p$. This algorithm is as fast as (or a little bit faster than) the algorithm proposed by Meyer and Reith. This paper is an extend version of [25]. We added the construction of a technique similar to Elligator on Edwards curves. This technique contributes the efficiency of the constanttime CSIDH algorithm. We also added the construction of new formulas to compute isogenies in $\tilde{O}(\sqrt{\ell})$ times on Edwards curves. It is based on formulas on Montgomery curves proposed by Bernstein \textit{et al.} ($\sqrt{\vphantom{2}}$élu's formulas). In our analysis, these formulas on Edwards curves is a little bit faster than those on Montgomery curves.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. Minor revision.
 Keywords
 Isogenybased cryptographyMontgomery curvesEdwards curvesCSIDHPostquantum cryptography
 Contact author(s)
 tomoki_moriya @ mist i utokyo ac jp
 History
 20210123: last of 2 revisions
 20190719: received
 See all versions
 Short URL
 https://ia.cr/2019/843
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/843, author = {Tomoki Moriya and Hiroshi Onuki and Tsuyoshi Takagi}, title = {How to Construct CSIDH on Edwards Curves}, howpublished = {Cryptology ePrint Archive, Paper 2019/843}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/843}}, url = {https://eprint.iacr.org/2019/843} }