A Lightweight General Modular Multiplier for Kyber PQC

Naderi Varandi, Hossein; Salarifard, Raziye

doi:10.22042/isecure.2025.217886

A Lightweight General Modular Multiplier for Kyber PQC

Document Type : Research Article

Authors

Hossein Naderi Varandi

Raziye Salarifard

Faculty of Computer Science and Engineering, Shahid Beheshti University, Tehran, Iran

https://doi.org/10.22042/isecure.2025.217886

Abstract

Kyber, a key encapsulation mechanism (KEM), plays a pivotal role in post-quantum cryptography. As a finalist in the NIST project, Kyber is gaining traction in industry libraries and systems. The heart of the Kyber algorithm lies in the Number Theoretic Transform (NTT), where modular multiplication is the most intricate operation. In this paper, we propose a novel general modular multiplier that reduces both time and area requirements compared to prior methods. Our key innovation lies in the novel reduction algorithm, which avoids fixed values for coefficients A or B (i.e., C = A × B mod q) used in NTT, Inverse NTT (INTT), and PWM (Point-Wise Multiplication). Additionally we introduce two pipeline architectures for modular multiplication within Kyber, emphasizing low area usage and high frequency. These architectures demonstrate 8% and 31% better frequency, while our work achieves the lowest slice usage and AT (Area × Time) among all previous work.

Keywords

Post-Quantum Cryptography

Crystals-Kyber

NTT Multiplier

Modular Multiplier

[1] P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, SFCS-94. IEEE Comput. Soc. Press.
[2] R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler, and D. Stehle. Crystals-kyber: Algorithm specification and supporting documentation (version 3.2). submission to the nist post-quantum cryptography standardization project, 2021.
[3] Yufei Xing and Shuguo Li. A compact hardware implementation of cca-secure key exchange mechanism crystals-kyber on fpga. IACR Transactions on Cryptographic Hardware and Embedded Systems, page 328–356, February 2021.
[4] Safiullah Khan, Ayesha Khalid, Ciara Rafferty, Yasir Ali Shah, Maire O’Neill, Wai-Kong Lee, and Seong Oun Hwang. Efficient, error-resistant ntt architectures for crystals-kyber fpga accelerators. In 2023 IFIP/IEEE 31st International Conference on Very Large Scale Integration (VLSI-SoC). IEEE, October 2023.
[5] Erdem Alkim, H¨ulya Evkan, Norman Lahr, Ruben Niederhagen, and Richard Petri. Isa extensions for finite field arithmetic - accel-erating kyber and newhope on risc-v. Cryptology ePrint Archive, Paper 2020/049, 2020. https://eprint.iacr.org/2020/049.
[6] Qingru Zeng, Quanxin Li, Baoze Zhao, Han Jiao, and Yihua Huang. Hardware design and implementation of post-quantum cryptography kyber. In 2022 IEEE High Performance Extreme Computing Conference (HPEC). IEEE, September 2022.
[7] Hang Yang, Rongmao Chen, Qiong Wang, Zixuan Wu, and Wei Peng. Hardware Acceleration of NTT-Based Polynomial Multiplication in CRYSTALS-Kyber, page 111–129. Springer Nature Singapore, 2024.
[8] Tuy Tan Nguyen, Sungjae Kim, Yongjun Eom, and Hanho Lee. Area-time efficient hardware architecture for crystals-kyber. Applied Sciences, 12(11):5305, May 2022.
[9] Lirui Zhao, Jipeng Zhang, Junhao Huang, Zhe Liu, and Gerhard Hancke. Efficient implementation of kyber on mobile devices. In 2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS). IEEE, December 2021.
[10] Leon Botros, Matthias J. Kannwischer, and Peter Schwabe. Memory-Efficient High-Speed Implementation of Kyber on Cortex-M4, page 209–228. Springer International Publishing, 2019.
[11] Vincent Hwang, Jiaxiang Liu, Gregor Seiler, Xiaomu Shi, Ming-Hsien Tsai, Bow-Yaw Wang, and Bo-Yin Yang. Verified ntt multiplications for nistpqc kem lattice finalists: Kyber, saber, and ntru. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(4):718–750, Aug. 2022.
[12] Yiming Huang, Miaoqing Huang, Zhongkui Lei, and Jiaxuan Wu. A pure hardware implementation of crystals-kyber pqc algorithm through resource reuse. IEICE Electronics Express, 17(17):20200234–20200234, September 2020.
[13] Patrick Longa and Michael Naehrig. Speeding up the number theoretic transform for faster ideal lattice-based cryptography. Cryptology ePrint Archive, Paper 2016/504, 2016. https://eprint.iacr.org/2016/504.
[14] Mojtaba Bisheh-Niasar, Reza Azarderakhsh, and Mehran Mozaffari-Kermani. High-speed ntt-based polynomial multiplication accelerator for post-quantum cryptography. In 2021 IEEE 28th Symposium on Computer Arithmetic(ARITH). IEEE, June 2021.
[15] Yuma Itabashi, Rei Ueno, and Naofumi Homma. Efficient modular polynomial multiplier for ntt accelerator of crystals-kyber. In 2022 25th Eu-romicro Conference on Digital System Design(DSD). IEEE, August 2022.
[16] Raziyeh Salarifard and Hadi Soleimany. An efficient hardware accelerator for ntt-based polynomial multiplication using fpga. Journal of Cryptographic Engineering, 14(2):415–426, June 2024.
[17] Ferhat Yaman, Ahmet Can Mert, Erdin¸c ¨Ozt¨urk, and Erkay Sava¸s. A hardware accelerator for polynomial multiplication operation of crystals-kyber pqc scheme. Cryptology ePrint Archive, Paper 2021/485, 2021. https://eprint.iacr.org/2021/485.
[18] Wenbo Guo, Shuguo Li, and Liang Kong. An efficient implementation of kyber. IEEE Transactions on Circuits and Systems II: Express Briefs, 69(3):1562–1566, March 2022.
[19] Raziyeh Salarifard, Reza Rashidian, Reyhaneh Kharazmi, and Ali Jahanian. Efficient ntt multiplier of ntru prime pqc algorithm. Journal of Innovations in Computer Science and Engineering (JICSE), 1(1), June 2023.
[20] Trong-Hung Nguyen, Cong-Kha Pham, and Trong-Thuc Hoang. A High-Speed Barret-Based Modular Multiplication with Bit-Correction for the CRYSTAL-KYBER Cryptosystem, page 191–199. Springer Nature Switzerland, 2023.