Crystal-Kyber算法的FPGA高效并行优化

吕顺森; 李斌; 翟嘉琪; 李松岐; 周清雷

doi:10.12263/DZXB.20220523

您当前的位置：

首页 >

文章列表页 >

Crystal-Kyber算法的FPGA高效并行优化

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

- Crystal-Kyber算法的FPGA高效并行优化
- FPGA Efficient Parallel Optimization of Crystal-Kyber
- 电子学报 2024年52卷第5期页码：1679-1689
- 作者机构：
  
  1.郑州大学计算机与人工智能学院，河南郑州 450001
  2.数字工程与先进计算国家重点实验室，河南郑州 450001
- 作者简介：
  
  [ "吕顺森男，1999年出生，河南信阳人.郑州大学硕士生.主要研究方向为后量子密码、高性能计算.E-mail: l_sh_sen@163.com" ]
  [ "李斌男，1986年出生，河南郑州人.博士.郑州大学讲师.主要研究方向为信息安全、可重构计算.E-mail: iebinli@zzu.edu.cn" ]
  [ "翟嘉琪男，1998年出生，河南郑州人.郑州大学硕士生.主要研究方向为高性能计算、体系结构." ]
  [ "李松岐男，1998年出生，河南洛阳人.郑州大学硕士生.主要研究方向为高性能计算、体系结构" ]
  [ "周清雷男，1962 年出生，河南新乡人 . 博士 . 郑州大学教授 . 主要研究方向为信息安全、自动机理论和计算复杂性理论.Email: ieqlzhou@zzu.edu.cn " ]
- 基金信息：
  
  国家自然科学基金(61702518)
- DOI：10.12263/DZXB.20220523
  中图分类号： TP313;
- 收稿：2022-05-09，
  
  修回：2022-07-02，
  
  纸质出版：2024-05-25
- 稿件说明：
移动端阅览
吕顺森, 李斌, 翟嘉琪, 等. 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 .

浏览量

下载量

CSCD

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

提交

工具集

关联资源

Crystals-Dilithium数字签名技术硬件实现综述

高能效混合基多项式乘法算法及可重构硬件结构研究与设计

基于2KNTT的多项式乘法单元设计