Paper 2025/170

Efficient Error Detection Methods for the Number Theoretic Transforms in Lattice-Based Algorithms

Mohamed Abdelmonem, Simula Research Laboratory, Infineon Technologies (Germany)
Lukas Holzbaur, Infineon Technologies (Germany)
Håvard Raddum, Simula Research Laboratory
Alexander Zeh, Infineon Technologies (Germany)
Abstract

The Number Theoretic Transform (NTT) is a crucial component in many post-quantum cryptographic (PQC) algorithms, enabling efficient polynomial multiplication. However, the reliability of NTT computations is an important concern, especially for safety-critical applications. This work presents novel techniques to improve the fault tolerance of NTTs used in prominent PQC schemes such as Kyber, Dilithium, and Falcon. The work first establishes a theoretical framework for error detection in NTTs, exploiting the inherent algebraic properties of these transforms. It derives necessary and sufficient conditions for constructing error-detecting vectors that can identify single faults without the need for costly recomputation. For the Dilithium scheme, the work further advances the state-of-the-art by developing the first algorithm capable of detecting up to two maliciously placed faults. The proposed error detection methods are shown to reduce the number of required multiplications by half, leading to significant improvements in computational efficiency compared to existing single error-detecting algorithms. Concrete implementations for Kyber, Dilithium, and Falcon demonstrate the practicality and effectiveness of the error-detection scheme.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Cascade 2025
Keywords
Error DetectionLattice-Based CryptographyNumber Theoretic TransformPost-Quantum Cryptography
Contact author(s)
mohameda @ simula no
lukas holzbaur @ infineon com
haavardr @ simula no
alexander zeh @ infineon com
History
2025-02-07: approved
2025-02-05: received
See all versions
Short URL
https://ia.cr/2025/170
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2025/170,
      author = {Mohamed Abdelmonem and Lukas Holzbaur and Håvard Raddum and Alexander Zeh},
      title = {Efficient Error Detection Methods for the Number Theoretic Transforms in Lattice-Based Algorithms},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/170},
      year = {2025},
      url = {https://eprint.iacr.org/2025/170}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.