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.