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

YANG Liu; ZHANG Yong-zhen; TIAN Jing; SONG Su-wen; WANG Zhong-feng

doi:10.12263/DZXB.20231210

您当前的位置：

首页 >

文章列表页 >

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

PAPERS | 更新时间：2025-12-08

- A Large-Width Polynomial Multiplier Based on Karatsuba Algorithm for BIKE
- ACTA ELECTRONICA SINICA Vol. 53, Issue 1, Pages: 84-93(2025)
- 作者机构：
  
  1.南京大学电子科学与工程学院，江苏南京 210023
  2.南京大学集成电路学院，江苏苏州 215011
  3.中山大学集成电路学院，广东深圳 518107
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(62104097)
- DOI：10.12263/DZXB.20231210
  CLC： TN47;
- Received：25 December 2023，
  
  Revised：2024-08-26，
  
  Published：25 January 2025
- 稿件说明：
移动端阅览
杨柳, 张永真, 田静, 等. 一种应用于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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

“密态网络安全前沿技术”专栏

Dynamic Temporal-Guided Diffusion Model for Pathological Image Classification

OOD Generalization of Vehicle Trajectory Prediction Based on Causal Model of Social Interaction

Selective Learning for Incomplete Medical Data

Automatic Theorem Identification for Scenario-Aware Verification in Ubiquitous Operating Systems

Related Author

No data

Related Institution

No data

⁰