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

Jing Tian, Piaoyang Wang, Zhe Liu, Jun Lin, Zhongfeng Wang, and Johann Großschädl

##### Abstract

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.IKEp751, SIKEp610, SIKEp503, and SIKEp434, respectively, compared to state-of-the-art generic implementations.

Available format(s)
Category
Implementation
Publication info
Published elsewhere. IEEE Transactions on Computers
DOI
10.1109/TC.2021.3057331
Keywords
elliptic curve cryptography (ECC)modular reductionMontgomery representationBarrett reductionpost-quantum cryptography (PQC).
Contact author(s)
jingtian_nju @ sina com
History
2021-07-09: revised
See all versions
Short URL
https://ia.cr/2020/660

CC BY

BibTeX

@misc{cryptoeprint:2020/660,
author = {Jing Tian and Piaoyang Wang and Zhe Liu and Jun Lin and Zhongfeng Wang and Johann Großschädl},
title = {Efficient Software Implementation of the SIKE Protocol Using a New Data Representation},
howpublished = {Cryptology ePrint Archive, Paper 2020/660},
year = {2020},
doi = {10.1109/TC.2021.3057331},
note = {\url{https://eprint.iacr.org/2020/660}},
url = {https://eprint.iacr.org/2020/660}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.