后量子密码CRYSTALS-Kyber的FPGA多路并行优化实现

doi:10.11959/j.issn.1000-436x.2022026

通信学报 ›› 2022, Vol. 43 ›› Issue (2): 196-207.doi: 10.11959/j.issn.1000-436x.2022026

后量子密码CRYSTALS-Kyber的FPGA多路并行优化实现

李斌¹, 陈晓杰², 冯峰¹, 周清雷¹

¹ 郑州大学计算机与人工智能学院，河南郑州 450001
² 信息工程大学数学工程与先进计算国家重点实验室，河南郑州 450001

修回日期:2022-01-10 出版日期:2022-02-25 发布日期:2022-02-01
作者简介:李斌（1986-），男，河南郑州人，博士，郑州大学讲师，主要研究方向为信息安全、可重构计算
陈晓杰（1993-），男，河南武陟人，信息工程大学博士生，主要研究方向为信息安全、可重构计算
冯峰（1990-），男，河南新乡人，郑州大学博士生，主要研究方向为信息安全
周清雷（1962-），男，河南新乡人，博士，郑州大学教授，主要研究方向为信息安全、自动机理论和计算复杂性理论
基金资助:
国家重点研发计划基金资助项目(2016YFB0800100);国家重点研发计划基金资助项目(2016YFB0800101);国家自然科学基金资助项目(61572444)

FPGA multi-unit parallel optimization and implementation of post-quantum cryptography CRYSTALS-Kyber

Bin LI¹, Xiaojie CHEN², Feng FENG¹, Qinglei ZHOU¹

¹ School of Computer and Artificial Intelligence, Zhengzhou University, Zhengzhou 450001, China
² State Key Laboratory of Mathematical Engineering and Advanced Computing, Information Engineering University, Zhengzhou 450001, China

Revised:2022-01-10 Online:2022-02-25 Published:2022-02-01
Supported by:
The National Key Research and Development Program of China(2016YFB0800100);The National Key Research and Development Program of China(2016YFB0800101);The National Natural Science Foundation of China(61572444)

摘要/Abstract

摘要：

在基于格的后量子密码中，多项式乘法运算复杂且耗时，为提高格密码在实际应用中的运算效率，提出了一种后量子密码CRYSTALS-Kyber的FPGA多路并行优化实现。首先，描述了Kyber算法的流程，分析了NTT、INTT及CWM的执行情况。其次，给出了FPGA的整体结构，采用流水线技术设计了蝶形运算单元，并以Barrett模约简和CWM调度优化，提高了计算效率。同时，放置32个蝶形运算单元并行执行，缩短了整体计算周期。最后，对多RAM通道进行了存储优化，以数据的交替存取控制和RAM资源复用，提高了访存效率。此外，采用松耦合架构，以DMA通信实现了整体运算的调度。实验结果和分析表明，所提方案可在44、49、163个时钟周期内完成NTT、INTT及CWM运算，优于其他方案，具有较高的能效比。

关键词: 后量子密码, CRYSTALS-Kyber, 现场可编程门阵列, 数论变换, 多项式乘法, 蝶形运算

Abstract:

In lattice-based post-quantum cryptography, polynomial multiplication is complicated and time-consuming.In order to improve the computational efficiency of lattice cryptography in practical applications, an FPGA multi-unit parallel optimization and implementation of post-quantum cryptography CRYSTALS-Kyber was proposed.Firstly, the flow of Kyber algorithm was described and the execution of NTT, INTT and CWM were analyzed.Secondly, the overall structure of FPGA was given, the butterfly arithmetic unit was designed by pipeline technology, and the Barrett modulus reduction and CWM scheduling optimization were used to improve the calculation efficiency.At the same time, 32 butterfly arithmetic units were executed in parallel, which shortens the overall calculation cycle.Finally, the multi-RAM channel was optimized to improve the memory access efficiency with alternate data access control and RAM resource reuse.In addition, with the loosely coupled architecture, the overall operation scheduling was realized by DMA communication.The experimental results and analysis show that the proposed scheme implemented can complete NTT, INTT and CWM operations within 44, 49, and 163 clock cycles, which is superior to other schemes and has high energy efficiency ratio.

Key words: post-quantum cryptography, CRYSTALS-Kyber, FPGA, NTT, polynomial multiplication, butterfly arithmetic

中图分类号:

TP309

李斌, 陈晓杰, 冯峰, 周清雷. 后量子密码CRYSTALS-Kyber的FPGA多路并行优化实现[J]. 通信学报, 2022, 43(2): 196-207.

Bin LI, Xiaojie CHEN, Feng FENG, Qinglei ZHOU. FPGA multi-unit parallel optimization and implementation of post-quantum cryptography CRYSTALS-Kyber[J]. Journal on Communications, 2022, 43(2): 196-207.

图/表 17

表1

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

表2

表3

表4

参考文献 23

[1]	DANG V , FARAHMAND F , ANDRZEJCZAK M ,et al. Implementation and benchmarking of round 2 candidates in the NIST post-quantum cryptography standardization process using hardware and software/hardware co-design approaches[J]. IACR Cryptol EPrint Arch,2020, 2020:795.
[2]	AVANZI R , BOS J , DUCAS L ,et al. CRYSTALS-Kyber[R]. 2017.
[3]	LYUBASHEVSKY V , SEILER G . NTTRU:truly fast NTRU using NTT[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019,2019(3): 180-201.
[4]	ZHANG N , QIN Q , YUAN H ,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.
[5]	YAMAN F , MERT A C , ?ZTüRK E ,et al. A hardware accelerator for polynomial multiplication operation of CRYSTALS-Kyber PQC scheme[C]// Proceedings of 2021 Design,Automation ＆ Test in Europe Conference ＆ Exhibition (DATE). Piscataway:IEEE Press, 2021: 1020-1025.
[6]	HUANG Y M , HUANG M Q , LEI Z K ,et al. A pure hardware implementation of CRYSTALS-KYBER PQC algorithm through resource reuse[J]. IEICE Electronics Express, 2020,17(17): 1-6.
[7]	MERT A C , KARABULUT E , OZTURK E ,et al. An extensive study of flexible design methods for the number theoretic transform[J]. IEEE Transactions on Computers, 2020:doi.org/10.1109/TC.2020.3017930.
[8]	MERT A C , ?ZTüRK E , SAVA? E . Design and implementation of a fast and scalable NTT-based polynomial multiplier architecture[C]// Proceedings of 2019 22nd Euromicro Conference on Digital System Design (DSD). Piscataway:IEEE Press, 2019: 253-260.
[9]	XING Y F , LI S G . A compact hardware implementation of CCA-secure key exchange mechanism CRYSTALS-Kyber on FPGA[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021,2021(2): 328-356.
[10]	RICCI S , JEDLICKA P , CIBIK P ,et al. Towards CRYSTALS-Kyber VHDL implementation[C]// Proceedings of the 18th International Conference on Security and Cryptography.[S.l. ]:Science and Technology Publications, 2021: 760-765.
[11]	RICCI S , MALINA L , JEDLICKA P ,et al. Implementing CRYSTALS-dilithium signature scheme on FPGAs[C]// Proceedings of 16th International Conference on Availability,Reliability and Security. New York:ACM Press, 2021: 1-11.
[12]	CHEN Z H , MA Y , CHEN T Y ,et al. Towards efficient kyber on FPGAs:a processor for vector of polynomials[C]// Proceedings of 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC). Piscataway:IEEE Press, 2020: 247-252.
[13]	SEILER G . Faster AVX2 optimized NTT multiplication for ring-LWE lattice cryptography[J]. IACR Cryptology EPrint Archive,2018, 2018:39.
[14]	ZIJLSTRA T , BIGOU K , TISSERAND A . Lattice-based cryptosystems on FPGA:parallelization and comparison using HLS[J]. IEEE Transactions on Computers, 2021:doi.org/10.1109/TC.2021.3112052.
[15]	BASU K , SONI D , NABEEL M ,et al. NIST post-quantum cryptography-a hardware evaluation study[R]. 2019.
[16]	AGRAWAL R , BU L K , EHRET A ,et al. Open-source FPGA implementation of post-quantum cryptographic hardware primitives[C]// Proceedings of 2019 29th International Conference on Field Programmable Logic and Applications (FPL). Piscataway:IEEE Press, 2019: 211-217.
[17]	BISHEH-NIASAR M , AZARDERAKHSH R , MOZAFFARI-KERMANI M . High-speed NTT-based polynomial multiplication accelerator for post-quantum cryptography[C]// Proceedings of 2021 IEEE 28th Symposium on Computer Arithmetic (ARITH). Piscataway:IEEE Press, 2021: 94-101.
[18]	FRITZMANN T , SIGL G , SEPúLVEDA J . RISQ-V:tightly coupled RISC-V accelerators for post-quantum cryptography[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020: 239-280.
[19]	陈朝晖, 马原, 荆继武 . 格密码关键运算模块的硬件实现优化与评估[J]. 北京大学学报(自然科学版), 2021,57(4): 595-604.
	CHEN Z H , MA Y , JING J W . Hardware optimization and evaluation for crucial modules of lattice-based cryptography[J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2021,57(4): 595-604.
[20]	刘冬生, 赵文定, 刘子龙 ,等. 应用于格密码的可重构多通道数论变换硬件设计[J]. 电子与信息学报, 2021:doi.org/10.11999/ JEIT210114.
	LIU D S , ZHAO W D , LIU Z L ,et al. Reconfigurable hardware design of multi-lanes number theoretic transform for lattice-based cryptography[J]. Journal of Electronics ＆ Information Technology, 2021:doi.org/10.11999/ JEIT210114.
[21]	华斯亮, 张惠国, 王书昶 . 用于全同态加密的数论变换乘法蝶形运算优化及实现[J]. 电子与信息学报, 2021,43(5): 1381-1388.
	HUA S L , ZHANG H G , WANG S C . 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.
[22]	沈诗羽, 何峰, 赵运磊 . Aigis密钥封装算法多平台高效实现与优化[J]. 计算机研究与发展, 2021,58(10): 2238-2252.
	SHEN S Y , HE F , ZHAO Y L . Multi-platform efficient implementation and optimization of aigis-enc algorithm[J]. Journal of Computer Research and Development, 2021,58(10): 2238-2252.
[23]	ZHANG N , YANG B H , CHEN C ,et al. Highly efficient architecture of NewHope-NIST on FPGA using low-complexity NTT/INTT[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020,2020(2): 49-72.

算法	安全等级	n	k	q
Kyber512	1	256	2	3 329
Kyber768	2	256	3	3 329
Kyber1024	3	256	4	3 329

模块	实现方式	LUT/个	FF/个	BRAM/个	DSP/个
蝶形运算单元	流水线	235	108	0	1
控制单元	串行	5 642	159	0	0
多RAM通道	并行	0	0	64	0
ROM存储	串行	0	0	5	0
Kyber算法	串并混合	14 634	5710	69	32

模块	频率/MHz	计算周期	性能/(p·s^-1)	能效比/(p·J^-1)
NTT	175	44	3 977 273	3 655 582
INTT	175	49	3 571 429	3 282 563
CWM	175	163	1 073 620	986 783

方案	器件	NTT周期	频率/MHz	LUT/个	FF/个	DSP/个	BRAM/个	时间/μs	AT
文献[5]	Artix-7	69	172	9 508	2 684	16	35	0.40	3 803
文献[9]	Artix-7	512	161	1 737	1 167	2	3	3.18	5 524
文献[10]	UltraScale+ XCVU7P	405	637	1 107	1 407	28	3.5	0.64	708
文献[12]	Artix-7	2 055	136	442	237	1	1.5	15.11	6 679
文献[17]	Artix-7	324	222	801	717	4	2	1.46	1 169
本文方案	Zynq-7035	44	175	8 428	3 979	32	11	0.25	2 107

后量子密码CRYSTALS-Kyber的FPGA多路并行优化实现

FPGA multi-unit parallel optimization and implementation of post-quantum cryptography CRYSTALS-Kyber

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 17

参考文献 23

相关文章 5

Metrics

推荐阅读 0

[1]	张琪琪,张建国,李璞,郭龑强,王云才. 基于布尔混沌的物理随机数发生器[J]. 通信学报, 2019, 40(1): 201-206.
[2]	王哲,梁满贵,及晓萌. 源端控制的OpenFlow数据面[J]. 通信学报, 2015, 36(3): 195-201.
[3]	古春生. 破解HFEM公钥密码方案[J]. 通信学报, 2013, 34(3): 85-89.
[4]	赵永哲,赵博,裴士辉,姜占华. HFEM公钥密码方案的设计与实现[J]. 通信学报, 2011, 32(6): 24-31.
[5]	乔庐峰,王志功,陆园琳,黄斌. 128用户PCI桥接器的数据结构设计与性能分析[J]. 通信学报, 2005, 26(1): 74-79.