Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves

Suhri Kim; Kisoon Yoon; Young Ho Park; Seokhie Hong

doi:10.1007/978-3-030-34621-8_10

Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves

Suhri Kim, Kisoon Yoon, Young Ho Park, Seokhie Hong

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

17 Citations (Scopus)

Abstract

In this paper, we present an efficient method to compute arbitrary odd-degree isogenies on Edwards curves. By using the w-coordinate, we optimized the isogeny formula on Edwards curves by Moody and Shumow. We demonstrate that Edwards curves have an additional benefit when recovering the coefficient of the image curve during isogeny computation. For (formula presented)-degree isogeny where (formula presented), our isogeny formula on Edwards curves outperforms Montgomery curves when (formula presented). To better represent the performance improvements when w-coordinate is used, we implement CSIDH using our isogeny formula. Our implementation is about 20% faster than the previous implementation. The result of our work opens the door for the usage of Edwards curves in isogeny-based cryptography, especially for CSIDH which requires higher degree isogenies.

Original language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Editors	Steven D. Galbraith, Shiho Moriai
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	273-292
Number of pages	20
ISBN (Print)	9783030346201
DOIs	https://doi.org/10.1007/978-3-030-34621-8_10
Publication status	Published - 2019
Event	25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019 - Kobe, Japan Duration: 2019 Dec 8 → 2019 Dec 12

Publication series

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

Conference

Conference	25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019
Country/Territory	Japan
City	Kobe
Period	19/12/8 → 19/12/12

Keywords

CSIDH
Edwards curves
Isogeny
Montgomery curves
Post-quantum cryptography
SIDH

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-030-34621-8_10

Cite this

Kim, S., Yoon, K., Park, Y. H., & Hong, S. (2019). Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves. In S. D. Galbraith, & S. Moriai (Eds.), Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 273-292). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11922 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-34621-8_10

Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves. / Kim, Suhri; Yoon, Kisoon; Park, Young Ho et al.
Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. ed. / Steven D. Galbraith; Shiho Moriai. Springer Science and Business Media Deutschland GmbH, 2019. p. 273-292 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11922 LNCS).

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

Kim, S, Yoon, K, Park, YH & Hong, S 2019, Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves. in SD Galbraith & S Moriai (eds), Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11922 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 273-292, 25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019, Kobe, Japan, 19/12/8. https://doi.org/10.1007/978-3-030-34621-8_10

Kim S, Yoon K, Park YH, Hong S. Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves. In Galbraith SD, Moriai S, editors, Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Springer Science and Business Media Deutschland GmbH. 2019. p. 273-292. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-34621-8_10

Kim, Suhri ; Yoon, Kisoon ; Park, Young Ho et al. / Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves. Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. editor / Steven D. Galbraith ; Shiho Moriai. Springer Science and Business Media Deutschland GmbH, 2019. pp. 273-292 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{956c7596b11b4071b1bcf22227c8ffa3,

title = "Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves",

abstract = "In this paper, we present an efficient method to compute arbitrary odd-degree isogenies on Edwards curves. By using the w-coordinate, we optimized the isogeny formula on Edwards curves by Moody and Shumow. We demonstrate that Edwards curves have an additional benefit when recovering the coefficient of the image curve during isogeny computation. For (formula presented)-degree isogeny where (formula presented), our isogeny formula on Edwards curves outperforms Montgomery curves when (formula presented). To better represent the performance improvements when w-coordinate is used, we implement CSIDH using our isogeny formula. Our implementation is about 20% faster than the previous implementation. The result of our work opens the door for the usage of Edwards curves in isogeny-based cryptography, especially for CSIDH which requires higher degree isogenies.",

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

author = "Suhri Kim and Kisoon Yoon and Park, {Young Ho} and Seokhie Hong",

note = "Funding Information: This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. NRF-2017R1A2B4011599). Publisher Copyright: {\textcopyright} 2019, International Association for Cryptologic Research.; 25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019 ; Conference date: 08-12-2019 Through 12-12-2019",

year = "2019",

doi = "10.1007/978-3-030-34621-8_10",

language = "English",

isbn = "9783030346201",

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 = "273--292",

editor = "Galbraith, {Steven D.} and Shiho Moriai",

booktitle = "Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves

AU - Kim, Suhri

AU - Yoon, Kisoon

AU - Park, Young Ho

AU - Hong, Seokhie

N1 - Funding Information: This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. NRF-2017R1A2B4011599). Publisher Copyright: © 2019, International Association for Cryptologic Research.

PY - 2019

Y1 - 2019

N2 - In this paper, we present an efficient method to compute arbitrary odd-degree isogenies on Edwards curves. By using the w-coordinate, we optimized the isogeny formula on Edwards curves by Moody and Shumow. We demonstrate that Edwards curves have an additional benefit when recovering the coefficient of the image curve during isogeny computation. For (formula presented)-degree isogeny where (formula presented), our isogeny formula on Edwards curves outperforms Montgomery curves when (formula presented). To better represent the performance improvements when w-coordinate is used, we implement CSIDH using our isogeny formula. Our implementation is about 20% faster than the previous implementation. The result of our work opens the door for the usage of Edwards curves in isogeny-based cryptography, especially for CSIDH which requires higher degree isogenies.

AB - In this paper, we present an efficient method to compute arbitrary odd-degree isogenies on Edwards curves. By using the w-coordinate, we optimized the isogeny formula on Edwards curves by Moody and Shumow. We demonstrate that Edwards curves have an additional benefit when recovering the coefficient of the image curve during isogeny computation. For (formula presented)-degree isogeny where (formula presented), our isogeny formula on Edwards curves outperforms Montgomery curves when (formula presented). To better represent the performance improvements when w-coordinate is used, we implement CSIDH using our isogeny formula. Our implementation is about 20% faster than the previous implementation. The result of our work opens the door for the usage of Edwards curves in isogeny-based cryptography, especially for CSIDH which requires higher degree isogenies.

KW - CSIDH

KW - Edwards curves

KW - Isogeny

KW - Montgomery curves

KW - Post-quantum cryptography

KW - SIDH

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

U2 - 10.1007/978-3-030-34621-8_10

DO - 10.1007/978-3-030-34621-8_10

M3 - Conference contribution

AN - SCOPUS:85077015784

SN - 9783030346201

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

SP - 273

EP - 292

BT - Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

A2 - Galbraith, Steven D.

A2 - Moriai, Shiho

PB - Springer Science and Business Media Deutschland GmbH

T2 - 25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019

Y2 - 8 December 2019 through 12 December 2019

ER -

Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this