TALUS: Threshold ML-DSA with One-Round Online Signing via Boundary Clearance and Carry Elimination
This solves the open problem of threshold signing for ML-DSA, enabling secure distributed signatures for applications like blockchain and multi-party authentication.
The paper tackles the problem of deploying ML-DSA in threshold settings by presenting TALUS, which achieves one-round online signing with >99% success and produces standard signatures verifiable by any unmodified ML-DSA verifier, with implementations showing signing times of 0.62–1.94 ms for TALUS-TEE and 2.27–5.02 ms for TALUS-MPC.
Deploying ML-DSA (FIPS 204) in threshold settings has remained an open problem: the scheme's inherently non-linear rounding step defeats the additive share techniques that underpin practical threshold schemes for elliptic-curve signatures such as FROST. We present TALUS, the first threshold ML-DSA construction that achieves one-round online signing with >99% online success, while producing standard signatures verifiable by any unmodified ML-DSA verifier. We formalise this as the Lattice Threshold Trilemma, proving that no group homomorphism from the ML-DSA nonce space into any abelian group can simultaneously be hiding and binding, ruling out all possible homomorphic commitment schemes. TALUS overcomes this barrier with two techniques. The Boundary Clearance Condition (BCC) identifies nonces whose rounding residuals lie far enough from modular boundaries that the secret key component s2 has no effect on the signature; such nonces (approximately 31.7% of attempts) are filtered during offline preprocessing. The Carry Elimination Framework (CEF) then enables parties to compute the commitment hash input distributedly, without reconstructing the full nonce product. Together, BCC and CEF reduce online signing to a single broadcast round: each party sends one message and the coordinator assembles a valid FIPS 204 signature. We instantiate TALUS in two deployment profiles: TALUS-TEE (trusted execution environment, T-of-N) and TALUS-MPC (fully distributed, malicious security with identifiable abort for T >= 2). Security of both variants reduces to ML-DSA EUF-CMA. A Rust implementation across all three FIPS 204 security levels (ML-DSA-44, ML-DSA-65, ML-DSA-87) shows that TALUS-TEE completes a signing operation in 0.62--1.94 ms and TALUS-MPC in 2.27--5.02 ms (amortised, T=3), competitive with the fastest concurrent threshold ML-DSA proposals.