Reconfigurable Hardware Design of Multi-lanes Number Theoretic Transform for Lattice-based Cryptography

LIU Dongsheng; ZHAO Wending; LIU Zilong; ZHANG Cong; LIU Xingjie

doi:10.11999/JEIT210114

Volume 44 Issue 2

Feb. 2022

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2022 > 44(2): 566-572

LIU Dongsheng, ZHAO Wending, LIU Zilong, ZHANG Cong, LIU Xingjie. Reconfigurable Hardware Design of Multi-lanes Number Theoretic Transform for Lattice-based Cryptography[J]. Journal of Electronics & Information Technology, 2022, 44(2): 566-572. doi: 10.11999/JEIT210114

Citation:

LIU Dongsheng, ZHAO Wending, LIU Zilong, ZHANG Cong, LIU Xingjie. Reconfigurable Hardware Design of Multi-lanes Number Theoretic Transform for Lattice-based Cryptography[J]. Journal of Electronics & Information Technology, 2022, 44(2): 566-572. doi: 10.11999/JEIT210114

Citation:

LIU Dongsheng, ZHAO Wending, LIU Zilong, ZHANG Cong, LIU Xingjie. Reconfigurable Hardware Design of Multi-lanes Number Theoretic Transform for Lattice-based Cryptography[J]. Journal of Electronics & Information Technology, 2022, 44(2): 566-572. doi: 10.11999/JEIT210114

PDF( 1833 KB)

Reconfigurable Hardware Design of Multi-lanes Number Theoretic Transform for Lattice-based Cryptography

doi: 10.11999/JEIT210114

School of Optical and Electronic Information, Huazhong University of Science and Technology, Wuhan 430074, China

Funds: The National Natural Science Foundation of China (61874163), The National Science and Technology Major Project (2017ZX01032-101), The Fundamental Research Funds for the Central Universities (HUST: 2018KFYYXJJ056)

Received Date: 2021-02-01
Rev Recd Date: 2021-06-10

Available Online: 2021-06-22

Publish Date: 2022-02-25

Abstract

Abstract

The performance of number theoretic transformation in lattice-based cryptography is insufficient, and the number theoretic transformation parameters are different. A Random Access Memory (RAM)-based reconfigurable multi-lanes number theoretic transform is proposed. In the design of number theory transformation unit, the multi-lanes architecture is improved on the time decimation operation architecture, and an optimized address allocation method is proposed. The number theory transform unit is implemented on Xilinx artix-7 Field Programmable Gate Array (FPGA) platform. The results show that the resource consumed by the unit is 1744 slices and 16 DSP, and the time to complete a polynomial multiplication is 2.01 μs (n=256), 3.57 μs (n=512), 6.71 μs (n=1024) and 13.43 μs (n=2048). The unit supports reconfigurable configurations of 256～2048 parameters n and 13～32-bit modulus q, and the maximum operating frequency is 232 MHz.
- Lattice-based cryptography,
- Polynomial multiplication,
- Number theoretic transform,
- Hardware implementation

FullText(HTML)

References(15)

References

[1]	SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484–1509. doi: 10.1137/S0097539795293172
[2]	ARUTE F, ARYA K, BABBUSH R, et al. Quantum supremacy using a programmable superconducting processor[J]. Nature, 2019, 574(7779): 505–510. doi: 10.1038/s41586-019-1666-5
[3]	赵勇, 戚巍, 徐兵杰, 等. 量子安全技术白皮书(2020)[R]. 2020.
[4]	CHEN Zhaohui, MA Yuan, CHEN Tianyu, et al. Towards efficient kyber on FPGAs: A processor for vector of polynomials[C]. The 2020 25th Asia and South Pacific Design Automation Conference, Beijing, China, 2020. doi: 10.1109/ASP-DAC47756.2020.9045459.
[5]	PÖPPELMANN T and GÜNEYSU T. Towards efﬁcient arithmetic for lattice-based cryptography on reconﬁgurable hardware[C]. The 2nd International Conference on Cryptology and Information Security in Latin America, Santiago, Chile, 2012. doi: 10.1007/978-3-642-33481-8_8" target="_blank">href="http://dx.doi.org/10.1007/978-3-642-33481-8_8">10.1007/978-3-642-33481-8_8.
[6]	RENTERÍA-MEJÍA C P and VELASCO-MEDINA J. Hardware design of an NTT-Based polynomial multiplier[C]. The 2014 IX Southern Conference on Programmable Logic, Buenos Aires, Argentina, 2014: 1–5. doi: 10.1109/SPL.2014.7002209.
[7]	YE J H and SHIEH M D. High-performance NTT Architecture for large integer multiplication[C]. 2018 International Symposium on VLSI Design, Automation and Test, Hsinchu, China, 2018: 1–4. doi: 10.1109/VLSI-DAT.2018.8373254.
[8]	ZHANG Neng, QIN Qiao, YUAN Hang, et al. NTTU: An area-efficient low-power NTT-uncoupled architecture for NTT-based multiplication[J]. IEEE Transactions on Computers, 2020, 69(4): 520–533. doi: 10.1109/TC.2019.2958334
[9]	AYSU A, PATTERSON C, and SCHAUMONT P. Low-cost and area-efficient FPGA implementations of lattice-based cryptography[C]. Proceedings of 2013 IEEE International Symposium on Hardware-Oriented Security and Trust, Austin, USA, 2013.
[10]	RENTERÍA-MEJÍA C R and VELASCO-MEDINA J. Lattice-based cryptoprocessor for CCA-Secure identity-based encryption[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2020, 67(7): 2331–2344. doi: 10.1109/TCSI.2020.2981089
[11]	FENG Xiang, LI Shuguo, and XU Sufen. RLWE-oriented high-speed polynomial multiplier utilizing multi-lane stockham NTT algorithm[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2020, 67(3): 556–559. doi: 10.1109/TCSII.2019.2917621
[12]	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, 2015, 62(1): 157–166. doi: 10.1109/TCSI.2014.2350431
[13]	MERT A C, KARABULUT E, OZTURK E, et al. An extensive study of flexible design methods for the number theoretic transform[J/OL]. IEEE Transactions on Computers, 2020, 1–15.
[14]	LIU Dongsheng, ZHANG Cong, LIN Hui, et al. A resource-efficient and side-channel secure hardware implementation of ring-LWE cryptographic processor[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2019, 66(4): 1474–1483. doi: 10.1109/TCSI.2018.2883966
[15]	KIM S, LEE K, CHO W, et al. Hardware architecture of a number theoretic transform for a bootstrappable RNS-based homomorphic encryption scheme[C]. The 2020 IEEE 28th Annual International Symposium on Field-Programmable Custom Computing Machines, Fayetteville, USA, 2020, 56–64. doi: 10.1109/FCCM48280.2020.00017.