面向格密码的可配置基-4 NTT硬件优化与实现

周清雷; 韩贺茹; 李斌; 刘宇航

doi:10.11959/j.issn.1000-436x.2024188

您当前的位置：

首页 >

文章列表页 >

面向格密码的可配置基-4 NTT硬件优化与实现

学术论文 | 更新时间：2024-11-14

- 面向格密码的可配置基-4 NTT硬件优化与实现
- Configurable radix-4 NTT hardware optimization and implementation for lattice-based cryptography
- 通信学报 2024年45卷第10期页码：163-179
- 作者机构：
  
  1.郑州大学计算机与人工智能学院，河南郑州 450001
  2.河南省网络密码技术重点实验室，河南郑州 450001
- 作者简介：
  
  [ "周清雷（1962- ），男，河南郑州人，博士，郑州大学教授，主要研究方向为信息安全、自动机理论和计算复杂性理论。" ]
  [ "韩贺茹（1999- ），女，河南驻马店人，郑州大学硕士生，主要研究方向为后量子密码、高性能可重构计算。" ]
  [ "李斌（1986- ），男，河南郑州人，博士，郑州大学讲师，主要研究方向为信息安全、可重构计算。" ]
  [ "刘宇航（1999- ），男，河南商丘人，郑州大学硕士生，主要研究方向为隐私保护计算、可重构硬件架构设计。" ]
- 基金信息：
  
  河南省科技攻关基金资助项目(232102211055);河南省网络密码技术重点实验室研究课题基金资助项目(LNCT2022-A14);河南省重大科技专项基金资助项目(221100210600)
- DOI：10.11959/j.issn.1000-436x.2024188
  中图分类号： TP309
- 收稿日期：2024-05-15，
  
  修回日期：2024-10-08，
  
  纸质出版日期：2024-10-25
- 稿件说明：
移动端阅览
周清雷,韩贺茹,李斌等.面向格密码的可配置基-4 NTT硬件优化与实现[J].通信学报,2024,45(10):163-179.

ZHOU Qinglei,HAN Heru,LI Bin,et al.Configurable radix-4 NTT hardware optimization and implementation for lattice-based cryptography[J].Journal on Communications,2024,45(10):163-179.
周清雷,韩贺茹,李斌等.面向格密码的可配置基-4 NTT硬件优化与实现[J].通信学报,2024,45(10):163-179. DOI： 10.11959/j.issn.1000-436x.2024188.

ZHOU Qinglei,HAN Heru,LI Bin,et al.Configurable radix-4 NTT hardware optimization and implementation for lattice-based cryptography[J].Journal on Communications,2024,45(10):163-179. DOI： 10.11959/j.issn.1000-436x.2024188.

摘要

针对数论变换（NTT）优化格密码算法中的多项式乘法问题，以及NTT设计趋向多应用场景的需求，提出了一种面向格密码的可配置基-4 NTT硬件结构。通过分析基-4 NTT/INTT（Inverse NTT）算法流程，设计了高效的现场可编程门阵列（FPGA）整体结构。该结构具备参数化的运行时可配置性和满足多样化需求的编译时可配置性，以流水线方式构建基-4 NTT统一化蝶形单元，并对模除、模约减等关键模块进行优化，提高了计算效率和可配置性。此外，提出可配置多RAM存储优化设计方案及数据存储分配算法，以避免内存冲突、提高数据访问效率。与相关方案的对比及分析表明，以Dilithium算法为例，所提方案不仅具有较高的工作频率，还实现了面积上高达54.3%的优化和吞吐量高达2倍的提升，能够充分发挥FPGA的计算优势。

Abstract

In response to the complex polynomial multiplication issue in lattice-based cryptography algorithms optimized with number theoretic transform (NTT)

as well as the demand for NTT designs catering to multiple application scenarios

a configurable radix-4 NTT hardware architecture for lattice-based cryptography was proposed. By analyzing the radix-4 NTT/INTT (inverse NTT) algorithm process

an efficient FPGA architecture was designed

which parameterized runtime configurability and offered compile-time configurability to meet diverse requirements

a pipeline approach was used to construct the radix-4 NTT unified butterfly unit

key algorithmic modules such as modular division and modular reduction were deeply optimized

thereby enhancing computational efficiency and reconfigurability. Additionally

a configurable multi-RAM storage optimization design scheme and data storage allocation algorithm were proposed to avoid memory conflicts and improve data access efficiency. Comparison and analysis with related approaches show that

using the Dilithium algorithm as an example

the proposed design not only achieves a high operational frequency but also achieves up to 54.3% improvement in area and 2 times optimization in throughput

fully leveraging the computational advantages of FPGA.

关键词

Keywords

references

SHOR P W . Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer [J ] . SIAM Review , 1999 , 41 ( 2 ): 303 - 332 .

ALAGIC G , APON D , COOPER D , et al . Status report on the third round of the NIST post-quantum cryptography standardization process [R ] . 2022 .

BERNSTEIN D J , LANGE T . Post-quantum cryptography [J ] . Nature , 2017 , 549 ( 7671 ): 188 - 194 .

KUMAR A , OTTAVIANI C , GILL S S , et al . Securing the future Internet of things with post-quantum cryptography [J ] . Security and Privacy , 2022 , 5 ( 2 ): 1 - 11 .

NEJATOLLAHI H , DUTT N , RAY S , et al . Post-quantum lattice-based cryptography implementations [J ] . ACM Computing Surveys , 2019 , 51 ( 6 ): 1 - 41 .

李延斌 , 朱嘉杰 , 唐明 , 等 . 面向格密码的能耗分析攻击技术 [J ] . 计算机学报 , 2023 , 46 ( 2 ): 331 - 352 .

LI Y B , ZHU J J , TANG M , et al . Power analysis attacks for lattice-based cryptography [J ] . Chinese Journal of Computers , 2023 , 46 ( 2 ): 331 - 352 .

ZENG C K , HE D B , FENG Q , et al . The implementation of polynomial multiplication for lattice-based cryptography: a survey [J ] . Journal of Information Security and Applications , 2024 , 83 : 103782 .

LI B , YAN Y F , WEI Y X , et al . Scalable and parallel optimization of the number theoretic transform based on FPGA [J ] . IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 2024 , 32 ( 2 ): 291 - 304 .

CHEN X R , YANG B H , YIN S Y , et al . CFNTT: scalable radix-2/4 NTT multiplication architecture with an efficient conflict-free memory mapping scheme [J ] . IACR Transactions on Cryptographic Hardware and Embedded Systems , 2021 : 94 - 126 .

GARRIDO M . A survey on pipelined FFT hardware architectures [J ] . Journal of Signal Processing Systems , 2022 , 94 ( 11 ): 1345 - 1364 .

ZHANG C , LIU D S , LIU X J , et al . Towards efficient hardware implementation of NTT for kyber on FPGAs [C ] // Proceedings of the 2021 IEEE International Symposium on Circuits and Systems (ISCAS) . Piscataway : IEEE Press , 2021 : 1 - 5 .

MA L J , WU X J , BAI G Q . Parallel polynomial multiplication optimized scheme for CRYSTALS-KYBER post-quantum cryptosystem based on FPGA [C ] // Proceedings of the 2021 International Conference on Communications, Information System and Computer Engineering (CISCE) . Piscataway : IEEE Press , 2021 : 361 - 365 .

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 .

MERT A C , ÖZTÜRK E , SAVAŞ E . FPGA implementation of a run-time configurable NTT-based polynomial multiplication hardware [J ] . Microprocessors and Microsystems , 2020 , 78 : 103219 .

陈韬 , 李慧琴 , 李伟 , 等 . 面向格基后量子密码算法的可重构多项式乘法架构 [J ] . 电子与信息学报 , 2023 , 45 ( 9 ): 3380 - 3392 .

CHEN T , LI H Q , LI W , et al . Reconfigurable polynomial multiplication architecture for lattice-based post-quantum cryptography algorithms [J ] . Journal of Electronics & Information Technology , 2023 , 45 ( 9 ): 3380 - 3392 .

WANG T F , ZHANG C , CAO P , et al . Efficient implementation of dilithium signature scheme on FPGA SoC platform [J ] . IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 2022 , 30 ( 9 ): 1158 - 1171 .

BECKWITH L , NGUYEN D T , GAJ K . High-performance hardware implementation of CRYSTALS-dilithium [C ] // Proceedings of the 2021 International Conference on Field-Programmable Technology (ICFPT) . Piscataway : IEEE Press , 2021 : 1 - 10 .

MERT A C , KARABULUT E , ÖZTÜRK E , et al . An extensive study of flexible design methods for the number theoretic transform [J ] . IEEE Transactions on Computers , 2022 , 71 ( 11 ): 2829 - 2843 .

HU X , TIAN J , LI M H , et al . AC-PM: an area-efficient and configurable polynomial multiplier for lattice based cryptography [J ] . IEEE Transactions on Circuits and Systems I: Regular Papers , 2023 , 70 ( 2 ): 719 - 732 .

DERYA K , MERT A C , ÖZTÜRK E , et al . CoHA-NTT: a configurable hardware accelerator for NTT-based polynomial multiplication [J ] . Microprocessors and Microsystems , 2022 , 89 : 104451 .

IMRAN M , KHAN S , KHALID A , et al . Evaluating NTT/INTT implementation styles for post-quantum cryptography [J ] . IEEE Embedded Systems Letters , 2024 , PP(99): 1.

ABDULRAHMAN A , HWANG V , KANNWISCHER M J , et al . Faster kyber and dilithium on the cortex-M4 [C ] // International Conference on Applied Cryptography and Network Security . Berlin : Springer , 2022 : 853 - 871 .

MERT A C , KARABULUT E , ÖZTÜRK E , et al . A flexible and scalable NTT hardware: applications from homomorphically encrypted deep learning to post-quantum cryptography [C ] // Proceedings of the 2020 Design , Automation & Test in Europe Conference & Exhibition (DATE) . Piscataway : IEEE Press , 2020 : 346 - 351 .

WANG W , TIAN S Q , JUNGK B , et al . Parameterized hardware accelerators for lattice-based cryptography and their application to the HW/SW co-design of qTESLA [J ] . IACR Transactions on Cryptographic Hardware and Embedded Systems , 2020 : 269 - 306 .

MAO G Y , CHEN D L , LI G Y , et al . High-performance and configurable SW/HW co-design of post-quantum signature CRYSTALS-dilithium [J ] . ACM Transactions on Reconfigurable Technology and Systems , 2023 , 16 ( 3 ): 1 - 28 .

SATRIAWAN A , SYAFALNI I , MARETA R , et al . Conceptual review on number theoretic transform and comprehensive review on its implementations [J ] . IEEE Access , 2023 , 11 : 70288 - 70316 .

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

WONG Z Y , WONG D C K , LEE W K , et al . KaratSaber: new speed records for saber polynomial multiplication using efficient karatsuba FPGA architecture [J ] . IEEE Transactions on Computers , 2023 , 72 ( 7 ): 1830 - 1842 .

GUPTA N , JATI A , CHATTOPADHYAY A , et al . Lightweight hardware accelerator for post-quantum digital signature CRYSTALS-dilithium [J ] . IEEE Transactions on Circuits and Systems I: Regular Papers , 2023 , 70 ( 8 ): 3234 - 3243 .

TAKALA J , PUNKKA K . Butterfly unit supporting radix-4 and radix-2 FFT [C ] // Proceedings of The 2005 International TICSP Workshop on Spectral Methods and Multirate Signal Processing . Piscataway : IEEE Press , 2005 : 47 - 54 .

MU J N , REN Y , WANG W , et al . Scalable and conflict-free NTT hardware accelerator design: methodology, proof, and implementation [J ] . IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2023 , 42 ( 5 ): 1504 - 1517 .

赵旭阳 , 梁志闯 , 胡跃 , 等 . NTT架构研究及其FPGA硬件优化实现 [J ] . 计算机学报 , 2023 , 46 ( 12 ): 2670 - 2686 .

ZHAO X Y , LIANG Z C , HU Y , et al . NTT architecture research and its FPGA hardware optimization implementation [J ] . Chinese Journal of Computers , 2023 , 46 ( 12 ): 2670 - 2686 .

浏览量

下载量

CSCD

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

提交

工具集

关联资源

后量子密码CRYSTALS-Kyber的FPGA多路并行优化实现