FPGA Efficient Parallel Optimization of Crystal-Kyber

LÜ Shun-sen; LI Bin; ZHAI Jia-qi; LI Song-qi; ZHOU Qing-lei

doi:10.12263/DZXB.20220523

您当前的位置：

首页 >

文章列表页 >

FPGA Efficient Parallel Optimization of Crystal-Kyber

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

- FPGA Efficient Parallel Optimization of Crystal-Kyber
- ACTA ELECTRONICA SINICA Vol. 52, Issue 5, Pages: 1679-1689(2024)
- 作者机构：
  
  1.郑州大学计算机与人工智能学院，河南郑州 450001
  2.数字工程与先进计算国家重点实验室，河南郑州 450001
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20220523
  CLC： TP313;
- Received：09 May 2022，
  
  Revised：2022-07-02，
  
  Published：25 May 2024
- 稿件说明：
移动端阅览
吕顺森, 李斌, 翟嘉琪, 等. Crystal-Kyber算法的FPGA高效并行优化[J]. 电子学报, 2024, 52(05): 1679-1689.

LÜ Shun-sen, LI Bin, ZHAI Jia-qi, et al. FPGA Efficient Parallel Optimization of Crystal-Kyber[J]. Acta Electronica Sinica, 2024, 52(05): 1679-1689.
吕顺森, 李斌, 翟嘉琪, 等. Crystal-Kyber算法的FPGA高效并行优化[J]. 电子学报, 2024, 52(05): 1679-1689. DOI：10.12263/DZXB.20220523

LÜ Shun-sen, LI Bin, ZHAI Jia-qi, et al. FPGA Efficient Parallel Optimization of Crystal-Kyber[J]. Acta Electronica Sinica, 2024, 52(05): 1679-1689. DOI：10.12263/DZXB.20220523

摘要

多项式乘法运算制约着基于格的后量子密码在现实中的应用.为提高后量子密码Crystal_Kyber算法的性能效率，减少运行时间，降低多项式乘法的影响，本文设计了一种新的蝶形运算单元对素模

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=61955448&type=

2.87866688

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=61955452&type=

1.60866666

=3 329的Kyber方案进行优化.首先，采用16路并行调度新型蝶形运算单元的方式执行算法，缩短了计算周期；其次，使用流水线技术以及改进的K

RED算法，设计实现新型蝶形运算单元，用于降低资源消耗；最后，利用多RAM的方式存储数据，并且多通道优化RAM，允许数据交替存储在RAM中，提高资源复用率.实验结果表明，本文优化后的数论变换（Number Theoretic Transform，NTT）、逆数论变换（Inverse NTT，INTT）、点对位相乘（Point-Wise Multiplication，PWM）的效率达到200 MHz，合并执行Kyber效率达到175 MHz，优于其他方案，具有良好的性能.

Abstract

Polynomial multiplication operations limit the practical applications of lattice-based post-quantum cryptography. In order to improve the performance and efficiency of post-quantum cryptography Crystal_Kyber algorithm

and reduce the running time and reduce the influence of polynomial multiplication

this paper designs a new butterfly operation unit to optimize the Kyber scheme with prime modulus

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=61955454&type=

2.87866688

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=61955456&type=

10.75266743

. First of all

the algorithm is executed by 16-way parallel scheduling of the new butterfly operation unit

which shortens the calculation cycle. Secondly

using pipeline technology and improved K

RED algorithm

the design and implementation of a new butterfly operation unit for reducing resource consumption. Ultimately

the data is stored in the way of multi-RAM

and the multi-channel RAM is optimized to allow data to be stored alternately in RAM and improve the resource reuse rate. The experimental results show that the optimized NTT (number theoretic transform)

INTT (Inverse NTT)

PWM (point-wise m

ultiplication) efficiency reaches 200 MHz

and the combined execution Kyber efficiency reaches 175 MHz

which is superior to other schemes and has good performance.

关键词

Keywords

references

NIST . Post-Quantum cryptography call for proposals [EB/OL ] . ( 2017-01-03 )[ 2022-04-15 ] . https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptographt-standardization/Call-for-Proposals https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptographt-standardization/Call-for-Proposals .

AVANZI R , BOS J , DUCAS L , et al . Crystals-kyber [R ] . Maryland : NIST , 2017 .

BISHEH-NIASAR M , AZARDERAKHSH R , MOZAFFARI-KERMANI M . High-speed NTT-based polynomial multiplication accelerator for post-quantum cryptography [C ] // 2021 IEEE 28th Symposium on Computer Arithmetic (ARITH) . Piscataway : IEEE , 2021 : 94 - 101 .

REGEV O . On lattices, learning with errors, random linear codes, and cryptography [J ] . Journal of the ACM , 2009 , 56 ( 6 ): 1 - 40 .

BOTROS L , KANNWISCHER M J , SCHWABE P . Memory-efficient high-speed implementation of Kyber on Cortex-M4 [C ] // International Conference on Cryptology in Africa . Springer : Cham , 2019 : 209 - 228 .

BASU K , SONI D , NABEEL M , et al . Nist post-quantum cryptography-a hardware evaluation study [J ] . IACR Crgptology Eprint Archive , 2019 , 47 : 1 - 16 .

ALKIM E , EVKAN H , LAHR N , et al . ISA extensions for finite field arithmetic: Accelerating Kyber and NewHope on RISC-V [J ] . IACR Transactions on Cryptographic Hardware and Embedded Systems , 2020 , 2020 : 219 - 242 .

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 .

DANG V , FARAHMAND F , ANDRZEJ- CZAK 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 [EB/OL ] . ( 2020 )[2022 ] . https://eprint.iacr.org/2020/795 https://eprint.iacr.org/2020/795 .

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 .

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 .

ROY S 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 : 443 - 466 .

周朕 , 何德彪 , 罗敏 , 等 . 紧凑的 Aigis-sig 数字签名方案软硬件协同实现方法 [J ] . 网络与信息安全学报 , 2021 , 7 ( 2 ): 64 - 76 .

ZHOU Z , HE D B , LUO M , et al . Compact software/hardware co-design and implementation method of Aigis-sig digital signature scheme [J ] . Chinese Journal of Network and Information Security , 2021 , 7 ( 2 ): 64 - 76 . (in Chinese)

ZHANG J , YU Y , FAN S , et al . Tweaking the asymmetry of asymmetric-key cryptography on lattices: KEMs and signatures of smaller sizes [C ] // IACR International Conference on Public-Key Cryptography . Cham : Springer , 2020 : 37 - 65 .

崔益军 , 姚衎 , 倪子颖 , 等 . 基于 MLWE 的格密码高效硬件实现 [J ] . 信息安全学报 , 2021 , 6 ( 6 ): 40 - 50 .

CUI Y J , YAO K , NI Z Y , et al . Efficient hardware implementation of MLWE lattice based cryptography [J ] . Journal of Cyber Security , 2021 , 6 ( 6 ): 40 - 50 . (in Chinese)

FENG X , LI S , XU S . RLWE-oriented high-speed polynomial multiplier utilizing multi-lane stockham NTT algorithm [J ] . IEEE Transactions on Circuits and Systems II: Express Briefs , 2019 , 67 ( 3 ): 556 - 559 .

ZHANG N , YANG B , 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 , 2 : 49 - 72 .

LI H M , MENTENS N , PICEK S . A scalable SIMD RISC-V based processor with customized vector extensions for CRYSTALS-kyber [C ] // Proceedings of the 59th ACM/IEEE Design Automation Conference . New York : ACM , 2022 : 733 - 738 .

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 .

KUO P C , CHEN Y W , HSU Y C , et al . High performance post-quantum key exchange on FPGAs [J ] . Jouranl of Information Sciencie & Engineering , 2021 , 37 ( 5 ): 1211 - 1229 .

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

LI B , CHEN X J , FENG F , et al . FPGA multi-unit parallel optimization and implementation of post-quantum cryptography Crystals-Kyber [J ] . Journal on Communications , 2022 , 43 ( 2 ): 196 - 207 . (in Chinese)

XING Y F , LI S G . An efficient implementation of the NewHope key exchange on FPGAs [J ] . IEEE Transactions on Circuits and Systems I: Regular Papers , 2020 , 67 ( 3 ): 866 - 878 .

BISHEH-NIASAR M , AZARDERAKH- SH R , MOZAFFARI-KERMANI M . Instruction-set accelerated implementation of Crystals-Kyber [J ] . IEEE Transactions on Circuits and Systems I: Regular Papers , 2021 , 68 ( 11 ): 4648 - 4659 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Survey of Hardware Implementation for Crystals-Dilithium Digital Signature in the Post Quantum Cryptography

Research and Design of High Energy Efficient Hybrid Base Polynomial Multiplication Algorithm and Reconfigurable Hardware Structure

A Polynomial Multiplier Design Based on 2KNTT

Related Author

ZHOU Qing-lei

Li Song-qi

Zhai Jia-qi

Lv Shun-sen

LI Bin

LIU Wei-qiang

CUI Yi-jun

LI Meng-xue

Related Institution

School of Computer and Artificial Intelligence， Zhengzhou University

College of Integrated Circuits, Nanjing University of Aeronautics and Astronautics

University of Information Engineering

Information Engineering University

⁰