Paper 2025/170
Efficient Error Detection Methods for the Number Theoretic Transforms in Lattice-Based Algorithms
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
-
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} }