[Resource Topic] 2019/843: How to Construct CSIDH on Edwards Curves

Welcome to the resource topic for 2019/843

How to Construct CSIDH on Edwards Curves

Authors: Tomoki Moriya, Hiroshi Onuki, Tsuyoshi Takagi


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.

ePrint: https://eprint.iacr.org/2019/843

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .