Paper 2019/843
How to Construct CSIDH on Edwards Curves
Tomoki Moriya and Hiroshi Onuki and Tsuyoshi Takagi
Abstract
CSIDH is an isogeny-based key exchange protocol proposed by Castryck, Lange, Martindale, Panny, and Renes in 2018. CSIDH is based on the ideal class group action on $\mathbb{F}_p$-isomorphism classes of Montgomery curves. In order to calculate the class group action, we need to take points defined over $\mathbb{F}_{p^2}$. The original CSIDH algorithm requires a calculation over $\mathbb{F}_p$ by representing points as $x$-coordinate over Montgomery curves. Meyer and Reith proposed a faster CSIDH algorithm in 2018 which calculates isogenies on Edwards curves by using a birational map between a Montgomery curve and an Edwards curve. 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 a number of theorems on the properties of Edwards curves. By using these theorems, we extend the CSIDH algorithm to that 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.
Metadata
- Available format(s)
- 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
-
CC BY