Configurable radix-4 NTT hardware optimization and implementation for lattice-based cryptography

ZHOU Qinglei; HAN Heru; LI Bin; LIU Yuhang

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

您当前的位置：

首页 >

文章列表页 >

Configurable radix-4 NTT hardware optimization and implementation for lattice-based cryptography

Papers | 更新时间：2024-11-14

- Configurable radix-4 NTT hardware optimization and implementation for lattice-based cryptography
- Journal on Communications Vol. 45, Issue 10, Pages: 163-179(2024)
- 作者机构：
  
  1.郑州大学计算机与人工智能学院，河南郑州 450001
  2.河南省网络密码技术重点实验室，河南郑州 450001
- 作者简介：
- 基金信息：
  
  Henan Province Science and Technology Key Project(232102211055);Research Topic of Henan Province Key Laboratory of Cybersecurity and Cryptology(LNCT2022-A14);Major Science and Technology Special Project of Henan Province(221100210600)
- DOI：10.11959/j.issn.1000-436x.2024188
  CLC： TP309
- Received：15 May 2024，
  
  Revised：2024-10-08，
  
  Published：25 October 2024
- 稿件说明：
移动端阅览
周清雷,韩贺茹,李斌等.面向格密码的可配置基-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 .

Views

1229

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

FPGA multi-unit parallel optimization and implementation of post-quantum cryptography CRYSTALS-Kyber

Related Author

Bin LI

Xiaojie CHEN

Feng FENG

Qinglei ZHOU

Related Institution

State Key Laboratory of Mathematical Engineering and Advanced Computing, Information Engineering University

AI问答

⁰