Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves

被引：18

作者：

Kim, Suhri ^{[1
]}

Yoon, Kisoon ^{[2
]}

Park, Young-Ho ^{[3
]}

Hong, Seokhie ^{[1
]}

机构：

[1] Korea Univ, Ctr Informat Secur Technol CIST, Seoul, South Korea

[2] NSHC Inc, Uiwang, South Korea

[3] Sejong Cyber Univ, Seoul, South Korea

来源：

ADVANCES IN CRYPTOLOGY - ASIACRYPT 2019, PT II | 2019年 / 11922卷

基金：

新加坡国家研究基金会;

关键词：

Isogeny; Post-quantum cryptography; Montgomery curves; Edwards curves; SIDH; CSIDH;

D O I：

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

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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 l-degree isogeny where l = 2s+ 1, our isogeny formula on Edwards curves outperforms Montgomery curves when s = 2. 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 isogenybased cryptography, especially for CSIDH which requires higher degree isogenies.

引用

页码：273 / 292

页数：20

共 23 条

[11] Efficient Algorithms for Supersingular Isogeny Diffie-Hellman
Costello, Craig
Longa, Patrick
Naehrig, Michael
[J]. ADVANCES IN CRYPTOLOGY - CRYPTO 2016, PT I, 2016, 9814 : 572 - 601
[12] De Feo Luca, 2018, Advances in Cryptology - ASIACRYPT 2018. 24th International Conference on the Theory and Application of Cryptology and Information Security. Proceedings: Lecture Notes in Computer Science (LNCS 11274), P365, DOI 10.1007/978-3-030-03332-3_14
[13] Differential Addition on Twisted Edwards Curves
Farashahi, Reza Rezaeian
Hosseini, Seyed Gholamhossein
[J]. INFORMATION SECURITY AND PRIVACY, ACISP 2017, PT II, 2017, 10343 : 366 - 378
[14] Hisil H, 2008, LECT NOTES COMPUT SC, V5350, P326, DOI 10.1007/978-3-540-89255-7_20
[15] Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies
Jao, David
De Feo, Luca
[J]. POST-QUANTUM CRYPTOGRAPHY, 2011, 7071 : 19 - +
[16] New Hybrid Method for Isogeny-Based Cryptosystems Using Edwards Curves
Kim, Suhri
Yoon, Kisoon
Kwon, Jihoon
Park, Young-Ho
Hong, Seokhie
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (03) : 1934 - 1943
[17] Mendel F, 2011, LECT NOTES COMPUT SC, V7073, P288, DOI 10.1007/978-3-642-25385-0_16
[18] Meyer M., 2017, HYBRID SIDH SCHEMES
[19] A Faster Way to the CSIDH
Meyer, Michael
Reith, Steffen
[J]. PROGRESS IN CRYPTOLOGY, INDOCRYPT 2018, 2018, 11356 : 137 - 152
[20] ANALOGUES OF VELU'S FORMULAS FOR ISOGENIES ON ALTERNATE MODELS OF ELLIPTIC CURVES
Moody, Dustin
Shumow, Daniel
[J]. MATHEMATICS OF COMPUTATION, 2016, 85 (300) : 1929 - 1951

← 1 2 3 →