Hardware Design and Implementation of Number Theoretic Transform in Post-Quantum Cryptography

doi:10.3969/j.issn.1671-1122.2023.04.008

Abstract

Abstract:

Number theoretic transform (NTT) is a key component of post-quantum cryptography algorithms, and its computing performance is critical to the running speed of the system. Compared with the classical NTT algorithm, the high-radix NTT algorithm can achieve better computational performance. In order to solve the problems of lengthy computing flow and complex control logic in the hardware implementation of high-radix NTT, this paper proposed a high-performance radix-4 NTT hardware architecture based on pipeline structure. Firstly, based on the classical NTT algorithm, a radix-4 recursive NTT was derived to facilitate hardware implementation, which simplified the computing flow of the high-radix algorithm. Secondly, a single-path delay feedback structure was presented to effectively pipeline the algorithm flow and reduced the complexity of the hardware architecture. Finally, the radix-4 butterfly unit was realized by coupling two-stage butterfly operations, and the reduction was optimized by using shift operations and additions, which could reduce the overhead of hardware resources. Taking the post-quantum cryptography algorithm falcon as an example, the proposed NTT hardware architecture has been implemented on Xilinx Artix-7 FPGA. The experimental results show that the proposed design has good performance in computing speed and hardware resources overhead compared to the related designs.

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

CLC Number:

TP309

XIAO Hao, ZHAO Yanrui, HU Yue, LIU Xiaofan. Hardware Design and Implementation of Number Theoretic Transform in Post-Quantum Cryptography[J]. Netinfo Security, 2023, 23(4): 72-79.

Figures/Tables 7

References 30

[1]	SHOR P W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J]. SIAM Review, 1999, 41(2): 303-332. doi: 10.1137/S0036144598347011 URL
[2]	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.
[3]	LIU Zhe, SEO H, ROY S, et al. Efficient Ring-LWE Encryption on 8-Bit AVR Processors[C]// Springer. 17th International Workshop on Cryptographic Hardware and Embedded Systems. Heidelberg: Spring, 2015: 663-682.
[4]	YANG Yingshan, GU Xiaozhuo, WANG Bin, et al. Efficient Password-Authenticated Key Exchange from RLWE Based on Asymmetric Key Consensus[C]// Springer. 15th International Conference on Information Security and Cryptology. Heidelberg: Spring, 2019: 31-49.
[5]	Shanghai Jiaotong University. Shanghai Jiaotong University Gu Dawu Team Achieves Breaking the LWE Challenge World Record[EB/OL]. (2022-03-10)[2022-10-13]. http://netinfo-security.org/CN/Y2022/V22/I3/100.
	上海交通大学. 网安学院谷大武团队成果打破格密码LWE Challenge的世界纪录[EB/OL]. (2022-02-24)[2022-10-13]. https://infosec.sjtu.edu.cn/NewsDetail.aspx?id=208.
[6]	ZHANG He, WANG Peng, LI Sizhao. Research on Lattice-Based Post-Quantum Cryptosystem[J]. Radio Engineering, 2022, 52(8): 1310-1321.
	张贺, 王鹏, 李思照. 基于格的后量子密码系统研究[J]. 无线电工程, 2022, 52(8):1310-1321.
[7]	ALAGIC G, ALPERIN-SHERIFF J, APON D, et al. Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process[R]. Gaithersburg: NIST, NISTIR 8309, 2020.
[8]	YIN Yanzhao, WU Liji, ZHANG Xiangmin, et al. Method to Construct Extension Field for NTT of Polynomial Multiplication with Small Modulus[J]. Journal of Cryptologic Research. 2021, 8(2): 260-272. doi: 10.13868/j.cnki.jcr.000435
	殷彦昭, 乌力吉, 张向民, 等. 一种用于小模数多项式乘法快速数论变换的扩域方法[J]. 密码学报, 2021, 8(2):260-272. doi: 10.13868/j.cnki.jcr.000435
[9]	XIE Xing, HUANG Xinming, SUN Ling, et al. FPGA Design and Implementation of Large Integer Multiplier[J]. Journal of Electronics & Information Technology, 2019, 41(8): 1855-1860.
	谢星, 黄新明, 孙玲, 等. 大整数乘法器的FPGA设计与实现[J]. 电子与信息学报, 2019, 41(8):1855-1860.
[10]	BANERJEE U, PATHAK A, CHANDRAKASAN A P. 2.3 An Energy-Efficient Configurable Lattice Cryptography Processor for the Quantum-Secure Internet of Things[C]// IEEE. 2019 IEEE International Solid-State Circuits Conference(ISSCC). New York: IEEE, 2019: 46-48.
[11]	RIAZI M S, LAINE K, PELTON B, et al. HEAX: An Architecture for Computing on Encrypted Data[C]// ACM. Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2020: 1295-1309.
[12]	XIE Xing, SUN Ling, HUANG Xinming, et al. Design and Implementation of Finite Field NTT Algorithm Based on FPGA[J]. Modern Electronics Technique, 2020, 43(9): 79-82.
	谢星, 孙玲, 黄新明, 等. 基于FPGA的有限域NTT算法设计与实现[J]. 现代电子技术, 2020, 43(9):79-82.
[13]	PALUDO R, SOUSA L. Number Theoretic Transform Architecture Suitable to Lattice-Based Fully-Homomorphic Encryption[C]// IEEE. 2021 IEEE 32nd International Conference on Application-Specific Systems, Architectures and Processors (ASAP). New York: IEEE, 2021: 163-170.
[14]	ZHANG Ye, WANG Shuo, ZHANG Xian, et al. Pipezk: Accelerating Zero-Knowledge Proof with a Pipelined Architecture[C]// IEEE. 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA). New York: IEEE, 2021: 416-428.
[15]	HUA Siliang, ZHANG Huiguo, WANG Shuchang. Optimization and Implementation of Number Theoretical Transform Multiplier Butterfly Operation for Fully Homomorphic Encryption[J]. Journal of Electronics & Information Technology, 2021, 43(5): 1381-1388.
	华斯亮, 张惠国, 王书昶. 用于全同态加密的数论变换乘法蝶形运算优化及实现[J]. 电子与信息学报, 2021, 43(5):1381-1388.
[16]	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. doi: 10.1109/TCSII.2022.3184703 URL
[17]	RENTERIA-MEJIA C P, VELASCO-MEDINA J. Hardware Design of an NTT-Based Polynomial Multiplier[C]// IEEE. 2014 IX Southern Conference on Programmable Logic (SPL). New York: IEEE, 2014: 1-5.
[18]	WEI Xing, HUANG Zhihong, YANG Haigang. High Throughput Dual-Mode Reconfigurable Floating-Point FFT Processor[J]. Journal of Electronics & Information Technology, 2018, 40(12): 3042-3050.
	魏星, 黄志洪, 杨海钢. 高吞吐率双模浮点可重构FFT处理器设计实现[J]. 电子与信息学报, 2018, 40(12):3042-3050.
[19]	WANG Wei, HUANG Xinming, EMMART N, et al. VLSI Design of a Large-Number Multiplier for Fully Homomorphic Encryption[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2013, 22(9): 1879-1887. doi: 10.1109/TVLSI.2013.2281786 URL
[20]	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: 94-126.
[21]	NGUYEN D T, DANG V B, GAJ K. A High-Level Synthesis Approach to the Software/Hardware Codesign of NTT-Based Post-Quantum Cryptography Algorithms[C]// IEEE. 2019 International Conference on Field-Programmable Technology (ICFPT). New York: IEEE, 2019: 371-374.
[22]	BANERJEE U, UKYAB T S, CHANDRAKASAN A P. Sapphire: A Configurable Crypto-Processor for Post-Quantum Lattice-Based Protocols[EB/OL]. (2019-10-16)[2022-10-13]. https://arxiv.org/abs/1910.07557.
[23]	XIAO Hao, YU Sijia, CHENG Biqian, et al. FPGA-Based High-Throughput Montgomery Modular Multipliers for RSA Cryptosystems[J]. IEICE Electronics Express, 2022, 68(6): 2137-2141.
[24]	CHE Wenjie, GAO Xianwei. FPGA Design and Implementation of the Carry-Save Barrett Modular Multiplication[J]. Electronic Design Engineering, 2016, 24(4): 7-9.
	车文洁, 高献伟. 基于FPGA的进位保留 Barrett 模乘法器设计与实现[J]. 电子设计工程, 2016, 24(4):7-9.
[25]	HARVEY D. Faster Arithmetic for Number-Theoretic Transforms[J]. Journal of Symbolic Computation, 2014(60): 113-119.
[26]	XIAO Hao. Research and Design of Multimode Fast Fourier Transform (FFT) Accelerators in Baseband Processors[D]. Shanghai: Fudan University, 2009.
	肖昊. 基带处理器中多模快速傅里叶变换(FFT)加速器的研究与设计[D]. 上海: 复旦大学, 2009.
[27]	CLAUDIA P R M, VELASCO M J. High-Throughput Ring-LWE Cryptoprocessors[J]. IEEE Transactions on Very Large Scale Integration Systems, 2017, 25(8): 2332-2345. doi: 10.1109/TVLSI.92 URL
[28]	YE J H, SHIEH M D. High-Performance NTT Architecture for Large Integer Multiplication[C]// IEEE. 2018 International Symposium on VLSI Design, Automation and Test (VLSI-DAT). New York: IEEE, 2018: 1-4.
[29]	MERT A C, KARABULUT E, OZTURK E, et al. An Extensive Study of Flexible Design Methods for the Number Theoretic Transform[EB/OL]. (2020-08-19)[2022-10-13]. https://www.researchgate.net/publication/343753706_An_Extensive_Study_of_Flexible_Design_Methods_for_the_Number_Theoretic_Transform.
[30]	XING Yufei, LI Shuguo. An Efficient Implementation of the New Hope Key Exchange on FPGAs[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2019, 67(3): 866-878. doi: 10.1109/TCSI.8919 URL

	基-2 NTT	基-4 NTT
BFU数量	${{\log }_{2}}n$	${{\log }_{4}}n$
乘法器	${{\log }_{2}}n-1$	${{\log }_{4}}n-1$
常系数乘法器	0	${{\log }_{4}}n$
乘法约简单元	${{\log }_{2}}n-1$	${{\log }_{2}}n-1$

方案	实现平台	时序参数			资源开销		ATP1	ATP2
		频率/MHz	周期	平均时间/μs	LUT	DSP	ATP1	ATP2
		点数n=1024，模数q=12289，位宽14 bit
文献[20]方案	Artix-7	213	1308	6.1	1161	12	7082.1	73.2
文献[21]方案	Zynq-7000	188	2032	10.8	898	4	9698.4	43.2
文献[29]方案	Artix-7	200	1445	7.2	1839	12	13240.8	86.4
文献[30]方案	Zynq-7000	152	1280	8.4	4823	8	40513.2	67.2
本文方案	Artix-7	227	2475	4.6	2829	4	13013.4	18.4