You are looking at a specific version 20200603:095730 of this paper. See the latest version.

Paper 2020/660

Faster Software Implementation of the SIKE Protocol Based on A New Data Representation

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

Abstract

Due to the smaller size in public and secret keys over other candidates for post-quantum cryptography (PQC), the supersingular isogeny key encapsulation (SIKE) protocol has survived from the second round fierce competition hosted by the National Institute of Standards and Technology (NIST) in January 2019. Many efforts have been done by researchers to reduce the computation latency, which, however, is still far more than desired. In the SIKE implementation, the Montgomery representation has been mostly adopted in the finite field arithmetic computing as the corresponding reduction algorithm is considered the fastest method for implementing the modular reduction. In this paper, we propose a new data representation for the supersingular isogeny-based elliptic-curve cryptography (ECC), of which the SIKE is a subclass. The new representation can facilitate faster modular reduction implementation than the Montgomery reduction. Meanwhile, the other finite field arithmetic operations in the ECC can also benefit from the proposed data representation. We have implemented all the arithmetic operations in C language with constant execution time based on our proposed data representation and applied them to the newest SIKE software library. Targeting at the SIKEp751, we run our design and the optimized implementation on a 2.6GHz Intel Xeon E5-2690 processor. The experiment results show that for the parameters of SIKEp751, the proposed modular reduction algorithm is about 2.61x faster than the best Montgomery one and our scheme also performs significantly better for the other finite field operations. With these improvements, the overall software implementation for the SIKEp751 achieves about 1.65x speedup compared to the state-of-the-art implementation.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
elliptic curve cryptography (ECC)modular reductionMontgomery representationBarrett reductionpost-quantum cryptography (PQC).
Contact author(s)
jingtian_nju @ sina com
History
2021-07-09: revised
2020-06-03: received
See all versions
Short URL
https://ia.cr/2020/660
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.