Paper 2019/843

How to Construct CSIDH on Edwards Curves

Tomoki Moriya, Hiroshi Onuki, and Tsuyoshi Takagi

Abstract

CSIDH is an isogeny-based 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 constant-time 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)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Isogeny-based cryptographyMontgomery curvesEdwards curvesCSIDHPost-quantum cryptography
Contact author(s)
tomoki_moriya @ mist i u-tokyo ac jp
History
2021-01-23: last of 2 revisions
2019-07-19: received
See all versions
Short URL
https://ia.cr/2019/843
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.