Paper 2026/1188

Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT

Abstract

NIST standardised the lattice-based key-encapsulation mechanism ML-KEM and the lattice-based digital signature scheme ML-DSA in 2024. Both compute a forward number-theoretic transform (NTT) over secret-bearing polynomials; the NTT's twiddle constants are a documented fault-attack surface. Published attacks zero every twiddle at once on ML-KEM key generation, or individual twiddles on ML-DSA signing. Countermeasures detect or mask such faults but none quantifies how much a single-twiddle perturbation disturbs the secret. This paper does, for key generation: the exact rank at each NTT layer of the linear map from the secret to the difference between a correct and a faulted run, for arbitrary twiddle perturbations, bit-flips included. Through that map, a single twiddle fault reveals as many independent linear combinations of a secret polynomial as there are butterflies using the twiddle, an exact count and not just a bound; stacking one fault per layer collapses the map's kernel to two coefficients of that polynomial for ML-KEM and one for ML-DSA. This kernel is the same whichever twiddle is hit in each layer, and no fault set, however large, shrinks it; the rank and kernel are machine-checked in Lean 4. ML-KEM publishes the faulted key uncompressed, so an attacker recovers all but those coefficients for all but a small fraction of keys; ML-DSA compresses its key, leaving the exact recovered count open. The exact per-layer rank tells countermeasure designers how much each layer's fault disturbs the secret.