一种应用于BIKE的基于Karatsuba算法的大尺寸多项式乘法器

杨柳; 张永真; 田静; 宋苏文; 王中风

doi:10.12263/DZXB.20231210

您当前的位置：

首页 >

文章列表页 >

一种应用于BIKE的基于Karatsuba算法的大尺寸多项式乘法器

学术论文 | 更新时间：2025-12-08

- 一种应用于BIKE的基于Karatsuba算法的大尺寸多项式乘法器
- A Large-Width Polynomial Multiplier Based on Karatsuba Algorithm for BIKE
- 电子学报 2025年53卷第1期页码：84-93
- 作者机构：
  
  1.南京大学电子科学与工程学院，江苏南京 210023
  2.南京大学集成电路学院，江苏苏州 215011
  3.中山大学集成电路学院，广东深圳 518107
- 作者简介：
  
  杨柳女，1999年出生于江苏省南通市.2024年毕业于南京大学电子科学与工程学院.现从事数字IC设计与验证工作.E-mail: 18851987916@163.com
  张永真女，2001年出生于河南省杞县.现为南京大学集成电路学院硕士生.主要研究方向为后量子密码.E-mail: yongzhenzhang@smail.nju.edu.cn
  田静女，2020年毕业于南京大学电子学院信息与通信工程专业并获得工学博士学位.现为南京大学集成电路学院助理教授、特聘研究员.主要研究方向包括后量子密码技术、现代纠错码等计算密集型算法的高性能集成电路设计.在领域主流期刊和会议上发表论文近40篇.E-mail: tianjing@nju.edu.cn
- 基金信息：
  
  国家自然科学基金(62104097)
- DOI：10.12263/DZXB.20231210
  中图分类号： TN47;
- 收稿：2023-12-25，
  
  修回：2024-08-26，
  
  纸质出版：2025-01-25
- 稿件说明：
移动端阅览
杨柳, 张永真, 田静, 等. 一种应用于BIKE的基于Karatsuba算法的大尺寸多项式乘法器[J]. 电子学报, 2025, 53(01): 84-93.

YANG Liu, ZHANG Yong-zhen, TIAN Jing, et al. A Large-Width Polynomial Multiplier Based on Karatsuba Algorithm for BIKE[J]. Acta Electronica Sinica, 2025, 53(01): 84-93.
杨柳, 张永真, 田静, 等. 一种应用于BIKE的基于Karatsuba算法的大尺寸多项式乘法器[J]. 电子学报, 2025, 53(01): 84-93. DOI：10.12263/DZXB.20231210

YANG Liu, ZHANG Yong-zhen, TIAN Jing, et al. A Large-Width Polynomial Multiplier Based on Karatsuba Algorithm for BIKE[J]. Acta Electronica Sinica, 2025, 53(01): 84-93. DOI：10.12263/DZXB.20231210

摘要

当前美国国家标准与技术研究院（National Institute of Standards and Technology，NIST）对后量子密码（Post-Quantum Cryptography，PQC）标准化方案的评估已进入第四轮，位翻转密钥封装（Bit Flipping Key Encapsulation，BIKE）协议是目前被评估的四个候选方案之一.在BIKE的密钥生成算法中，多项式乘法作为众多密码系统中特别耗时的操作之一，耗费了大量的时间和面积资源.针对此问题，本文设计了一种基于Karatsuba算法（Karatsuba Algorithm，KA）的无交叠多项式乘法器，可高效实现万级比特位宽的多项式乘法，具有低时延、高性能和面积小的特点.同时，本文将该优化乘法器应用于BIKE密钥生成算法中，并基于现场可编程门阵列（Field Programmable Gate Array，FPGA）对其进行硬件架构实现，改进了原有的紧凑多项式乘法和多项式求逆算法.本文提出的乘法器通过采用不同的操作数位宽，可适应对面积和延时的不同需求.与BIKE原本的设计相比，改进的设计使密钥生成模块的延时减小了36.54%，面积延迟积（Area Delay Production，ADP）减小了10.4%.

Abstract

The current evaluation of the post-quantum cryptography (PQC) standardization program by the National Institute of Standards and Technology (NIST) has entered the fourth round. Bit flipping key encapsulation (BIKE) is one of four candidates currently being evaluated. In the key generation of BIKE

the polynomial multiplication consumes a lot of time and area resources

which is also one of the slowest and most area consuming operations in most cryptography systems. In this work

we propose an overlap-free polynomial multiplier based on the Karatsuba algorithm (KA)

which can efficiently implement polynomial multiplication of tens of thousands of bits with low latency

high performance and small area. This multiplier is applied to the BIKE key generation algorithm

which is implemented in hardware architecture based on the field programmable gate array (FPGA)

improving the original compact polynomial multiplication and polynomial inversion algorithm. The multiplier proposed in this article can adapt to different requirements for area and delay by using different operand bit widths. Compared with BIKE’s original design

the improved design reduces the delay of the key generation module by 36.54% and the area delay production (ADP) by 10.4%.

关键词

Keywords

references

CHEN L , JORDAN S , LIU Y K , et al . Report on post-quantum cryptography [M ] . Gaithersburg : US Department of Commerce, National Institute of Standards and Technology , 2016 .

RIVEST R L , SHAMIR A , ADLEMAN L . A method for obtaining digital signatures and public-key cryptosystems [J ] . Communications of the ACM , 1978 , 21 ( 2 ): 120 - 126 .

MILLER V S . Use of elliptic curves in cryptography [M ] // Advances in Cryptology - CRYPTO'85 Proceedings . Berlin : Springer Berlin Heidelberg , 2007 : 417 - 426 .

黎明 , 吴丹 , 戴葵 , 等 . 高性能可扩展公钥密码协处理器研究与设计 [J ] . 电子学报 , 2011 , 39 ( 3 ): 665 - 670 .

LI M , WU D , DAI K , et al . Research and design of a high-performance scalable public-key cipher coprocessor [J ] . Acta Electronica Sinica , 2011 , 39 ( 3 ): 665 - 670 . (in Chinese)

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 .

张晓涵 , 程池 , 余天润 . 对密钥不匹配攻击的进一步理论分析: 以NTRU-HRSS为例 [J ] . 电子学报 , 2023 , 51 ( 4 ): 1081 - 1092 .

ZHANG X H , CHENG C , YU T R . Further theoretical analysis of key mismatch attacks: A case study of NTRU-HRSS [J ] . Acta Electronica Sinica , 2023 , 51 ( 4 ): 1081 - 1092 . (in Chinese)

ARAGON N , BARRETO P , BETTAIEB S , et al . BIKE: bit flipping key encapsulation round 3 submission [C ] // NIST Post-Quantum Cryptography Standardization Conference . Florida : Fort Lauderdale , 2018 : 1 - 14 .

NIST . Post Quantum Cryptography [EB/OL ] . ( 2024-08-13 )[ 2024-08-20 ] . https://csrc.nist.gov/Projects/post-quantum-cryptography https://csrc.nist.gov/Projects/post-quantum-cryptography .

RICHTER-BROCKMANN J , MONO J , GÜNEYSU T . Folding BIKE: Scalable hardware implementation for reconfigurable devices [J ] . IEEE Transactions on Computers , 2022 , 71 ( 5 ): 1204 - 1215 .

KARATSUBA A A , OFMAN Y P . Multiplication of many-digital numbers by automatic computers [J ] . Doklady Akademii Nauk. SSSR , 1962 , 145 ( 2 ): 293 - 294 .

陈韬 , 李慧琴 , 吴艾青 , 等 . 基于2KNTT的多项式乘法单元设计 [J ] . 电子学报 , 2024 , 52 ( 2 ): 455 - 467 .

CHEN T , LI H Q , WU A Q , et al . A polynomial multiplier design based on 2KNTT [J ] . Acta Electronica Sinica , 2024 , 52 ( 2 ): 455 - 467 . (in Chinese)

ZHU Y H , ZHU M , YANG B H , et al . LWRpro: An energy-efficient configurable crypto-processor for module-LWR [J ] . IEEE Transactions on Circuits and Systems I: Regular Papers , 2021 , 68 ( 3 ): 1146 - 1159 .

WONG Z Y , WONG D C , LEE W K , et al . High-speed RLWE-oriented polynomial multiplier utilizing karatsuba algorithm [J ] . IEEE Transactions on Circuits and Systems II: Express Briefs , 2021 , 68 ( 6 ): 2157 - 2161 .

EL HADJ YOUSSEF W , MACHHOUT M , ZEGHID M , et al . Efficient hardware architecture of recursive Karatsuba-Ofman multiplier [C ] // 2008 3rd International Conference on Design and Technology of Integrated Systems in Nanoscale Era . Piscataway : IEEE , 2008 : 1 - 6 .

HEIDARPUR M , MIRHASSANI M . An efficient and high-speed overlap-free karatsuba-based finite-field multiplier for FGPA implementation [J ] . IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 2021 , 29 ( 4 ): 667 - 676 .

FAN H , SUN J , GU M , et al . Overlap-free Karatsuba - Ofman polynomial multiplication algorithms [J ] . IET Information Security , 2010 , 4 ( 1 ): 8 - 14 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于时滞FlipIt博弈与多智能体强化学习的欺骗防御时机选取方法

基于时空维度分解与异构解码的轻量化轨迹预测模型

考虑簇减少的可变长度限制X结构Steiner最小树算法

融合视觉与几何推理的地下车位全场景检测算法

面向边缘物联网的双教师蒸馏式轻量化入侵检测