Fault effects on secret keys exposed by number-theoretic transform errors
Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT
Cryptography and Security
Summary
Some modern cryptography methods use mathematical steps called number-theoretic transforms (NTTs) on secret data. The paper studies what happens when a small error (called a fault) changes part of this transform, especially focusing on specific components called twiddles. The researchers show exactly how much information about the secret input leaks from these faults. They find ways to measure this leakage and how it depends on the fault’s position and type. This helps in designing better protections against such attacks.
What this means in practice
- •For hardware security engineers: Design and verify fault detection or masking methods that reduce secret information leakage from single twiddle faults in cryptographic NTT computations.
- •For embedded system developers: Assess risks of fault attacks on NIST-standard post-quantum key generation and signature algorithms to implement stronger countermeasures.
Authors
Chakshu Gupta
Abstract
NIST standardised ML-KEM and ML-DSA in 2024 for post-quantum key establishment and digital signatures. Both compute forward number-theoretic transforms (NTTs) on secret polynomials. Published attacks zero every fixed multiplier, or twiddle, during Kyber key generation with a single fault, or individual twiddles in one Dilithium signing variant; countermeasures detect or mask these faults. Nonzero replacements preserve invertibility, but the uncompressed correct-minus-faulted transform difference can still expose input information. This paper characterises the linear map from a secret polynomial to this difference under arbitrary static twiddle replacements, including bit-flips. For one fault, rank equals the number of butterflies sharing its twiddle, halving by layer from 128 to 2 for ML-KEM and to 1 for ML-DSA. Known positions, replacement values and the difference determine that many independent linear combinations of input coefficients. With one fault per layer, all but the constant and linear coefficients for ML-KEM, or the constant for ML-DSA, are determined; Lean 4 certifies this rank-and-kernel result. Those coefficients cancel for every fault set and choice of replacement values. NIST permits seed storage, motivating comparison of a known correct key with a released faulty key from the same seed. If only one ML-KEM secret-polynomial NTT is faulted, the key difference is a known matrix column times the transform difference; an invertible column entry reconstructs the latter. For ML-DSA, neither reconstruction nor the number of secret-polynomial candidates from compressed key differences is established. The per-layer ranks give a closed-form measure of raw exposure for countermeasure design.