一种面积高效的双态可配置NTT硬件加速器

doi:10.3969/j.issn.1671-1122.2024.06.013

摘要/Abstract

摘要：

矩阵向量乘法是基于格的后量子密码（Post-Quantum Cryptography，PQC）方案的主要计算瓶颈。利用数论变换（Number Theoretic Transform，NTT）能将矩阵向量乘法的计算复杂度从O(N²)降到O(Nlog₂N)，从而可以进一步提高后量子密码方案的计算速度。文章基于现场可编程门阵列（Field Programmable Gate Array, FPGA）提出了一种面积高效的双态可配置NTT硬件加速器，能高效地执行Kyber和Dilithium算法中的NTT运算。文章所提方案使用的模乘器通过查找表（Look Up Table，LUT）技术压缩数据位宽降低取模成本后，利用KRED算法对结果约简。此外，结合优化后的无冲突NTT数据流，文章所提出的双态可配置NTT加速器可以高效完成计算。文章所提出的NTT硬件加速器在Xilinx Artix-7平台上进行了验证。相较于参考文献方案，文章所提出的双态可配置NTT硬件加速器在保持对Kyber和Dilithium算法通用性的同时，在计算性能和硬件开销等方面表现更好。

关键词: 后量子密码, 快速数论变换, 模乘, 硬件加速, 现场可编程门阵列

Abstract:

Matrix-vector multiplication is the main computational bottleneck of lattice-based Post-Quantum Cryptography (PQC) schemes. Utilizing the number theoretic transform (NTT) can reduce the computational complexity of matrix-vector multiplication from O(N²) to O(Nlog₂N), thereby further improving the computational speed of post-quantum cryptographic schemes. This article proposed an area-efficient dual-mode configurable NTT hardware accelerator based on field programmable gate array (FPGA), capable of efficiently executing NTT operations in the Kyber and Dilithium algorithms. The multiplier used in the proposed design compresses data bit width and reduced modulo costs using table lookup techniques, followed by reduction of results using the KRED algorithm. Furthermore, by combining optimized non-conflicting NTT data streams, the proposed dual-mode configurable NTT accelerator can efficiently complete computations. The NTT hardware accelerator proposed in this article is validated on the Xilinx Artix-7 platform. Compared to the reference work, the proposed dual-mode configurable NTT hardware accelerator performs better in terms of computational performance and hardware overhead while maintaining generality for Kyber and Dilithium algorithms.

Key words: post-quantum cryptography, number theoretic transform, modular multiplication, hardware acceleration, field programmable gate array

中图分类号:

TP309

朱敏, 肖昊. 一种面积高效的双态可配置NTT硬件加速器[J]. 信息网络安全, 2024, 24(6): 959-967.

ZHU Min, XIAO Hao. An Area Efficient Dual-State Configurable NTT Hardware Accelerator[J]. Netinfo Security, 2024, 24(6): 959-967.

图/表 7

图1

图2

图3

图4

表1

表2

表3

参考文献 18

[1]	TAO Yunting, KONG Fanyu, YU Jia, et al. Survey of Number Theoretic Transform Algorithms for Quantum-Resistant Lattice-Based Cryptography[J]. Netinfo Security, 2021, 21(9): 46-51.
	陶云亭, 孔凡玉, 于佳, 等. 抗量子格密码体制的快速数论变换算法研究综述[J]. 信息网络安全, 2021, 21(9):46-51.
[2]	ALAGIC G, ALPERIN-SHERIFF J, APON D, et al. Status Reporton the Second Round of the NIST Post-Quantum CryptographyStandardization Process[R]. Gaithersburg: NIST, 8309, 2020.
[3]	LIU Zhe, PÖPPELMANN T, ODER T, et al. High-Performance Ideal Lattice-Based Cryptography on 8-Bit AVR Microcontrollers[J]. ACM Transactions on Embedded Computing Systems (TECS), 2017, 16(4): 1-24.
[4]	ZHANG Neng, YANG Bohan, CHEN Chen, et al. Highly Efficient Architecture of New Hope-NIST on FPGA Using Low-Complexity NTT/INTT[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020(2): 49-72.
[5]	CHEN D D, MENTENS N, VERCAUTEREN F, et al. High-Speed Polynomial Multiplication Architecture for Ring-LWE and SHE Cryptosystems[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2014, 62(1): 157-166.
[6]	REISIS D, VLASSOPOULOS N. Conflict-Free Parallel Memory Accessing Techniques for FFT Architectures[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2008, 55(11): 3438-3447.
[7]	MERT A C, ÖZTÜRK E, SAVAŞ E. Design and Implementation of a Fast and Scalable NTT-Based Polynomial Multiplier Architecture[C]// IEEE. 2019 22nd Euromicro Conference on Digital System Design (DSD). New York: IEEE, 2019: 253-260.
[8]	CHEN Xiangren, YANG Bohan, YIN Shouyi, et al. CFNTT: Scalable Radix-2/4 NTT Multiplication Architecture with An Efficient Conflict-Free Memory Mapping Scheme[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(1): 94-126.
[9]	KIM D W, MAULANA D I, JUNG W. Kyber Accelerator on FPGA Using Energy-Efficient LUT-Based Barrett Reduction[C]// IEEE.19th International SoC Conference (ISOCC 2022). New York: IEEE, 2022: 83-84.
[10]	ZHAO Cankun, ZHANG Neng, WANG Hanning, et al. A Compact and High-Performance Hardware Architecture for Crystals-Dilithium[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(1): 270-295.
[11]	NGUYEN D T, DANG V B, GAJ K. High-Level Synthesis in Implementing and Benchmarking Number Theoretic Transform in Lattice-Based Post-Quantum Cryptography Using Software/Hardware Codesign[C]// Springer. Applied Reconfigurable Computing. Architectures, Tools, and Applications:16th International Symposium (ARC 2020). Heidelberg: Springer, 2020: 247-257.
[12]	LONGA P, NAEHRIG M. Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography[C]// Springer.Cryptology and Network Security:15th International Conference (CANS 2016). Heidelberg: Springer, 2016: 124-139.
[13]	YE Zewen, CHEUNG R C C, HUANG Kejie. PipeNTT: A Pipelined Number Theoretic Transform Architecture[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2022, 69(10): 4068-4072.
[14]	DERYA K, MERT A C, ÖZTÜRK E, et al. CoHA-NTT: A Configurable Hardware Accelerator for NTT-Based Polynomial Multiplication[EB/OL]. [2024-02-20]. https://www.xueshufan.com/publication/3216016201.
[15]	BISHEH-NIASAR M, AZARDERAKHSH R, MOZAFFARI-KERMANI M. Instruction-Set Accelerated Implementation of CRYSTALS-Kyber[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2021, 68(11): 4648-4659.
[16]	YAMAN F, MERT A C, ÖZTÜRK E, et al. A Hardware Accelerator for Polynomial Multiplication Operation of CRYSTALS-KYBER PQC Scheme[C]// IEEE. 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE). New York: IEEE, 2021: 1020-1025.
[17]	MAO Gaoyu, CHEN Donglong, LI Guangyan, et al. High-Performance and Configurable SW/HW Co-Design of Post-Quantum Signature CRYSTALS-Dilithium[J]. ACM Transactions on Reconfigurable Technology and Systems, 2023, 16(3): 1-28.
[18]	ZHOU Zhen, HE Debiao, LIU Zhe, et al. A Software/Hardware Co-Design of Crystals-Dilithium Signature Scheme[J]. ACM Transactions on Reconfigurable Technology and Systems (TRETS), 2021, 14(2): 1-21.

方案	本文	巴雷特约简算法	蒙哥马利算法
器件	Artix-7	Artix-7	Artix-7
LUT数量/个	1060	1193（1.1×）	3715（3.5×）
FF数量/个	231	922（4.0×）	552（2.4×）

模式	Kyber
方案	本文	文献[14]	文献[15]	文献[16]
器件	Artix-7	Virtex-7	Artix-7	Artix-7
BFU数量/个	4	1	1	4
LUT数量/个	5412	2128	360	2543
FF数量/个	1435	1144	145	792
DSP数量/个	0	8	3	4
BRAM总量/个	4.5	3	2	9
频率/MHz	260	174	115	182
执行时间/μs	0.5	5.2	8.1	1.2
面积/10^-3	6.7	3.8	1.3	3.1
ATP	3.4	19.8	10.5	3.7

模式	Dilithum
方案	本文	文献[14]	文献[17]	文献[18]
器件	Artix-7	Artix-7	Zynq 7000	Artix-7
BFU数量/个	4	1	1	1
LUT数量/个	5412	2119	799	2044
FF数量/个	1435	1058	971	—
DSP数量/个	0	8	2	16
BRAM总量/个	4.5	3	4.5	6
频率/MHz	260	117	172	216
执行时间/μs	1.1	8.9	8.1	5.4
面积/10^-3	6.7	3.8	2.3	5.4
ATP	7.4	33.8	18.6	29.1