Paper 2019/1206

High-Speed Modular Multipliers for Isogeny-Based Post-Quantum Cryptography

Jing Tian, Zhe Liu, Jun Lin, Zhongfeng Wang, and Binjing Li

Abstract

As one of the post-quantum protocol candidates, the supersingular isogeny key encapsulation (SIKE) protocol delivers promising public and secret key sizes over other candidates. Nevertheless, the considerable computations form the bottleneck and limit its practical applications. The modular multiplication operations occupy a large proportion of the overall computations required by the SIKE protocol. The VLSI implementation of the high-speed modular multiplier remains a big challenge. In this paper, we propose three improved modular multiplication algorithms based on an unconventional radix for this protocol, all of which cost about 20% fewer computations than the prior art. Besides, a multi-precision scheme is also introduced for the proposed algorithms to improve the scalability in hardware implementation, resulting in three new algorithms. We then present very efficient high-speed modular multiplier architectures for the six algorithms. It is shown that these new architectures can be highly optimized and extensively pipelined to obtain high throughput thanks to the adopted overlapping processing scheme. The FPGA implementation results show the proposed multipliers without the multi-precision scheme all achieve about 60 times higher throughput than the state-of-the-art design (the FFM2 multiplier), and those with the multi-precision scheme all acquire almost 10 times higher throughput than this work. Meanwhile, each of the multi-precision based designs has almost the same resource consumptions as the FFM2 does.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
Modular multiplicationpost-quantum cryptography (PQC)FPGAVLSI.
Contact author(s)
jingtian @ smail nju edu cn
History
2019-10-16: received
Short URL
https://ia.cr/2019/1206
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1206,
      author = {Jing Tian and Zhe Liu and Jun Lin and Zhongfeng Wang and Binjing Li},
      title = {High-Speed Modular Multipliers for Isogeny-Based Post-Quantum Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1206},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1206}},
      url = {https://eprint.iacr.org/2019/1206}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.