Paper 2026/1188

Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT

Chakshu Gupta, Georgia Institute of Technology
Abstract

NIST standardised ML-KEM and ML-DSA in 2024 for post-quantum key establishment and digital signatures. Both compute forward number-theoretic transforms on secret polynomials. Their fixed multipliers, called twiddles, are a documented fault-attack target. Published attacks zero every twiddle during Kyber key generation with a single fault, or individual twiddles in one Dilithium signing variant. Nonzero replacements preserve transform invertibility, raising the question of what the difference between correct and faulted outputs reveals without transform collapse. This paper characterises the linear map from a secret polynomial to that transform difference under static twiddle replacements. Each selected twiddle takes a fixed changed field value at every use during one call; zero and nonzero replacements, including qualifying bit flips, are covered. For one replacement, 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 and replacement values specify the linear equations, while a known transform difference supplies their values. With one replacement per layer, these equations determine every coefficient except the constant and linear coefficients for ML-KEM, or the constant for ML-DSA. Lean 4 certifies this result for both 256-coefficient network shapes over fields of characteristic other than two, with nonzero original twiddles. Those coefficients cancel from the difference for every allowed fault set and choice of replacement values. NIST permits seed storage, motivating comparison of a known correct public key with a released faulty key from the same seed. If replacements affect only one ML-KEM secret-polynomial transform and all other computations are unchanged, the decoded 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 the paired compressed keys is established.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
ML-KEMML-DSANTTfault attackleakage boundformal verificationpost-quantum cryptography
Contact author(s)
cgupta65 @ gatech edu
History
2026-10-27: last of 5 revisions
2026-06-06: received
See all versions
Short URL
https://ia.cr/2026/1188
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/1188,
      author = {Chakshu Gupta},
      title = {Rank Ceiling for Twiddle-Perturbation Faults on the Forward {NTT}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1188},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1188}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.