Cryptology ePrint Archive: Report 2020/246

Ultra-Fast Modular Multiplication Implementation for Isogeny-Based Post-Quantum Cryptography

Jing Tian and Jun Lin and Zhongfeng Wang

Abstract: Supersingular isogeny key encapsulation (SIKE) protocol delivers promising public and secret key sizes over other post-quantum candidates. However, the huge computations form the bottleneck and limit its practical applications. The modular multiplication operation, which is one of the most computationally demanding operations in the fundamental arithmetics, takes up a large part of the computations in the protocol. In this paper, we propose an improved unconventional-radix finite-field multiplication (IFFM) algorithm which reduces the computational complexity by about 20% compared to previous algorithms. We then devise a new high-speed modular multiplier architecture based on the IFFM. It is shown that the proposed architecture can be extensively pipelined to achieve a very high clock speed due to its complete feedforward scheme, which demonstrates significant advantages over conventional designs. The FPGA implementation results show the proposed multiplier has about 67 times faster throughput than the state-of-the-art designs and more than 12 times better area efficiency than previous works. Therefore, we think that these achievements will greatly contribute to the practicability of this protocol.

Category / Keywords: implementation / Modular multiplication, supersingular isogeny Diffie-Hellman (SIDH) key exchange, post-quantum cryptography (PQC), hardware architecture, FPGA.

Original Publication (in the same form): 2019 IEEE Workshop on Signal Processing Systems (SiPS)

Date: received 23 Feb 2020

Contact author: jingtian_nju at sina com

Available format(s): PDF | BibTeX Citation

Version: 20200225:203658 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]