面向格基后量子密码的故障检测方案

Fault Detection Scheme for Lattice-based Post-quantum Cryptography

摘要

数论变换(Number Theoretic Transform,NTT)作为后量子格基密码算法(如Kyber和Dilithium)的核心组件,其容错性对系统安全性至关重要.然而,现有NTT故障检测方案普遍存在检测延迟高、硬件开销大的问题.针对上述局限性,本文提出一种算法级的NTT故障检测方案.首先,通过分析NTT潜在的故障攻击点,包括模乘法器、模加法器和蝶形单元等易泄露模块,建立NTT故障模型.其次,提出算法级的NTT故障检测方案.该方案通过旋转输入序列、调整计算系数的预处理操作形成新的输入序列,并设计编码器与解码器对新输入序列进行计算生成待校验值.最后,将原始序列经计算得到的原始校验值与待校验值进行对比,以此判断是否存在错误.实验结果表明:相较于无故障检测的原始实现,该方案仅增加5.8%的硬件面积和5.9%的延迟开销,同时故障检测率接近100%,实现了高故障检测率与低资源开销的平衡.

Abstract

As a core component of post-quantum lattice-based cryptographic algorithms(e.g.,Kyber and Dilithium),the fault tolerance of Number Theoretic Transform(NTT)is crucial for system security.However,existing NTT fault detection schemes generally suffer from high detection latency and high hardware overhead.To address these limitations,this paper proposes an algorithmic-level NTT fault detection scheme.First,an NTT fault model is established by analyzing the potential fault attack points of NTT,including leakage-prone modules such as mode multiplier,mode adder,and butterfly unit.Secondly,an algorithmic-level NTT fault detection scheme is proposed.The scheme forms a new input sequence by the preprocessing operation of rotating the input sequence and adjusting the computational coefficients,and designs the encoder and decoder to generate the to-be-checked value by computing the new input sequence.Finally,the original checksum value calculated from the original sequence is compared with the checksum value to determine whether there is any error.The experimental results show that compared with the original implementation without fault detection,this scheme only increases the hardware area by 5.8% and the delay overhead by 5.9%,while the fault detection rate is close to 100%,realizing the balance between high fault detection rate and low resource overhead.

关键词

后量子密码 / 数论变换(NTT) / 故障注入攻击 / 故障检测

Key words

post-quantum code / Number Theoretic Transformations(NTT) / fault injection attack / fault detection

[1] WANG C,YAO H N,WANG B N,et al.Progress in quantum computing cryptography attacks[J].Chinese Journal of Computers,2020,43(9):1691-1707.
[2] Hermelink J,Streit S,Striede E,et al.Adapting belief propagation to counter shuffling of NTTs[C]//IACR Transactions on Cryptographic Hardware and Embedded Systems,2023:60-88.
[3] Sum K,Duong P N,Lee H C.Configurable memory-based NTT architecture for homomorphic encryption[J].IEEE Transactions on Computers,2015,64(1):123-134.
[4] Zheng Y,Chen J.Scalable and parallel optimization of the number theoretic transform based on FPGA[J].IEEE Transactions on Circuits and Systems I:Regular Papers,2022,69(5):1567-1578.
[5] Liu X,Wang Y.Rethinking parallel memory access pattern in number theoretic transform design[J].Journal of Systems Science and Mathematical Sciences,2023,43(3):567-580.
[6] Aghapour S,Ahmadi K,Anastasova M,et al.PUF-Kyber:design of a PUF-based kyber architecture benchmarked on diverse ARM processors[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2024,43(12):4453-4462.
[7] Mu J,Tan H,Wu J,et al.Energy-efficient NTT design with one-bank SRAM and 2D PE array[C]//Proceedings of the Design,Automation & Test in Europe Conference(DATE),2023:3353-3365.
[8] Tosun T,Savas E.Zero-value filtering for accelerating non-profiled side-channel attack on incomplete NTT-based implementations of lattice-based cryptography[J].IEEE Transactions on Information Forensics and Security,2024,19:3353-3365,doi:10.1109/TIFS.2024.3359890.
[9] Guo Y,Liu W,Chen W,et al.ECLBC:a lightweight block cipher with error detection and correction mechanisms[J].IEEE Internet of Things Journal,2024,11(12):21727-21740.
[10] Saha S,Alam M,Bag A,et al.Learn from your faults:Leakage assessment in fault attacks using deep learning[J].Journal of Cryptology,2023,36(3):19.
[11] Libano F,Rech P,Brunhayer J.Efficient error detection for matrix multiplication with systolic arrays on FPGAs[J].IEEE Transactions on Computers,2023,72(8):2390-2403.
[12] Heinz D,Poppelmann T.Combined fault and DPA protection for lattice-based cryptography[J].IEEE Transactions on Computers,2023,72(4):1055-1066.
[13] Ravi P,Yang B,Bhasin S,et al.Fiddling the twiddle constants-fault injection analysis of the number theoretic transform[C]//IACR Transactions on Cryptographic Hardware and Embedded Systems,2023:447-481.
[14] Kannwischer M J,Rijneveld J,Schwabe P,et al.pqm4:testing and benchmarking NIST PQC on ARM Cortex-M4[EB/OL].https://eprint.iacr.org/2019/844,2019.
[15] Avazi R,Bos J,Ducas L,et al.Crystals-Kyber:algorithm specifications and supporting documentation[EB/OL].Cryptology ePrint Archive:2017/634,https://eprint.iaccr.org/2017/634,2017.
[16] Mus K,Islam S,Sunar B.QuantumHammer:a practical hybrid attack on the LUOV signature scheme[C]//Proceedings of the ACM SIGSAC Conference on Computer and Communications Security,2020,doi:10.1145/3372297.3417272.
[17] Ravi P,Jhanwar M,Howe J,et al.Exploiting determinism in lattice-based signatures:practical fault attacks on pqm4 implementations of NIST candidates[C]//Proceedings of the Asia Conference on Computer and Communications Security(AsiaCCS),2019:427-440.
[18] Singh R,Islam S,Sunar B,et al.Analysis of EM fault injection on bit-sliced number theoretic transform software in Dilithium[J].ACM Transactions on Embedded Computing Systems,2024,23(2):1-27.
[19] Ducas L,Kiltz E,Lepoint T,et al.CRYSTALS-dilithium:a lattice-based digital signature scheme[J].IACR Transactions on Cryptographic Hardware and Embedded Systems,2018,(1):238-268,doi:10.13154/tches.v2018.i1.238-268.
[20] Bauer S,De Santis F,Koleci K,et al.A fault-resistant NTT by polynomial evaluation and interpolation[EB/OL].https://eprint.iacr.org/2024/788,2025-04-15.
[21] O′donnell A,Bleakley C J,Revijtego P,et al.Efficient concurrent error detection and correction of soft errors in NTT-based convolutions[C]//Proceedings of the IET Irish Signals and Systems Conference(ISSC),2009:1-6.
[22] Sarker A,Kermani M M,Azarderakhsh R.Fault detection architectures for inverted binary Ring-LWE construction benchmarked on FPGA[J].IEEE Transactions on Circuits and Systems II:Express Briefs,2021,68(4):1403-1407.
[23] Sarker A,Kermani M M,Azarderakhsh R.Hardware constructions for error detection of number-theoretic transform utilized in secure cryptographic architectures[J].IEEE Transactions on Very Large Scale Integration(VLSI)Systems,2018,27(3):738-741.
[24] Sarker A,Canto A C,Kermani M M,et al.Error detection architectures for hardware/software co-design approaches of number-theoretic transform[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2022,42(7):2418-2422.
[25] Khan S,Khalid A,Rafferty C,et al.Efficient,error-resistant NTT architectures for CRYSTALS-Kyber FPGA accelerators[C]//Proceedings of IFIP/IEEE 31st International Conference on Very Large Scale Integration(VLSI-SoC),2023:1-6.
[26] Kastensmidt F,Rech P.FPGAs and parallel architectures for aerospace applications[C]//British Journal of Pharmacology,2016,doi:10.1007/978-3-319-14352-1.
[27] Sarker A,Kermani M M,Azarderakhsh R.Error detection architectures for ring polynomial multiplication and modular reduction of Ring-LWE in Z/pZ[x]xⁿ+1 benchmarked on ASIC[J].IEEE Transactions on Reliability,2021,70(1):362-370.
[28] Sarker A,Kermani M M,Azarderakhsh R.Efficient error detection architectures for postquantum signature Falcon′s sampler and KEM SABER[J].IEEE Transactions on Very Large Scale Integration(VLSI)Systems,2022,30(6):794-802.
[29] Canto A C,Sarker A,Kaur J,et al.Error detection schemes assessed on FPGA for multipliers in lattice-based key encapsulation mechanisms in post-quantum cryptography[J].IEEE Transactions on Emerging Topics in Computing,2023,11(3):791-797

基金资助

先进密码技术与系统安全四川省重点实验室开放课题项目(SKLACSS-202408)资助;嵩山实验室项目(241110210200)资助.