Paper 2024/788

A Fault-Resistant NTT by Polynomial Evaluation and Interpolation

Sven Bauer, Siemens (Germany)
Fabrizio De Santis, Siemens (Germany)
Kristjane Koleci, Siemens (Germany)
Anita Aghaie, Siemens (Germany)
Abstract

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 Kyber and the digital signature algorithm Dilithium. In this work, we introduce a novel and efficient method for safeguarding the NTT against fault 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 Kyber and Dilithium 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 Dilithium.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
Lattice-Based CryptographyPost-Quantum CryptographyKyberDilithiumNTTFault Countermeasures
Contact author(s)
svenbauer @ siemens com
fabrizio desantis @ siemens com
kristjane koleci @ siemens com
anita aghaie @ siemens com
History
2024-05-24: approved
2024-05-22: received
See all versions
Short URL
https://ia.cr/2024/788
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/788,
      author = {Sven Bauer and Fabrizio De Santis and Kristjane Koleci and Anita Aghaie},
      title = {A Fault-Resistant {NTT} by Polynomial Evaluation and Interpolation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/788},
      year = {2024},
      url = {https://eprint.iacr.org/2024/788}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.