Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT

arXiv:2610.30383 · cs.CR · Submitted 2026-10-21 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: We're looking at the paper: "Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT".

Elias: Here's the gist of the paper. The gist The rank ceiling for twiddle-perturbation faults on the forward NTT characterizes how many independent linear combinations of input coefficients are exposed when fixed multipliers are zeroed or replaced during key generation with a single fault, providing bounds for countermeasure design<ref:2610.30383#pg6>.

Nadia: How it works The paper investigates the linear map from a secret polynomial to the difference between the correct and faulted transform, denoted as DK: F n q → F n q, under arbitrary static twiddle replacements including bit-flips<ref:2610.30383#pg9>.

Elias: The rank of this difference map counts independent linear combinations of input coefficients in the transform difference<ref:2610.30383#pg10>.

Nadia: The rank for a single replacement is determined by the number of butterflies sharing its twiddle, which halves by layer.

Paper summary: Nadia: So, we’re looking at this paper, "Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT." The main idea here is about how much information leaks when you mess with those twiddles during key generation for ML-KEM and ML-DSA.

Elias: Right. Basically, NIST standardized these schemes in two thousand twenty-four and this research looks at attacks where someone zeroes out or replaces fixed multipliers, called twiddles, with a single fault <ref:2610.30383#pg1>. The core claim is that this analysis characterizes the linear map from the secret polynomial to the difference between the correct and faulted transform NIST standardised ML-KEM and ML-DSA in two thousand twenty-four for post-quantum key establishment and digital signatures <ref:2610.30383#pg1,NIST standardised ML-KEM and ML-DSA in 2024 for post-quantum>.

Priya: So, what does characterizing that linear map actually mean for us? Are we talking about something practical for defense, or is this mostly theoretical analysis of how sensitive these polynomials are to faults?

Nadia: It’s about finding the rank of this difference map. This rank tells you the number of independent linear combinations of input coefficients that get exposed when you have a single fault Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT. The paper says that for one fault, the rank equals the number of butterflies sharing its twiddle, and this number halves by layer, going from one hundred twenty-eight to two for ML-KEM and to just one for ML-DSA Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT <ref:2610.30383#pg1,Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT>.

Elias: That halving by layer is interesting. It means that if you have one fault per layer, you get a specific rank ceiling. The paper says that with one replacement per layer, all but the constant and linear coefficients for ML-KEM are determined, or just the constant coefficient for ML-DSA Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT.

Priya: So if we can determine almost everything except a few simple parts of the secret polynomial, that sounds like a pretty strong result for understanding where an attacker might be able to start probing. But what about those coefficients that cancel out?

Nadia: Well, the paper notes that those coefficients cancel out for every fault set and every choice of replacement values Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT. But it also points out that there are specific known positions, replacement values, and the actual transform difference that still determine many independent linear combinations of input coefficients Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT.

Paper summary: Elias: That leads into how this relates to key recovery. The paper mentions that for ML-KEM, if only one secret polynomial NTT is faulted, the key difference is described as "a known matrix column times the transform difference," and an invertible entry in that matrix can reconstruct it Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT.

Priya: So, if we have that known map and that raw difference, we could potentially reconstruct parts of the original secret key even with just one fault? But Elias, what about ML-DSA? Does that reconstruction capability carry over there?

Elias: For ML-DSA, the paper says neither reconstruction nor the number of secret-polynomial candidates from compressed key differences is established Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT. They do look at a different observable for ML-DSA, which is t1 = t1 - t'one instead of just the uncompressed difference Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT <ref:2610.30383#pg1,Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT>.

Nadia: That’s a big difference. For ML-KEM, they have this rank ceiling result that provides linear constraints for coefficient-bounded candidate counts when you have the known map and raw difference available Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT. They give specific counts like forty-nine for ML-KEM-five hundred twelve twenty-five for ML-KEM-seven hundred sixty-eight and ML-KEM-one thousand twenty-four and five for ML-DSA variants Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT.

Priya: Those candidate counts sound like they are not lower bounds on how much work an attacker has to do, but more about bounding the size of polynomials that are consistent with those compressed public keys Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT. So, it’s a constraint on what the possible secrets could look like given the observed public key.

Elias: Exactly. And they also establish kernel inclusions for ML-KEM and ML-DSA, which are certified in Lean four point two seven.zero and Mathlib four point two seven.zero Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT <ref:2610.30383#pg1,Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT>. Specifically, they find ker DK equals (n - two span F q (b0), m = two (n/two)) for ML-KEM and (n - one span F q (b0), m = two n) for ML-DSA Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT <ref:2610.30383#pg1,Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT>.

Nadia: So, what does that kernel mean in practice? It seems like it defines the space of all possible differences you can observe. But I see a limitation mentioned later, where they state that the raw map ranks hold independently of release Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT.

Paper summary: Priya: That’s important because if we're trying to design countermeasures, we need to know what the raw exposure rate is. The paper says the per-layer leakage rate lambda = n/two + one is the single-fault rank from Theorem one Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT <ref:2610.30383#pg1,Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT>. So, if you look at layer zero, that's n/two plusone <ref:2610.30383#pg1>.

Elias: And for ML-DSA, those raw rates have to be distinguished from the compressed observable Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT. They also mention that Power2Round drops twelve low-order bits per coefficient, leaving a high-part vector t1 Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT.

Nadia: So, to put it plainly for someone listening who isn't deep in math, this paper shows us how much input information gets exposed when you try to cheat the forward number-theoretic transform using a single fault on ML-KEM or ML-DSA Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT. It gives us concrete numbers about the rank ceiling per layer and what that means for designing error detection.

Priya: The main thing I’m taking away is that you can use these rank and kernel results as linear constraints to bound the number of possible secret polynomials consistent with observed public keys Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT. It's not about finding a way to recover the key, but it’s about knowing how much information is leaked if you *do* try to recover it.

Elias: And the final part is that for ML-KEM, with one fault per layer, every coefficient of one input polynomial gets determined except for its constant and linear ones Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT. That means those few coefficients cancel out across different fault patterns and replacements Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT.

Nadia: It’s a bit of a cautionary tale about error detection. The paper says that detector guarantees must be matched to these errors in the checked transform, not just to the rank Dk alone Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT. And it mentions that interpolation checks guarantee single-coefficient error detection under its evaluation-point conditions Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT.

Priya: So, what does this change for someone building a post-quantum system? It tells you exactly how sensitive your implementation is to those twiddle faults, and what kind of detection mechanism you need to deploy. It gives you a concrete measure of the raw leakage rate lambda for each layer Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT.

Elias: Ultimately, this work provides a closed-form measure of raw exposure for countermeasure design, specifically by giving you those per-layer ranks Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT. That's what they’ve characterized.

Conclusion: Nadia: So, this paper "Rank Ceiling for Twiddle-Perturbation Faults on the Forward NTT" is really about quantifying how much secret information leaks when you mess with the twiddles in ML-KEM and ML-DSA key generation.

Elias: Exactly, it’s mapping out the linear map from a secret polynomial to what happens when you compare the correct transform to a faulted one.

Priya: So, if I understand this right, they're not trying to find a way around the fault itself but rather measuring the exposure rate for designing better error detection.

Nadia: Right. They show that for ML-KEM and ML-DSA, one single static twiddle replacement per layer gives you a rank ceiling—a limit on how many independent pieces of input information are exposed.

Elias: And they give you specific numbers, like the rank halving by layer, which is really telling about the structural weakness in these schemes under this type of fault.

Priya: What does that mean for us when we’re thinking about countermeasures? If we know this rank ceiling, it tells us what kind of error detection guarantee we actually need to achieve in practice.

Nadia: It means detector guarantees have to match these calculated errors in the checked transform, not just whatever rank calculation you run alone.

Elias: It’s a bit nuanced because they also note that for ML-DSA, those raw rates from the NTT have to be separated from what an observer actually sees in a compressed public key.

Priya: So, it's about distinguishing the noise we create during fault injection from the actual information that gets published.

Nadia: That’s right. The paper establishes these rank and kernel identities, which are certified mathematically, giving us hard constraints on what the possible secret polynomials look like given those observations.

Elias: It sets a floor for what an attacker can actually deduce from a faulty public key if they only have one fault to work with.

Priya: This groundwork is important because it moves us past just saying "it's sensitive" and gives us the actual mathematical bounds on that sensitivity.

Nadia: And this leads into how we design better error detection schemes, which we’ll be digging into next.

College of Computing, Georgia Institute of Technology

cs.CR

Submitted: 2026-10-21

Updated: 2026-10-21

Comments: 20 pages, 1 figure, 1 table. Also available at https://eprint.iacr.org/2026/1188

Code: https://github.com/ChakshuGupta13/lab

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 90/100

The gist: The gist The rank ceiling for twiddle-perturbation faults on the forward NTT characterizes how many independent linear combinations of input coefficients are exposed when fixed multipliers are zeroed

Key concepts

Forward NTT: A mathematical tool used in cryptography to perform fast polynomial multiplication. It transforms a polynomial from the coefficient domain into the transform domain where multiplication is simpler. The paper focuses on faults occurring within this transformation process.
Twiddle Replacement Fault: This refers to a specific type of error where one of the fixed multipliers (twiddles) used in the NTT calculation is intentionally changed or zeroed during key generation. The study quantifies how much information about the secret polynomial leaks when such a fault occurs.
Rank Ceiling: This measures the maximum number of independent linear combinations of input coefficients that can be determined from the difference between a correct and faulted NTT. It acts as a ceiling, setting an upper limit on how much secret information is exposed by a single fault.

Summary

The gist The rank ceiling for twiddle-perturbation faults on the forward NTT characterizes how many independent linear combinations of input coefficients are exposed when fixed multipliers are zeroed or replaced during key generation with a single fault, providing bounds for countermeasure design<ref:2610.30383#pg6>.

How it works

The paper investigates the linear map from a secret polynomial to the difference between the correct and faulted transform, denoted as DK: F n q → F n q, under arbitrary static twiddle replacements including bit-flips<ref:2610.30383#pg9>. The rank of this difference map counts independent linear combinations of input coefficients in the transform difference<ref:2610.30383#pg10>.

The rank for a single replacement is determined by the number of butterflies sharing its twiddle, which halves by layer. For one replacement per layer, the maximum raw-difference rank is attained when the sum of singleton ranks equals the combined rank. Specifically, for ML-KEM on 256-coefficient inputs, one replacement per layer attains ranks 254 and 255 respectively.

Public-Key Observables

The observation regime assumes an observer knows a public key from an unfaulted run and obtains a faulty public key from another run with the same seed material. For ML-KEM, the decoded key difference is described as a known matrix column times the transform difference, where an invertible entry reconstructs it. For ML-DSA, the observable is ∆t1 = t1 − t′ 1 rather than the uncompressed difference, and for a fixed nonzero transform difference and a uniformly sampled public matrix, the probability of identical compressed keys is below 2−35.

Rank Bounds and Kernel Inclusions

The rank ceiling for an arbitrary fault set K is bounded by the sum of the singleton ranks, specifically rank DK ≤ dim X k∈K rowsp Dk! ≤ X k∈K lenl(k). The kernel inclusions establish that for ML-KEM, ker DK = (n − 2, spanFq (b0, b1) m = log2 (n/2), and for ML-DSA, ker DK = (n − 1, spanFq (b0) m = log2 n. These kernel equalities are certified in the accompanying Lean 4.27.0 and Mathlib 4.27.0 artifact.

Implications for Countermeasures

The rank and kernel results provide linear constraints for coefficient-bounded candidate counts when a known map and raw difference are available. For ML-KEM, the attained per-polynomial counts are 49 for ML-KEM-512, 25 for ML-KEM-768 and ML-KEM-1024, and 5 for ML-DSA variants. These candidate counts are not lower bounds on attack work but rather bounds on coefficient-bounded polynomials consistent with the compressed public keys.

Interaction with Countermeasures

The paper discusses how single stored-twiddle replacements reach all lenl butterflies in its group, and the number of realized errors depends on the input. Detector guarantees must be matched to these errors in the checked transform, not to rank Dk alone. The interpolation check guarantees detection of a single coefficient error under its evaluation-point conditions. The weighted-checksum method guarantees single-error detection and gives a two-error construction for Dilithium.

The raw map ranks hold independently of release, and using them as linear constraints requires the known map and raw difference of Section 2. The layer l has 2l twiddles and a singleton rank n/2l+1. At n = 256, the sole layer-0 twiddle has rank 128, versus 64 rank-2 twiddles in ML-KEM’s last layer and 128 rank-1 twiddles in ML-DSA’s. The protection policy additionally needs implementation costs, covered indices and replacement/release probabilities.

The final result is that the per-layer leakage rate λl:= n/2l+1 is the single-fault rank from Theorem 1. For ML-DSA, these raw rates must be distinguished from the compressed observable. Power2Round drops d = 13 low-order bits per coefficient, leaving the published high-part vector t1 [Nat24a, Alg. 35]. Write ∆t:= t − t′ and ∆t1:= t1 − t′ 1. Write s = s1,r for the affected secret polynomial in module slot r and κ for the number of rows of Ab. For each row i, ∆t (i) (x) = NTT−1 Abi,r · DK(x), 1 ≤ i ≤ κ, where the product is coordinatewise in the complete NTT domain F n q.

The paper concludes that for a single static twiddle replacement, one changed twiddle per layer attains the largest raw-difference rank. For the one-per-layer pattern, a known map and raw difference determine every coefficient of one input polynomial except its constant and linear coefficients for ML-KEM, or its constant coefficient for ML-DSA. For each scheme, those same coefficients cancel from the raw difference for every allowed fault pattern. The paper establishes neither reconstruction nor the number of coefficient-bounded candidates from compressed keys when only one ML-KEM secret-polynomial NTT is faulted. The rank and kernel identities alone establish neither a rejection probability nor an inverse-fault key-recovery procedure. The standardized row counts are κ ∈ 4, 6, 8 [Nat24a, Table 1]. For ML-DSA, these raw rates must be distinguished from the compressed observable. Power2Round drops d = 13 low-order bits per coefficient, leaving the published high-part vector t1 [Nat24a, Alg. 35]. Write ∆t:= t − t′ and ∆t1:= t1 − t′ 1. Write s = s1,r for the affected secret polynomial in module slot r and κ for the number of rows of Ab. For each row i, ∆t (i) (x) = NTT−1 Abi,r · DK(x), 1 ≤ i ≤ κ, where the product is coordinatewise in the complete NTT domain F n q.

The paper is licensed under a “CC BY 4.0” license. The author directed and reviewed this work and takes responsibility for the correctness of all material. The certified statements concern abstract networks, not deployed-code correctness. The certified statements require a field with 2 ≠ 0, nonzero original twiddles and one changed twiddle per layer. The axiom dependencies are exactly propext, Classical.choice and Quot.sound. The certified statements concern abstract networks, not deployed-code correctness<ref:2610.

Improvements for AI systems

Improved Fault Detection via Rank Analysis: The system can detect faults by comparing a known correct key with a released faulty key from the same seed, specifically for ML-KEM, because the decoded key difference is a known matrix column times the transform difference; an invertible column entry reconstructs it.
Enhanced Candidate Filtering: For ML-DSA, the system can use the observation that for a fixed nonzero transform difference and a uniformly sampled public matrix, the probability of identical compressed keys is below 2-35 for every standardized parameter set, which acts as a non-erasure bound against faulty key release.
Optimized Countermeasure Design: The system can design countermeasures by using The per-layer ranks give a closed-form measure of raw exposure for countermeasure design, allowing designers to target the layer with the highest rank to focus protection efforts, such as at layer 0 which has a singleton rank of 128 for ML-KEM.
Candidate Count Bounding: When a known map and raw difference are available, the system can establish candidate counts for coefficient-bounded polynomials in secret vectors, providing an upper bound on the number of possible faulty secrets based on the rank and nullity of the transform difference matrix.
Detection of Multiple Faults: The system can identify faults by comparing DK with Dk, k in K using replacement values, where "rank DK <= dim X k in rowsp Dk!" provides a bound on the total number of independent linear equations derived from an arbitrary fault set K.

Abstract

NIST standardised ML-KEM and ML-DSA in 2024 for post-quantum key establishment and digital signatures. Both compute forward number-theoretic transforms (NTTs) on secret polynomials. Published attacks zero every fixed multiplier, or twiddle, during Kyber key generation with a single fault, or individual twiddles in one Dilithium signing variant; countermeasures detect or mask these faults. Nonzero replacements preserve invertibility, but the uncompressed correct-minus-faulted transform difference can still expose input information. This paper characterises the linear map from a secret polynomial to this difference under arbitrary static twiddle replacements, including bit-flips. For one fault, 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, replacement values and the difference determine that many independent linear combinations of input coefficients. With one fault per layer, all but the constant and linear coefficients for ML-KEM, or the constant for ML-DSA, are determined; Lean 4 certifies this rank-and-kernel result. Those coefficients cancel for every fault set and choice of replacement values. NIST permits seed storage, motivating comparison of a known correct key with a released faulty key from the same seed. If only one ML-KEM secret-polynomial NTT is faulted, the 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 compressed key differences is established. The per-layer ranks give a closed-form measure of raw exposure for countermeasure design.

Sources

Error Detection Schemes for Barrett Reduction of CT-BU on FPGA in Post Quantum Cryptography