arXiv:2610.30383 · v3
Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT
摘要
ML-KEM and ML-DSA compute forward number-theoretic transforms on secret polynomials. Their fixed multipliers, or twiddles, are a documented fault-attack target. This paper characterises the linear map from a secret polynomial to the difference between correct and faulted transform outputs. Each selected twiddle takes a fixed changed field value at every use during one call; zero and nonzero replacements 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. With one replacement per layer, known fault positions, replacement values and a raw transform difference 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 shapes over fields of characteristic other than two, with nonzero original twiddles. Those coefficients cancel from the difference for every allowed fault set and replacement choice. Seed storage motivates comparing a known correct public key with a released faulty key from the same seed. If only one ML-KEM secret-polynomial transform is affected 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, reconstruction and exact candidate counts from paired compressed keys remain unestablished.
作者备注：22 pages, 1 figure, 1 table. Pre-print also available at https://eprint.iacr.org/2026/1188. Code available at https://github.com/ChakshuGupta13/lab/tree/main/cryptanalysis/gupta2026rank