The Hint Weight of ML-DSA Signatures Is Key-Dependent: An Empirical Study across the Three FIPS 204 Parameter Sets

summary

Video file (mp4)

The gist

The gist Every ML-DSA (FIPS 204) signature carries a public hint vector h, and an empirical study finds that the Hamming weight of each hint polynomial hk depends on the signing key, which is a weak

In short

The study investigated whether ML-DSA signatures' hint weights depend on the signing key. Findings show that while the total hint weight is weakly key-dependent (explaining 0.5% to 1.5% of variance), per-polynomial weights are strongly dependent on the key. This suggests a weak statistical fingerprint exists, but it does not endanger the secret signing key.

Key concepts

ML-DSA (FIPS 204) Signature
This is a digital signature scheme standardized by NIST. Each signature includes a public hint vector 'h' used by the verifier to correct rounding errors when reconstructing the compressed public key. The paper examines how the properties of this hint vector relate to the private signing key.
Hint Weight (wt(hk))
This refers to the Hamming weight, or the number of '1's, in each polynomial within the hint vector 'h'. The research found that this weight is not random; it depends on which specific private signing key was used to generate the signature.
(t0)k Euclidean Norm
The authors model the key dependence by relating the expected hint weight to the Euclidean norm of a specific part of the private key, denoted as (t0)k. This term represents a low-order part of the private key that is not kept secret but can be recovered from signatures.

Terminology used across episodes

This episode discusses

The paper

The Hint Weight of ML-DSA Signatures Is Key-Dependent: An Empirical Study across the Three FIPS 204 Parameter Sets · Read on arXiv

Dominik Blain

Every ML-DSA (FIPS 204) signature carries a public hint vector h. We find that the Hamming weight of each hint polynomial h k depends on the signing key: to first order it measures the Euclidean norm of (t0) k, the low-order part of t that key generation leaves out of the public key. A closed-form model predicts the per-key mean weight with Pearson r between 0.95 and 0.98; once the norm is accounted for, we detect no key-dependent signal above sampling noise. We measure the effect on the reference C implementation, with 200 keys and 2,000 signatures per key for each parameter set. A one-way ANOVA rejects key-independence of the total hint weight for ML-DSA-44, ML-DSA-65 and ML-DSA-87 (F = 30.1, 10.3, 11.1). The effect is weak: the key explains 0.5% to 1.5% of the variance of the total weight. A single signature identifies its key among 200 with 1.1 to 1.3 times chance accuracy from the total weight, and 1.5 to 1.8 times from the per-polynomial weight vector. A one-sided test at significance 0.001 separates two typical keys with probability one half after about 1,300 to 3,700 signatures per key. The hint weight does not endanger the signing key. The Dilithium designers do not treat t0 as secret, and t0 is known to be recoverable from signatures. The hint weight is, however, a weak statistical fingerprint: with enough signatures, it can be used to test whether they come from a common key, without the public key. Bounded-weight signing, a backward-compatible filter whose effect on the security argument we did not analyze, removes 86-91% of the between-key spread of the total weight but leaves the per-polynomial channel largely intact.

Transcript

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

Nadia: I'm Nadia, and with me are Elias and Priya, guest researcher.

Elias: Today's paper: "The Hint Weight of ML-DSA Signatures Is Key-Dependent".

Nadia: The gist Every ML-DSA (FIPS 204) signature carries a public hint vector h,

Elias: First, who's behind it and why it matters.

Paper summary: Nadia: So we're wrapping up this discussion on "The Hint Weight of ML-DSA Signatures Is Key-Dependent: An Empirical Study across the Three FIPS two hundred four Parameter Sets <ref:2610.10992#pg1,The Hint Weight of ML-DSA Signatures Is Key-Dependent: An Empirical>." We saw that the total hint weight is only weakly key-dependent, explaining just zero point five percent to one point five percent of the variance in the data <ref:2610.10992#pg3>.

Elias: The authors found that a single signature can identify its key among two hundred with an accuracy of one point one to one point three times chance using just the total weight, but that accuracy jumps to one point five to one point eight times when looking at the per-polynomial weight vector <ref:2610.10992#pg1>.

Priya: So what this paper really means for us is that we have a weak statistical fingerprint in ML-DSA signatures that lets an observer test if two batches of signatures come from the same key without needing the public key <ref:2610.10992#pg2>.

Nadia: That's the practical relevance, Priya. It means filtering on total weight reduces that total-weight channel, but you still have to deal with the per-polynomial channel because that's where the key dependence stays intact <ref:2610.10992#pg3>.

Elias: The conclusion is that this hint weight does not endanger the signing key because (t0) is known to be recoverable from signatures, and the Dilithium designers don't treat it as secret <ref:2610.10992#pg3>.

Priya: So, in short, we have identified a weak linkability fingerprint that exists in ML-DSA signatures and shown how countermeasures like bounded-weight signing affect that fingerprint by measuring the effect on the total versus per-polynomial channels <ref:2610.10992#pg3>.

Conclusion: Nadia: So we're looking at "The Hint Weight of ML-DSA Signatures Is Key-Dependent: An Empirical Study across the Three FIPS two hundred four Parameter Sets." This paper is about whether that public hint vector carries some secret information about the private key used to sign a message.

Elias: Right, it's checking if the weight of each part of that signature hints at something specific about how you generated your key. The authors are looking at three different parameter sets from FIPS two hundred four which is just Dilithium.

Priya: So they measured the Hamming weight, which is just a count of those bits in the hint vector, and they found it's not completely random across different keys. It’s weak but it exists.

Nadia: Weak is the word. They say the key only explains about half a percent to one and a half percent of why the total weight changes between keys. That’s a tiny bit of variance.

Elias: But they also pointed out that if you look at each individual polynomial in that hint vector, every single one of them is dependent on the key on its own. That’s interesting because it means it's not just a random aggregate number messing things up.

Priya: What does this actually mean for someone who isn't a cryptographer? It suggests that if you collect enough signatures, you could theoretically test if two different batches of messages came from the same signing key without even knowing the public key.

Nadia: That’s the practical relevance—a weak linkability fingerprint. But they also showed that countermeasures like bounded-weight signing can actually remove a huge chunk of that difference, eighty-six to ninety-one percent of it.

Elias: They found that bounded-weight signing really kills the total weight channel, but the per-polynomial channel stays pretty much untouched. So if you only look at the total weight, you lose most of this information.

Priya: It’s a trade-off then—you can filter for some noise reduction, but you still have to deal with that fine detail in the polynomial weights if you want to maintain security guarantees on your own.

Nadia: Exactly. This whole study boils down to this idea: the hint weight doesn't actually compromise the signing key itself, because we already know how to recover parts of it from signatures. But it does give us a statistical tool for testing key reuse in real-world scenarios.

Elias: So we’ve established that this fingerprint is weak and that some defenses can hide it, but the underlying mechanism still exists within the signature structure. Next up, we're going to look at how those countermeasures actually perform on paper.

More episodes

← Home