TALUS: FIPS-204-Exact Threshold ML-DSA via Boundary Clearance
About
We present TALUS, a threshold signing protocol for ML-DSA (FIPS 204) that supports an arbitrary number of parties, emits signatures accepted by any unmodified ML-DSA verifier, and reduces, for a bounded number of signatures per key, to ML-DSA's own assumptions (Module-LWE and SelfTargetMSIS). Its core is the Boundary Clearance Condition (BCC): for a constant fraction of nonces (31.7% at ML-DSA-65), the secret vector s2 provably cannot cross a rounding boundary, so the s2-dependent rejection check can be enforced offline on preprocessed nonces. This removes the interaction that forces multi-round signing in prior schemes, yielding a TEE-assisted one-round profile and a fully distributed honest-majority MPC profile with two online rounds, both built on a Carry Elimination Framework that computes the shared commitment w1 = HighBits(Ay) on secret shares, a step we show is unavoidable. We prove a lower bound: any FIPS-204-exact threshold scheme revealing a summed (Irwin-Hall) nonce admits an efficient key-recovery attack after about 2^30 signatures under one key (at ML-DSA-65), so no q_s-independent unforgeability is possible for this class. Complementing it, a q_s-bounded analysis certifies over 105 bits at the operational signing cap for the external view, with insider ceilings disclosed per view and a mandatory key rotation capping each key's signing lifetime. A Rust implementation across all three FIPS 204 levels and a hardware-validated single-party core demonstrates practicality.
Related benchmarks
| Task | Dataset | Result | Rank | |
|---|---|---|---|---|
| Threshold Digital Signature | ML-DSA FIPS 204 | -- | 9 | |
| Threshold Digital Signature | ML-DSA-44 FIPS 204 | Amortised Signing Latency (ms)0.62 | 5 | |
| Threshold Digital Signature | ML-DSA-65 FIPS 204 | Amortised Signing Latency (ms)1.52 | 5 | |
| Threshold Digital Signature Signing | ML-DSA-44 | Online Latency (ms)0.16 | 3 | |
| Threshold Digital Signature Signing | ML-DSA-65 | Online Time (ms)0.29 | 3 | |
| Threshold Digital Signature Signing | ML-DSA-87 | Online Latency (ms)0.41 | 3 |