How to construct CSIDH on Edwards curves

Tomoki Moriya; Hiroshi Onuki; Tsuyoshi Takagi

doi:10.1016/j.ffa.2023.102310

How to construct CSIDH on Edwards curves

Tomoki Moriya^*, Hiroshi Onuki, Tsuyoshi Takagi

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

3 Downloads (Pure)

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_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	https://doi.org/10.1016/j.ffa.2023.102310
Publication status	Published - Dec 2023

Bibliographical note

Acknowledgements
This research was conducted under a contract of “Research and development on new generation cryptography for secure wireless communication services” among “Research and Development for Expansion of Radio Wave Resources (JPJ000254)”, which was supported by the Ministry of Internal Affairs and Communications, Japan.

Keywords

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

Access to Document

10.1016/j.ffa.2023.102310Licence: Creative Commons: Attribution (CC BY)

MoriyaT2023FiniteFinal published version, 881 KBLicence: Creative Commons: Attribution (CC BY)

Cite this

@article{4dfb57bb3d4e4c198a380e2408570899,

title = "How to construct CSIDH on Edwards curves",

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 Fp -isomorphism classes of Montgomery curves. The original CSIDH algorithm requires a calculation over Fp 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 Fp4 . Therefore, calculating the class group action on Edwards curves with w-coordinates over only Fp 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 Fp. 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. (√{\'e}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, √{\'e}lu's formulas, and CTIDH [3] (faster constant-time CSIDH) on Edwards curves. Each result shows the efficiency of algorithms on Edwards curves.",

keywords = "Isogeny-based cryptography, Montgomery curves, Edwards curves, CSIDH, Post-quantum cryptography",

author = "Tomoki Moriya and Hiroshi Onuki and Tsuyoshi Takagi",

note = "Acknowledgements This research was conducted under a contract of “Research and development on new generation cryptography for secure wireless communication services” among “Research and Development for Expansion of Radio Wave Resources (JPJ000254)”, which was supported by the Ministry of Internal Affairs and Communications, Japan.",

year = "2023",

month = dec,

doi = "10.1016/j.ffa.2023.102310",

language = "English",

volume = "92",

journal = "Finite Fields and Their Applications",

issn = "1071-5797",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - How to construct CSIDH on Edwards curves

AU - Moriya, Tomoki

AU - Onuki, Hiroshi

AU - Takagi, Tsuyoshi

N1 - Acknowledgements This research was conducted under a contract of “Research and development on new generation cryptography for secure wireless communication services” among “Research and Development for Expansion of Radio Wave Resources (JPJ000254)”, which was supported by the Ministry of Internal Affairs and Communications, Japan.

PY - 2023/12

Y1 - 2023/12

N2 - 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 Fp -isomorphism classes of Montgomery curves. The original CSIDH algorithm requires a calculation over Fp 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 Fp4 . Therefore, calculating the class group action on Edwards curves with w-coordinates over only Fp 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 Fp. 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.

AB - 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 Fp -isomorphism classes of Montgomery curves. The original CSIDH algorithm requires a calculation over Fp 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 Fp4 . Therefore, calculating the class group action on Edwards curves with w-coordinates over only Fp 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 Fp. 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.

KW - Isogeny-based cryptography

KW - Montgomery curves

KW - Edwards curves

KW - CSIDH

KW - Post-quantum cryptography

U2 - 10.1016/j.ffa.2023.102310

DO - 10.1016/j.ffa.2023.102310

M3 - Article

SN - 1071-5797

VL - 92

JO - Finite Fields and Their Applications

JF - Finite Fields and Their Applications

M1 - 102310

ER -

How to construct CSIDH on Edwards curves

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this