Paper 2026/1188

Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT

Abstract

NIST standardised a lattice-based key-encapsulation mechanism (ML-KEM) and a lattice-based digital signature scheme (ML-DSA) in 2024 as post-quantum replacements for classical key establishment and digital signatures. 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 with a single glitch on ML-KEM key generation, or zero individual twiddles on ML-DSA signing. Countermeasures detect or mask such faults, but none bounds the information that survives when an attacker perturbs twiddles one at a time. This paper supplies that bound as an exact per-layer rank ladder, for arbitrary perturbations $\zeta_k \mapsto \zeta_k^{'}$ with bit-flips included. A single twiddle fault leaks exactly the butterfly length of its layer in secret coefficients, a count attained rather than merely bounded, so one fault per layer pins all but two coefficients for ML-KEM and all but one for ML-DSA. The surviving ambiguity is identical whichever twiddle is hit in each layer: $\mathrm{span}(e_0, e_1)$ for ML-KEM's incomplete NTT, $\mathrm{span}(e_0)$ for ML-DSA's complete NTT. No combination of twiddle-perturbation faults, however large, shrinks it further, and this rank-and-kernel characterisation is machine-checked in Lean 4. The per-layer leakage rate it exposes gives countermeasure designers a closed-form budget for allocating protection.

Note: Remark 2 (intermediate-product faults): the conjecture that span{D(s)} = Im(D_k) is now proved; the "formal proof remains open" qualifier is removed. Remark 4 (sign-time query count): the observable gap left to future work in v1 is now closed with a concrete per-polynomial query analysis, reconciling the rank ceiling with the query counts of Yuan et al. Remark 5 (inverse-NTT rank ceiling): new. The Gentleman–Sande inverse transform has the same rank ceiling as the forward direction (machine-checked in Lean 4); the remark shows this ceiling is structurally gated and not a live differential attack. §1 and §8 reconciled with the above; minor prose tightening throughout §7.