How to construct CSIDH on Edwards curves.

CSIDH is an isogeny-based key exchange protocol proposed by Castryck 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, calculating the class group action on Edwards curves with w -coordinates over only F p is not a trivial task. In this paper, we prove some theorems about the properties of Edwards curves. We construct the new CSIDH algorithm using these theorems on Edwards curves with w -coordinates over 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 extended version of [29]. We added the construction of a technique similar to Elligator on Edwards curves. This technique contributes to the efficiency of the constant-time CSIDH algorithm. We also added the construction of new formulas to compute isogenies in O ˜ (ℓ) time on Edwards curves. It is based on formulas on Montgomery curves proposed by Bernstein et al. ( élu's formulas). In our analysis, these formulas on Edwards curves are a little bit faster than those on Montgomery curves. We finally implemented CSIDH, élu's formulas, and CTIDH [3] (faster constant-time CSIDH) on Edwards curves. Each result shows the efficiency of algorithms on Edwards curves. [ABSTRACT FROM AUTHOR]