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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Fault-Resistant NTT by Polynomial Evaluation and Interpolation

  • Sven Bauer,
  • Fabrizio De Santis,
  • Kristjane Koleci,
  • Anita Aghaie

摘要

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.