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

A Large-Width Polynomial Multiplier Based on Karatsuba Algorithm for BIKE

作　　者：杨柳 张永真 田静[2] 宋苏文 王中风 YANG Liu;ZHANG Yong-zhen;TIAN Jing;SONG Su-wen;WANG Zhong-feng(School of Electronic Science and Engineering,Nanjing University,Nanjing,Jiangsu 210023,China;School of Integrated Circuits,Nanjing University,Suzhou,Jiangsu 215011,China;School of Integrated Circuits,Sun Yat-Sen University,Shenzhen,Guangdong 518107,China)

机构地区：[1]南京大学电子科学与工程学院,江苏南京210023 [2]南京大学集成电路学院,江苏苏州215011 [3]中山大学集成电路学院,广东深圳518107

出　　处：《电子学报》2025年第1期84-93,共10页Acta Electronica Sinica

基　　金：国家自然科学基金(No.62104097)。

摘　　要：当前美国国家标准与技术研究院(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%.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%.

关 键 词：后量子密码(PQC) 多项式乘法器 Karatsuba算法(KA) 位翻转密钥封装(BIKE) 

分 类 号：TN47[电子电信—微电子学与固体电子学]