A Fault-Resistant NTT by Polynomial Evaluation and Interpolation
摘要
In computer arithmetic operations, the Number Theoretic Transform (NTT) plays a significant role in the efficient implementation of cyclic and nega-cyclic convolutions with the application of multiplying large integers and large degree polynomials. Multiplying polynomials is a common operation in lattice-based cryptography. Hence, the NTT is a core component of several lattice-based cryptographic algorithms. Two well-known examples are the key encapsulation mechanism ML-KEM and the digital signature algorithm ML-DSA. In this work, we introduce a novel and efficient method for safeguarding the NTT against fault injection attacks. This new countermeasure is based on polynomial evaluation and interpolation. We prove its error detection capability, calculate the required additional computational effort, and show how to concretely use it to secure the NTT in ML-KEM and ML-DSA against fault injection attacks. Finally, we provide concrete implementation results of the proposed novel technique on a resource-constrained ARM Cortex-M4 microcontroller, e.g., the technique exhibits a \(72\%\) relative overhead, when applied to ML-DSA, and \(67\%\) , when applied to ML-KEM.