FIPS 204-Compatible Threshold ML-DSA via Shamir Nonce DKG

This paper introduces the first FIPS 204-compatible threshold ML-DSA scheme that achieves unconditional nonce share privacy and standard signature compatibility through a novel Shamir nonce DKG and pairwise-canceling PRF masks, enabling secure signing with arbitrary thresholds across various coordinator-based and fully distributed profiles.

The Gist

Imagine you have a super-secure digital vault (like a bank account or a government seal) that requires a specific key to open. In the old world, you might give this key to a single person. But if that person gets hacked, loses the key, or decides to go rogue, the whole system is in trouble.

To fix this, we use Threshold Signatures. Instead of one key, we split the key into $N$ pieces (shards) and give them to $N$ different people. To open the vault, you don't need everyone; you just need a specific number of them (say, 3 out of 5) to come together and combine their pieces to sign a transaction.

Now, imagine the world is changing. Quantum computers are coming, and they will break our current locks. The US government (NIST) just released a new, quantum-proof lock called ML-DSA (FIPS 204).

The Problem:
While we have great ways to split keys for old locks (like ECDSA), splitting the new ML-DSA lock is incredibly hard.

1. The "Rejection" Trap: ML-DSA works like a game of "guess the number." If the guess is slightly off, you have to start over. In a single-person scenario, this happens about 20% of the time. But if you try to split the work among 5 people using old methods, the math gets so messy that the chance of success drops to almost zero. It's like trying to get 5 people to whisper a secret to each other, but the noise is so loud that they can never agree on the answer.
2. The Size Problem: Some previous attempts to fix this made the digital "signature" (the receipt) huge—5 times bigger than normal. This breaks compatibility with existing systems, like trying to fit a truck tire on a bicycle.

The Solution: "Shamir Nonce DKG"
This paper presents a new way to split the ML-DSA lock that solves both problems. The author, Leo Kao, uses a clever trick involving Shamir Secret Sharing (a mathematical way to split secrets) specifically for the "nonce" (the random number used in the game).

Here is the analogy:

The Analogy: The Orchestra and the Conductor

Imagine a group of musicians (the signers) trying to play a song (create a signature) for a very strict conductor (the verifier).

The Old Way (The Noise Problem):
In the old attempts, every musician had to shout their part loudly so everyone could hear it. But because they were shouting, the sound got distorted. To fix the distortion, they had to add so much "static noise" that the song became unrecognizable (huge signatures) or they just couldn't agree on the tune (failed attempts).

The New Way (The Whispering Orchestra):
This paper introduces a new method where the musicians don't shout. Instead, they use a Shamir Nonce DKG (Distributed Key Generation).

1. The Secret Sheet Music: Before the concert, the musicians agree on a secret sheet of music (the secret key). They split this music into pieces using a special math trick (Shamir sharing).
2. The Improvisation (The Nonce): For every song, they need to improvise a random melody (the nonce). In the past, they tried to guess this melody individually, which caused the "Rejection Trap."
   • The Innovation: Instead of guessing individually, they jointly generate the melody. Each musician writes a small part of a polynomial (a mathematical curve). When they combine their parts, they get a perfect, random melody that no single person knows, but everyone contributes to.
   • The Magic: Because they are using a specific type of curve (Shamir), even if a hacker steals the notes from 2 out of 3 musicians, they still can't figure out the melody. The remaining notes act like a "one-time pad," making the secret mathematically impossible to crack without the full group.

The "Pairwise-Canceling Masks" (The Noise Canceling Headphones)
There's one more hurdle. When the musicians send their parts to the conductor, they need to hide their individual contributions so no one can steal the melody.

• The paper uses Pairwise-Canceling Masks. Imagine every pair of musicians has a secret "noise-canceling" code. When they send their notes, they add their own noise. But because the noise is perfectly calculated to cancel out the noise from their partner, when the conductor adds everything up, the noise disappears, and only the pure melody remains.
• This ensures privacy without making the signature huge.

The Three "Deployment Profiles" (How to Run the Orchestra)

The paper offers three ways to run this system depending on how much trust you have:

1. Profile P1 (The Trusted Conductor): You have a super-secure, tamper-proof computer (a TEE/HSM) acting as the conductor. It does the hard math in a sealed box.
   • Pros: Fastest (5.8ms).
   • Cons: You have to trust the hardware manufacturer.
2. Profile P2 (The Pure Democracy): No trusted hardware. Everyone talks to everyone using complex math (MPC) to verify each other.
   • Pros: No hardware trust needed; even if most people are bad actors, the system holds.
   • Cons: Slower (21.5ms) and requires more communication.
3. Profile P3+ (The Semi-Async Team): This is for real-world humans. The musicians prepare their parts offline (while they are drinking coffee). When the "Go" signal comes, they just send their part within a time window.
   • Pros: Very flexible; great for humans who can't be online at the exact same second.
   • Cons: Requires a bit of setup.

Why This Matters

• It's Standard: The resulting signature is exactly the same size (3.3 KB) as a normal ML-DSA signature. Existing systems can verify it without any changes.
• It's Fast: It works in milliseconds, comparable to a single person signing.
• It's Secure: It doesn't rely on "hope" or complex assumptions. It uses pure math (statistics) to prove that even if a hacker steals some pieces, they learn nothing.
• It Solves the "Scalability Gap": Previous methods broke when you tried to use more than 6 people. This works for 3, 16, or even 32 people.

In Summary:
This paper is like inventing a new way for a choir to sing a complex, quantum-proof song. Instead of everyone shouting and drowning each other out, they use a secret, coordinated whispering technique that ensures the song is perfect, the audience (verifiers) hears it clearly, and no one in the choir can steal the melody. It makes the future of secure, distributed digital signatures actually practical.

Technical Summary

Here is a detailed technical summary of the paper "FIPS 204-Compatible Threshold ML-DSA via Shamir Nonce DKG" by Leo Kao.

1. Problem Statement

The imminent arrival of quantum computers threatens current public-key cryptography. In response, NIST has standardized ML-DSA (Module-Lattice-Based Digital Signature Algorithm) as FIPS 204. While threshold signatures (where a group of $N$ parties requires a subset of $T$ to sign) are well-established for classical schemes like ECDSA, adapting them to lattice-based ML-DSA presents unique challenges:

• Rejection Sampling: ML-DSA uses the "Fiat-Shamir with Aborts" paradigm. A signature is valid only if the response vector $z = y + cs_1$ satisfies a strict norm bound ($\|z\|_\infty < \gamma_1 - \beta$). In threshold settings, naive reconstruction often violates this bound due to large Lagrange coefficients or noise accumulation.
• Signature Size Compatibility: Existing lattice-based threshold schemes either produce signatures significantly larger than the standard 3.3 KB (breaking FIPS 204 compatibility) or are limited to very small thresholds ($T \le 6$).
• Nonce Privacy: In threshold signing, the signing nonce $y$ must be generated collaboratively. Prior approaches often require a "two-honest" assumption ($|S| \ge T+1$) or rely on computational assumptions (like noise flooding) to hide nonce shares, which can be inefficient or insecure against future attacks.
• The "Threshold Gap": For practical thresholds ($T \in [9, 32]$), no existing scheme simultaneously achieves arbitrary thresholds, standard signature size, FIPS 204 compatibility, and strong privacy guarantees.

2. Methodology

The authors propose Threshold ML-DSA via Shamir Nonce DKG, a novel framework built on two primary techniques:

A. Shamir Nonce DKG (Distributed Key Generation)

Instead of generating the nonce $y$ as a simple sum of random values, the parties jointly generate $y$ as a degree-$(T-1)$ Shamir sharing.

• Structure Matching: The long-term secret key $s_1$ is already shared as a degree-$(T-1)$ polynomial. The nonce $y$ is generated to match this exact structure.
• Privacy Mechanism: Each party $i$ holds a share $y_i$ which is an evaluation of a degree-$(T-1)$ polynomial. The adversary, controlling at most $T-1$ parties, sees only $T-1$ evaluations of an honest party's polynomial.
• Conditional Min-Entropy: Because the polynomial has $T$ coefficients and the adversary knows $T-1$ evaluations, there is exactly one degree of freedom remaining. The honest party's nonce share $y_h$ retains conditional min-entropy exceeding $5\times$the secret key entropy (for$|S| \le 17$). This provides statistical privacy (no computational assumptions required) even with a single honest party in coordinator-based profiles.
• Elimination of Two-Honest Requirement: In coordinator-based profiles (P1, P3+), this technique allows signing sets of size $|S| = T$ (the theoretical minimum), whereas prior pairwise-mask schemes required $|S| \ge T+1$.

B. Pairwise-Canceling Masks

To handle lattice-specific challenges absent in ECDSA (commitment binding, the $r_0$-check, and response aggregation), the authors adapt pairwise-canceling masks:

• Commitment Hiding: Parties mask their commitment values $W_i$ using pairwise PRF seeds. These masks sum to zero, hiding individual contributions while allowing the aggregator to reconstruct the correct aggregate $W$.
• $r_0$-Check Privacy: The check $\|LowBits(w - cs_2)\|_\infty < \gamma_2 - \beta$ requires reconstructing $cs_2$. Since $c$ is invertible with high probability, leaking $cs_2$ reveals the secret key $s_2$. The protocol uses masks to hide individual $s_2$ shares during the reconstruction of $cs_2$ within the aggregator or MPC/2PC sub-protocols.

C. Irwin-Hall Distribution Analysis

The aggregated nonce $y$ follows an Irwin-Hall distribution (the sum of $|S|$ uniform variables) rather than a single uniform draw.

• Security Loss: The authors perform a rigorous direct shift-invariance analysis (Corollary 9) to quantify the security loss.
• Result: The security loss is negligible: $< 0.007$ bits per session for $|S| \le 17$ and $< 0.013$ bits for $|S| \le 33$. This resolves the scalability gap found in prior work where security bounds became vacuous for larger thresholds.

3. Key Contributions

1. First FIPS 204-Compatible Threshold Scheme with Arbitrary $T$: The scheme produces standard 3.3 KB signatures verifiable by unmodified FIPS 204 implementations for any threshold $T$.
2. Statistical Nonce Share Privacy: Achieves nonce privacy based on conditional min-entropy (statistical security) without computational assumptions, even for $|S|=T$ in coordinator-based profiles.
3. Three Deployment Profiles with UC Proofs:
   • Profile P1 (TEE-Assisted): Uses a Trusted Execution Environment (TEE) coordinator. Achieves 3 online rounds. Fastest (5.8 ms for 3-of-5).
   • Profile P2 (Fully Distributed): Uses Multi-Party Computation (MPC) with SPDZ and edaBits. Achieves 5 online rounds with dishonest-majority security (tolerates $N-1$ corruptions). No hardware trust required.
   • Profile P3+ (Semi-Async 2PC): Designed for human-in-the-loop authorization. Uses 2PC between two computation parties. Signers precompute nonces offline and respond within a time window. Achieves 2 logical rounds (1 signer step + 1 server round).
4. Direct Shift-Invariance Bound: Replaces conservative Raccoon-style bounds with a tighter direct analysis, proving the scheme remains secure for thousands of signing sessions without vacuous bounds.

4. Results & Performance

• Implementation: A Rust implementation (approx. 5.5k lines of core logic) was benchmarked on commodity hardware (Intel i7-12700H).
• Latency:
  • P1 (TEE): 5.8 ms (3-of-5), scaling to ~60 ms for 32-of-45.
  • P2 (MPC): 21.5 ms (3-of-5), scaling to ~129 ms for 32-of-45.
  • P3+ (Async): 22.1 ms (3-of-5), scaling to ~94 ms for 32-of-45.
• Success Rate: The observed success rate is 21–45%, comparable to or slightly better than single-signer ML-DSA (20–25%). The Irwin-Hall distribution concentrates more mass near zero, increasing the probability of passing the rejection sampling check.
• Scalability: The scheme scales effectively up to $T=32$ and beyond (up to $T=128$ with sub-3s latency for P3+), overcoming the $T \le 6$ limitation of short-coefficient LSSS schemes.

5. Significance

This work bridges a critical gap in post-quantum cryptography:

• Practical Deployment: It enables the use of ML-DSA in high-security, distributed environments (e.g., cryptocurrency custody, distributed PKI, government multi-party authorization) without sacrificing performance or standard compliance.
• Security Model Advancement: By proving security against dishonest majorities (in P2) and achieving statistical nonce privacy without the "two-honest" assumption, it sets a new standard for lattice-based threshold signatures.
• Standardization Readiness: The strict adherence to FIPS 204 formats ensures immediate interoperability with existing infrastructure, facilitating the transition to post-quantum security.

In summary, the paper presents a breakthrough in threshold cryptography by combining Shamir secret sharing structures with lattice-specific optimizations to achieve a practical, secure, and standards-compliant post-quantum signature scheme.