A Novel Modular Multiplier for Isogeny-Based Post-Quantum Cryptography
Bo Wu, Jing Tian, Xiao Hong Hu, Zhongfeng Wang · 2020
Supersingular isogeny key encapsulation (SIKE) protocol is a promising candidate for the standard of post quantum cryptography (PQC), but it suffers from high computational complexity. Since the modular multiplication takes up a large proportion of the computations in SIKE protocol, accelerating this operation can efficiently speed up the entire protocol. In this paper, we propose a new modular multiplication algorithm, which can achieve lower complexity than prior arts. The SIKE-friendly prime with form of p = 2nxlBny+1 = Rn+1 is considered. The modulo-p operation is mainly replaced by n modulo-R operations, for which a general Barrett reduction( GBR) algorithm is presented and applied. Moreover, an efficient architecture is designed for the proposed algorithm, where the pipelining and interleaved techniques are applied. For the multiply-accumulate (MAC) part, various optimization techniques are introduced to reduce the data path and the complexity. The FPGA implementation results show that for a level-5 quantum-security parameter, our design achieves the fastest clock speed with middle number of clock cycles and small resources consumption among the state-of-the-art works.