Efficient algorithm for computing odd-degree isogenies on montgomery curves

Kenta Kodera; Chen Mou Cheng; Atsuko Miyaji

doi:10.1007/978-3-030-65299-9_20

Efficient algorithm for computing odd-degree isogenies on montgomery curves

Kenta Kodera^*, Chen Mou Cheng, Atsuko Miyaji

^*Corresponding author for this work

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

1 Scopus citations

Abstract

Isogeny-based cryptography, such as commutative supersingular isogeny Diffie-Hellman (CSIDH), has been shown to be promising candidates for post-quantum cryptography. However, their speeds have remained unremarkable. For example, computing odd-degree isogenies between Montgomery curves is a dominant computation in CSIDH. To increase the speed of this isogeny computation, this study proposes a new technique called the “2-ADD-Skip method,” which reduces the required number of points to be computed. This technique is then used to develop a novel algorithm for isogeny computation. It is found that the proposed algorithm requires fewer field arithmetic operations for the degrees of ℓ≥ 19 compared with the algorithm of Meyer et al., which utilizes twisted Edwards curves. Further, a prototype CSIDH-512 implementation shows that the proposed algorithm can give a 6.7% speedup over the implementation by Meyer et al. Finally, individual experiments for each degree of isogeny show that the proposed algorithm requires the lowest number of clock cycles among existing algorithms for 19 ≤ ℓ≤ 373.

Original language	English
Title of host publication	Information Security Applications - 21st International Conference, WISA 2020, Revised Selected Papers
Editors	Ilsun You
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	258-275
Number of pages	18
ISBN (Print)	9783030652982
DOIs	https://doi.org/10.1007/978-3-030-65299-9_20
State	Published - 2020
Externally published	Yes
Event	21st International Conference on Information Security Applications, WISA 2020 - Jeju Island, Korea, Republic of Duration: 26 08 2020 → 28 08 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12583 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Conference on Information Security Applications, WISA 2020
Country/Territory	Korea, Republic of
City	Jeju Island
Period	26/08/20 → 28/08/20

Bibliographical note

Publisher Copyright:
© Springer Nature Switzerland AG 2020.

Keywords

Isogeny
Montgomery curves
Post-quantum cryptography

Access to Document

10.1007/978-3-030-65299-9_20

Cite this

Kodera, K., Cheng, C. M., & Miyaji, A. (2020). Efficient algorithm for computing odd-degree isogenies on montgomery curves. In I. You (Ed.), Information Security Applications - 21st International Conference, WISA 2020, Revised Selected Papers (pp. 258-275). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12583 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-65299-9_20

Kodera, Kenta ; Cheng, Chen Mou ; Miyaji, Atsuko. / Efficient algorithm for computing odd-degree isogenies on montgomery curves. Information Security Applications - 21st International Conference, WISA 2020, Revised Selected Papers. editor / Ilsun You. Springer Science and Business Media Deutschland GmbH, 2020. pp. 258-275 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{54ffeacbf81a4104b99943d7bce5bef2,

title = "Efficient algorithm for computing odd-degree isogenies on montgomery curves",

abstract = "Isogeny-based cryptography, such as commutative supersingular isogeny Diffie-Hellman (CSIDH), has been shown to be promising candidates for post-quantum cryptography. However, their speeds have remained unremarkable. For example, computing odd-degree isogenies between Montgomery curves is a dominant computation in CSIDH. To increase the speed of this isogeny computation, this study proposes a new technique called the “2-ADD-Skip method,” which reduces the required number of points to be computed. This technique is then used to develop a novel algorithm for isogeny computation. It is found that the proposed algorithm requires fewer field arithmetic operations for the degrees of ℓ≥ 19 compared with the algorithm of Meyer et al., which utilizes twisted Edwards curves. Further, a prototype CSIDH-512 implementation shows that the proposed algorithm can give a 6.7% speedup over the implementation by Meyer et al. Finally, individual experiments for each degree of isogeny show that the proposed algorithm requires the lowest number of clock cycles among existing algorithms for 19 ≤ ℓ≤ 373.",

keywords = "Isogeny, Montgomery curves, Post-quantum cryptography",

author = "Kenta Kodera and Cheng, {Chen Mou} and Atsuko Miyaji",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020.; 21st International Conference on Information Security Applications, WISA 2020 ; Conference date: 26-08-2020 Through 28-08-2020",

year = "2020",

doi = "10.1007/978-3-030-65299-9_20",

language = "英语",

isbn = "9783030652982",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "258--275",

editor = "Ilsun You",

booktitle = "Information Security Applications - 21st International Conference, WISA 2020, Revised Selected Papers",

address = "德国",

}

Kodera, K, Cheng, CM & Miyaji, A 2020, Efficient algorithm for computing odd-degree isogenies on montgomery curves. in I You (ed.), Information Security Applications - 21st International Conference, WISA 2020, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12583 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 258-275, 21st International Conference on Information Security Applications, WISA 2020, Jeju Island, Korea, Republic of, 26/08/20. https://doi.org/10.1007/978-3-030-65299-9_20

Efficient algorithm for computing odd-degree isogenies on montgomery curves. / Kodera, Kenta; Cheng, Chen Mou; Miyaji, Atsuko.
Information Security Applications - 21st International Conference, WISA 2020, Revised Selected Papers. ed. / Ilsun You. Springer Science and Business Media Deutschland GmbH, 2020. p. 258-275 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12583 LNCS).

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

TY - GEN

T1 - Efficient algorithm for computing odd-degree isogenies on montgomery curves

AU - Kodera, Kenta

AU - Cheng, Chen Mou

AU - Miyaji, Atsuko

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2020.

PY - 2020

Y1 - 2020

N2 - Isogeny-based cryptography, such as commutative supersingular isogeny Diffie-Hellman (CSIDH), has been shown to be promising candidates for post-quantum cryptography. However, their speeds have remained unremarkable. For example, computing odd-degree isogenies between Montgomery curves is a dominant computation in CSIDH. To increase the speed of this isogeny computation, this study proposes a new technique called the “2-ADD-Skip method,” which reduces the required number of points to be computed. This technique is then used to develop a novel algorithm for isogeny computation. It is found that the proposed algorithm requires fewer field arithmetic operations for the degrees of ℓ≥ 19 compared with the algorithm of Meyer et al., which utilizes twisted Edwards curves. Further, a prototype CSIDH-512 implementation shows that the proposed algorithm can give a 6.7% speedup over the implementation by Meyer et al. Finally, individual experiments for each degree of isogeny show that the proposed algorithm requires the lowest number of clock cycles among existing algorithms for 19 ≤ ℓ≤ 373.

AB - Isogeny-based cryptography, such as commutative supersingular isogeny Diffie-Hellman (CSIDH), has been shown to be promising candidates for post-quantum cryptography. However, their speeds have remained unremarkable. For example, computing odd-degree isogenies between Montgomery curves is a dominant computation in CSIDH. To increase the speed of this isogeny computation, this study proposes a new technique called the “2-ADD-Skip method,” which reduces the required number of points to be computed. This technique is then used to develop a novel algorithm for isogeny computation. It is found that the proposed algorithm requires fewer field arithmetic operations for the degrees of ℓ≥ 19 compared with the algorithm of Meyer et al., which utilizes twisted Edwards curves. Further, a prototype CSIDH-512 implementation shows that the proposed algorithm can give a 6.7% speedup over the implementation by Meyer et al. Finally, individual experiments for each degree of isogeny show that the proposed algorithm requires the lowest number of clock cycles among existing algorithms for 19 ≤ ℓ≤ 373.

KW - Isogeny

KW - Montgomery curves

KW - Post-quantum cryptography

UR - http://www.scopus.com/inward/record.url?scp=85098269401&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-65299-9_20

DO - 10.1007/978-3-030-65299-9_20

M3 - 会议稿件

AN - SCOPUS:85098269401

SN - 9783030652982

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 258

EP - 275

BT - Information Security Applications - 21st International Conference, WISA 2020, Revised Selected Papers

A2 - You, Ilsun

PB - Springer Science and Business Media Deutschland GmbH

T2 - 21st International Conference on Information Security Applications, WISA 2020

Y2 - 26 August 2020 through 28 August 2020

ER -

Kodera K, Cheng CM, Miyaji A. Efficient algorithm for computing odd-degree isogenies on montgomery curves. In You I, editor, Information Security Applications - 21st International Conference, WISA 2020, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2020. p. 258-275. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-65299-9_20

Efficient algorithm for computing odd-degree isogenies on montgomery curves

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this