## Abstract

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

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

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 Õ(√ℓ) 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.

_{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_{p4}. 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 Õ(√ℓ) 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.

Original language | English |
---|---|

Article number | 102310 |

Number of pages | 45 |

Journal | Finite Fields and Their Applications |

Volume | 92 |

Early online date | 5 Oct 2023 |

DOIs | |

Publication status | Published - Dec 2023 |

## Keywords

- Isogeny-based cryptography
- Montgomery curves
- Edwards curves
- CSIDH
- Post-quantum cryptography