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 proceedingConference contributionpeer-review

1 Scopus citations


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 languageEnglish
Title of host publicationInformation Security Applications - 21st International Conference, WISA 2020, Revised Selected Papers
EditorsIlsun You
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages18
ISBN (Print)9783030652982
StatePublished - 2020
Externally publishedYes
Event21st International Conference on Information Security Applications, WISA 2020 - Jeju Island, Korea, Republic of
Duration: 26 08 202028 08 2020

Publication series

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


Conference21st International Conference on Information Security Applications, WISA 2020
Country/TerritoryKorea, Republic of
CityJeju Island

Bibliographical note

Publisher Copyright:
© Springer Nature Switzerland AG 2020.


  • Isogeny
  • Montgomery curves
  • Post-quantum cryptography


Dive into the research topics of 'Efficient algorithm for computing odd-degree isogenies on montgomery curves'. Together they form a unique fingerprint.

Cite this