How to Construct CSIDH on Edwards Curves

Tomoki Moriya; Hiroshi Onuki; Tsuyoshi Takagi

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 $F_{p}$ -isomorphism classes of Montgomery curves. The original CSIDH algorithm requires a calculation over $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 $F_{p^{4}}$ . Therefore, it is not a trivial task to calculate the class group action on Edwards curves with $w$ -coordinates over only $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 -coordinates over . 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 times on Edwards curves. It is based on formulas on Montgomery curves proposed by Bernstein \textit{et al.} (é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 cryptography Montgomery curves Edwards curves CSIDH Post-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: 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},
      url = {https://eprint.iacr.org/2019/843}
}