面向Saber算法的并行乘法器
PDF下载 (450)吕 杰,汪鹏君,张会红.面向Saber算法的并行乘法器[J].宁波大学学报(理工版),2022,35(6):15-21.DOI:
L? Jie,WANG Pengjun,ZHANG Huihong.Design of parallel multiplier for Saber[J].Journal of Ningbo University(Natural Science & Engineering Edition),2022,35(6):15-21.DOI:
| Title: | Design of parallel multiplier for Saber |
| 作者: | 吕 杰, 汪鹏君, 张会红 |
| Author(s): | L? Jie, WANG Pengjun, ZHANG Huihong |
| 关键词: | 后量子密码; Saber算法; Karatsuba算法; Schoolbook相乘方式; 并行乘法器 |
| Keywords: | post-quantum cryptography; Saber algorithm; Karatsuba algorithm; Schoolbook multiplication method; parallel multiplier |
| 分类号: | TP391 |
| 文献标识码: | A |
| 摘要: | 随着量子计算的发展, 现有密码系统的安全性将受到严重威胁. Saber算法是抵御量子计算攻击的后量子密码方案之一, 但存在多项式商环上模乘占据运算开销过大的问题. 鉴此, 本文通过对Karatsuba算法和Schoolbook相乘方式的剖析, 提出一种面向Saber算法的并行乘法器设计方案. 该方案首先利用Karatsuba算法分解模乘运算的关键路径, 结合乘法复用和加法替换的策略减少硬件开销, 然后采用并行运算电路压缩关键运算路径时长, 最后在TSMC 65nm工艺下, 利用Modelsim和DC软件仿真验证. 结果表明 该方案运算时长为137个时钟周期, 与传统方式相比速度提升46.50%, 功耗为87.83mW, 面积为927.32×103 ?m2. |
| Abstract: | With the development of the quantum computer, the security of modern cryptosystems will be placed under threat. In defending against quantum computing attacks, Saber algorithm becomes one of the schemes in the ongoing post-quantum cryptography standardization project. The bottleneck of Saber is multiplication in polynomial quotient rings, where the multiplication occupies high costs in computation operation. In this paper, a parallel multiplier for Saber is proposed, which is based on analysis of Karatsuba and Schoolbook. Firstly, disassembling the calculated path of polynomial modulo multiplication is carried out by the Karatsuba algorithm, whereby a strategy of combining multiplication reused with addition superseding multiplication is utilized to reduce hardware overhead. Secondly, the critical path is compressed by a parallel structure. Finally, in the TSMC 65nm process, analysis is conducted using the tools of Modelsim and DC. The results indicate that the designed scheme accomplishes 137 clock cycles’ critical path of an operation, improving 46.5% in speed performance as compared with the conventional method, the power consumption is 87.83mW and the area overhead is 927.32×103 ?m2. |
| 参考文献 /References: | [1] 刘冬生, 赵文定, 刘子龙, 等. 应用于格密码的可重构多通道数论变换硬件设计[J]. 电子与信息学报, 2022, 44(2):566-572. [2] Bernstein D J, Lange T. Post-quantum cryptography[J]. Nature, 2017, 549(7671):188-194. [3] Shor P W. Algorithms for quantum computation: Discrete logarithms and factoring[C]//Proceedings 35th Annual Symposium on Foundations of Computer Science. Santa Fe, NM, USA. IEEE, 1994:124-134. [4] Grover L K. A fast quantum mechanical algorithm for database search[C]//STOC ’96: Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing. 1996:212-219. [5] Basso A, Mera J M B, D’Anvers J P, et al. Saber: Mod-LWR based Kem (Round 3 Submission to NIST PQC)[R]. 2020. [6] Basso A, Roy S S. Optimized polynomial multiplier architectures for post-quantum KEM Saber[C]//2021 58th ACM/IEEE Design Automation Conference (DAC), 2021:1285-1290. [7] D’Anvers J P, Karmakar A, Vercauteren F, et al. Saber: module-LWR based key exchange, CPA-secure encryption and CCA-secure kem[C]//2018 International Conference on Cryptology in Africa (AFRICACRYPT), 2018:282-305. [8] Wang B, Gu X Z, Yang Y S. Saber on ESP32[C]//2020 18th International Conference on Applied Cryptography and Network Security (ACNS), 2020:421-440. [9] Paksoy I K, Murat C. TMVP-based multiplication for polynomial quotient rings and application to Saber on arm cortex-m4[J]. IACR Cryptology Eprint Archive, 2020, 2020:1302-1323. [10] Bermudo M J M, Karmakar A, Verbauwhede I. Time-memory trade-off in Toom-Cook multiplication: An application to module-lattice based cryptography[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020, 2020(2):222-244. [11] Maria B M J, Turan F, Karmakar A, Roy S S, et al. Compact domain-specific co-processor for accelerating module lattice-based kem[C]//2020 57th ACM/IEEE Design Automation Conference. San Francisco, CA, USA. IEEE, 2020:1-6. [12] Sinha R S, Basso A. High-speed instruction-set coprocessor for lattice-based key encapsulation mechanism: Saber in hardware[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020, 2020(4):443- 466. |
| 备注/Memo: | 收稿日期:2022-05-31.宁波大学学报（理工版）网址:http://journallg.nbu.edu.cn/ 基金项目:国家自然科学基金（62134002,62174121）. 第一作者:吕杰（1996－）,男,浙江绍兴人,在读硕士研究生,主要研究方向:集成电路和信息安全等.E-mail:lv_jie_i_am@163.com *通信作者:汪鹏君（1966－）,男,浙江宁波人,教授,主要研究方向:集成电路和信息安全等.E-mail:wangpengjun@wzu.edu.cn 宁波大学学报（理工版）网址：http://journallg.nbu.edu.cn/ |
