How to Construct CSIDH on Edwards Curves

Tomoki Moriya; Hiroshi Onuki; Tsuyoshi Takagi

doi:10.1007/978-3-030-40186-3_22

How to Construct CSIDH on Edwards Curves

Tomoki Moriya^*, Hiroshi Onuki, Tsuyoshi Takagi

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 𝔽_p-isomorphism classes of Montgomery curves. In order to calculate the class group action, we need to take points defined over 𝔽_p². The original CSIDH algorithm requires a calculation over 𝔽_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 𝔽_p⁴. Therefore, it is not a trivial task to calculate the class group action on Edwards curves with w-coordinates over only 𝔽_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 𝔽_p. This algorithm is as fast as (or a little bit faster than) the algorithm proposed by Meyer and Reith.

Original language	English
Title of host publication	Topics in Cryptology – CT-RSA 2020
Subtitle of host publication	The Cryptographers’ Track at the RSA Conference 2020, San Francisco, CA, USA, February 24–28, 2020, Proceedings
Editors	Stanislaw Jarecki
Publisher	Springer
Pages	512–537
Number of pages	26
Edition	1
ISBN (Electronic)	9783030401863
ISBN (Print)	9783030401856
DOIs	https://doi.org/10.1007/978-3-030-40186-3_22
Publication status	Published - 30 Jan 2020

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12006
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

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

Access to Document

10.1007/978-3-030-40186-3_22

Cite this

Moriya, T., Onuki, H., & Takagi, T. (2020). How to Construct CSIDH on Edwards Curves. In S. Jarecki (Ed.), Topics in Cryptology – CT-RSA 2020: The Cryptographers’ Track at the RSA Conference 2020, San Francisco, CA, USA, February 24–28, 2020, Proceedings (1 ed., pp. 512–537). (Lecture Notes in Computer Science; Vol. 12006). Springer. https://doi.org/10.1007/978-3-030-40186-3_22

@inproceedings{64bdb40d5a3d437583b584d9869a2c3d,

title = "How to Construct CSIDH on Edwards Curves",

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 𝔽p-isomorphism classes of Montgomery curves. In order to calculate the class group action, we need to take points defined over 𝔽p2. The original CSIDH algorithm requires a calculation over 𝔽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 𝔽p4. Therefore, it is not a trivial task to calculate the class group action on Edwards curves with w-coordinates over only 𝔽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 𝔽p. This algorithm is as fast as (or a little bit faster than) the algorithm proposed by Meyer and Reith.",

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

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

year = "2020",

month = jan,

day = "30",

doi = "10.1007/978-3-030-40186-3_22",

language = "English",

isbn = "9783030401856",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "512–537",

editor = "Stanislaw Jarecki",

booktitle = "Topics in Cryptology – CT-RSA 2020",

edition = "1",

}

Moriya, T, Onuki, H & Takagi, T 2020, How to Construct CSIDH on Edwards Curves. in S Jarecki (ed.), Topics in Cryptology – CT-RSA 2020: The Cryptographers’ Track at the RSA Conference 2020, San Francisco, CA, USA, February 24–28, 2020, Proceedings. 1 edn, Lecture Notes in Computer Science, vol. 12006, Springer, pp. 512–537. https://doi.org/10.1007/978-3-030-40186-3_22

How to Construct CSIDH on Edwards Curves. / Moriya, Tomoki; Onuki, Hiroshi; Takagi, Tsuyoshi.
Topics in Cryptology – CT-RSA 2020: The Cryptographers’ Track at the RSA Conference 2020, San Francisco, CA, USA, February 24–28, 2020, Proceedings. ed. / Stanislaw Jarecki. 1. ed. Springer, 2020. p. 512–537 (Lecture Notes in Computer Science; Vol. 12006).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - How to Construct CSIDH on Edwards Curves

AU - Moriya, Tomoki

AU - Onuki, Hiroshi

AU - Takagi, Tsuyoshi

PY - 2020/1/30

Y1 - 2020/1/30

N2 - 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 𝔽p-isomorphism classes of Montgomery curves. In order to calculate the class group action, we need to take points defined over 𝔽p2. The original CSIDH algorithm requires a calculation over 𝔽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 𝔽p4. Therefore, it is not a trivial task to calculate the class group action on Edwards curves with w-coordinates over only 𝔽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 𝔽p. This algorithm is as fast as (or a little bit faster than) the algorithm proposed by Meyer and Reith.

AB - 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 𝔽p-isomorphism classes of Montgomery curves. In order to calculate the class group action, we need to take points defined over 𝔽p2. The original CSIDH algorithm requires a calculation over 𝔽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 𝔽p4. Therefore, it is not a trivial task to calculate the class group action on Edwards curves with w-coordinates over only 𝔽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 𝔽p. This algorithm is as fast as (or a little bit faster than) the algorithm proposed by Meyer and Reith.

KW - Isogeny-based cryptography

KW - Montgomery curves

KW - Edwards curves

KW - CSIDH

KW - Post-quantum cryptography

U2 - 10.1007/978-3-030-40186-3_22

DO - 10.1007/978-3-030-40186-3_22

M3 - Conference contribution

SN - 9783030401856

T3 - Lecture Notes in Computer Science

SP - 512

EP - 537

BT - Topics in Cryptology – CT-RSA 2020

A2 - Jarecki, Stanislaw

PB - Springer

ER -

How to Construct CSIDH on Edwards Curves

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this