Paper 2026/1188
Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT
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
-
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}
}