Efficient Software Implementation of the SIKE Protocol Using a New Data Representation

被引:6
作者
Tian, Jing [1 ]
Wang, Piaoyang [1 ]
Liu, Zhe [2 ]
Lin, Jun [1 ]
Wang, Zhongfeng [1 ]
Grosschaedl, Johann [3 ]
机构
[1] Nanjing Univ, Sch Elect Sci & Engn, Nanjing 210093, Peoples R China
[2] Nanjing Univ Aeronaut & Astronaut, Coll Comp Sci & Technol, Nanjing 210016, Peoples R China
[3] Univ Luxembourg, L-4365 Esch Sur Alzette, Luxembourg
基金
中国国家自然科学基金; 国家重点研发计划;
关键词
Protocols; Cryptography; Elliptic curves; Elliptic curve cryptography; Software algorithms; Public key; NIST; Supersingular Isogeny Diffie-Hellman (SIDH) key exchange; Elliptic Curve Cryptography (ECC); modular reduction operation; montgomery representation; barrett representation; Post-Quantum Cryptography (PQC); MULTIPLICATION; TIME;
D O I
10.1109/TC.2021.3057331
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Thanks to relatively small public and secret keys, the Supersingular Isogeny Key Encapsulation (SIKE) protocol made it into the third evaluation round of the post-quantum standardization project of the National Institute of Standards and Technology (NIST). Even though a large body of research has been devoted to the efficient implementation of SIKE, its latency is still undesirably long for many real-world applications. Most existing implementations of the SIKE protocol use the Montgomery representation for the underlying field arithmetic since the corresponding reduction algorithm is considered the fastest method for performing multiple-precision modular reduction. In this paper, we propose a new data representation for supersingular isogeny-based Elliptic-Curve Cryptography (ECC), of which SIKE is a sub-class. This new representation enables significantly faster implementations of modular reduction than the Montgomery reduction, and also other finite-field arithmetic operations used in ECC can benefit from our data representation. We implemented all arithmetic operations in C using the proposed representation such that they have constant execution time and integrated them to the latest version of the SIKE software library. Using four different parameters sets, we benchmarked our design and the optimized generic implementation on a 2.6 GHz Intel Xeon E5-2690 processor. Our results show that, for the prime of SIKEp751, the proposed reduction algorithm is approximately 2.61 times faster than the currently best implementation of Montgomery reduction, and our representation also enables significantly better timings for other finite-field operations. Due to these improvements, we were able to achieve a speed-up by a factor of about 1.65, 2.03, 1.61, and 1.48 for SIKEp751, SIKEp610, SIKEp503, and SIKEp434, respectively, compared to state-of-the-art generic implementations.
引用
收藏
页码:670 / 683
页数:14
相关论文
共 41 条
[1]  
Azarderakhsh R., 2014, CTR APPL CRYPTOGR RE, V20
[2]  
Azarderakhsh R, 2017, Supersingular Isogeny Key Encapsulation. Submission to the NIST Post-Quantum Standardization Project
[3]  
Azarderakhsh Reza., 2016, Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography, AsiaPKC'16, page, P1, DOI DOI 10.1145/2898420.2898421
[4]  
BARRETT P, 1987, LECT NOTES COMPUT SC, V263, P311
[5]   Arithmetic Considerations for Isogeny-Based Cryptography [J].
Bos, Joppe W. ;
Friedberger, Simon J. .
IEEE TRANSACTIONS ON COMPUTERS, 2019, 68 (07) :979-990
[6]  
Chen L, 2016, REPORT POSTQUANTUM C, V12
[7]   EXPONENTIATION CRYPTOSYSTEMS ON THE IBM PC [J].
COMBA, PG .
IBM SYSTEMS JOURNAL, 1990, 29 (04) :526-538
[8]   ON MINIMUM COMPUTATION TIME OF FUNCTIONS [J].
COOK, SA ;
AANDERAA, SO .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1969, 142 (AUG) :291-+
[9]  
Costello C., 2020, PQCRYPTO SIDH
[10]   Efficient Algorithms for Supersingular Isogeny Diffie-Hellman [J].
Costello, Craig ;
Longa, Patrick ;
Naehrig, Michael .
ADVANCES IN CRYPTOLOGY - CRYPTO 2016, PT I, 2016, 9814 :572-601