This assessment is based on version 1 of this paper. Version 5 is now available on arXiv — the authors may have revised their methods, results, or conclusions.
TALUS: Threshold ML-DSA with One-Round Online Signing via Boundary Clearance and Carry Elimination
Leo Kao
Abstract
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.
AI Impact Assessments
(3 models)Scientific Impact Assessment: TALUS
1. Core Contribution
TALUS addresses a genuine open problem in post-quantum cryptography: how to perform threshold signing for ML-DSA (FIPS 204) with minimal online rounds while maintaining full compatibility with unmodified verifiers. The paper identifies two key innovations:
Boundary Clearance Condition (BCC): The central insight is elegant — when the low-order residual r₀ of the nonce commitment lies sufficiently far from modular boundaries (by more than β = τη), the secret-dependent correction term cs₂ cannot cause any coefficient to cross a rounding boundary. This means the r₀-check passes automatically without computing cs₂, eliminating the need for MPC on s₂. This holds with probability ≈31.7% per attempt, filterable during offline preprocessing.
Carry Elimination Framework (CEF): Exploits the identity α⁻¹ ≡ −16 (mod q) to enable distributed computation of w₁ = HighBits(Ay) without reconstructing the full nonce, using masked broadcasts and a single carry-bit comparison.
Lattice Threshold Trilemma: Formalizes that no group homomorphism from the ML-DSA nonce space can simultaneously be hiding and binding, proving that carry resolution is mathematically necessary (not a protocol artifact).
2. Methodological Rigor
The paper demonstrates substantial rigor in several dimensions:
Security proofs: Game-hopping reductions for both TALUS-TEE (5 games) and TALUS-MPC (6 games), reducing to ML-DSA EUF-CMA. UC proofs are provided in appendices. The concrete security bound of ≥85.3 bits for ML-DSA-65 at NIST Level 3 is explicitly computed, accounting for Irwin-Hall nonce distribution shift-invariance loss (quantified via exact FFT convolution).
Experimental validation: Monte Carlo experiments confirm theoretical predictions (BCC rate 0.3138 vs. theory 0.3166; carry identity 100% agreement over 10⁵ trials). GCP network experiments across three geographic scenarios demonstrate practical latency.
Concerns: The Trilemma theorem, while interesting, relies on perfect binding (injectivity), and Remark 3 argues this is necessary for threshold signing because malicious signers aren't restricted to short vectors. This argument is reasonable but somewhat informal — a more careful treatment of the computational vs. information-theoretic binding gap would strengthen the claim. The 85.3-bit concrete security (vs. 128-bit target) reflects inherent Fiat-Shamir reduction losses shared by all such schemes, but may concern practitioners. The paper's honest-majority requirement for TALUS-MPC with T≥3 (justified by Theorem 27) is a meaningful limitation.
3. Potential Impact
Practical deployment: The paper targets a real industrial need — NIST's post-quantum migration requires threshold variants for enterprise key management, HSMs, and custody systems. FIPS 204 compatibility is commercially critical. The two deployment profiles (TEE and MPC) cover distinct trust models.
Performance: TALUS-TEE at 0.62–1.94ms and TALUS-MPC at 2.27–5.02ms are competitive. The single online round is the key structural advantage — each saved round eliminates one full network RTT, which dominates in distributed deployments (demonstrated via GCP experiments: 350ms transatlantic vs. would-be ~510ms for 3-round protocols).
T=2 specialization: The DCF instantiation for T=2 with ~5KB offline communication (74× less than T≥3) is particularly impactful for the dominant 2-of-2 custody use case.
Broader influence: The BCC observation — that a probabilistic condition on public data can eliminate secret-dependent computation — is a conceptual contribution that could inspire similar approaches in other lattice-based protocols (the paper notes ML-KEM as a direction).
4. Timeliness & Relevance
This paper is highly timely. ML-DSA (FIPS 204) was standardized in 2024, and the threshold signing problem is an immediate practical need cited by NISTIR 8214. The concurrent works (Mithril, Quorus, Trilithium, Hermine) confirm this is an active research frontier. TALUS improves on all prior FIPS-compatible schemes in online round count, which is the critical metric for latency-sensitive applications.
5. Strengths & Limitations
Key Strengths:
Notable Limitations:
Summary
TALUS makes a strong contribution to a timely and practically important problem. The BCC observation is the paper's crown jewel — a clean structural insight that meaningfully advances the state of the art. The paper is thorough, well-organized, and backed by both formal proofs and experimental validation. The main caveats are the honest-majority requirement for MPC and the probabilistic nature of BCC success in the MPC variant.
Generated Mar 24, 2026
Comparison History (263)
FloatDoor opens an entirely new attack surface—platform-triggered backdoors exploiting floating-point non-determinism—that affects the rapidly growing ecosystem of LLM deployments across diverse hardware. Its novelty (first input-independent, platform-triggered backdoor), broad applicability (GPUs, TPUs, CPUs), and implications for model supply-chain security give it outsized cross-disciplinary impact spanning security, ML, and systems. TALUS is a strong cryptographic contribution solving an important threshold signing problem, but it addresses a narrower community (post-quantum threshold cryptography) and builds incrementally on known techniques for ML-DSA deployment.
Paper 2 (TALUS) likely has higher impact: it tackles an open, standard-relevant cryptographic problem—threshold ML-DSA (FIPS 204)—and delivers the first one-round online signing with standard, drop-in verifiable signatures. It adds a formal impossibility result (Lattice Threshold Trilemma) plus generally useful techniques (BCC, CEF), with rigorous security reductions and concrete implementations across all parameter sets. This has broad applicability to post-quantum secure infrastructure (HSMs, wallets, distributed key management) and is highly timely given ML-DSA standardization and deployment.
While Paper 1 offers an elegant, low-overhead solution for LLM security, Paper 2 tackles a fundamental open problem in post-quantum cryptography. By formalizing the Lattice Threshold Trilemma and introducing techniques to bypass the non-linear rounding step of ML-DSA, TALUS enables practical threshold signatures for the new FIPS 204 standard. This breakthrough provides foundational cryptographic infrastructure for future secure systems, giving it a profound and long-lasting scientific impact.
Paper 2 (TALUS) likely has higher impact: it solves a widely recognized open problem—practical thresholding of the NIST-standard ML-DSA—while preserving unmodified verifier compatibility, a key deployment constraint. It adds foundational theory (the Lattice Threshold Trilemma impossibility result) plus broadly applicable techniques (BCC/CEF) and provides concrete, competitive implementations across all FIPS 204 levels, directly relevant to imminent post-quantum infrastructure rollouts. Paper 1 is strong and timely for privacy-preserving compute, but its impact is narrower (accelerator/FHE stack) and more dependent on specialized hardware adoption.
Paper 1 solves a major open problem in post-quantum cryptography by enabling threshold signatures for the newly standardized ML-DSA. Its novel theoretical framework and practical techniques provide foundational contributions to cryptography. While Paper 2 offers a highly valuable applied security audit of a widely deployed system, Paper 1's foundational cryptographic innovations and alignment with new global standards suggest a deeper and longer-lasting scientific impact.
Paper 2 solves a critical open problem in post-quantum cryptography by enabling efficient threshold signing for the newly standardized ML-DSA (FIPS 204). This breakthrough directly facilitates the global transition to quantum-safe security infrastructure, offering immense real-world utility for securing distributed systems like certificate authorities and wallets. While Paper 1 provides a valuable systematization of privacy risks in synthetic data, Paper 2's fundamental cryptographic innovation and immediate, broad applicability in core security infrastructure give it a higher potential for foundational scientific impact.
Paper 2 likely has higher impact: it solves a key open problem—practical threshold signing for the newly standardized post-quantum ML-DSA (FIPS 204)—with a novel one-round online protocol, formal impossibility result (Lattice Threshold Trilemma), and concrete techniques (BCC, CEF) plus performant implementations. This has strong real-world applicability for wallets, HSMs, and distributed key management in PQC transitions, with broad cryptography/security relevance and timeliness due to standardization. Paper 1 is insightful for LLM security evaluation methodology, but its impact is more incremental and narrower in immediate deployability.
TALUS addresses a fundamental open problem in post-quantum cryptography—threshold signing for the NIST standard ML-DSA (FIPS 204). It provides a formal impossibility result (Lattice Threshold Trilemma) and novel techniques (BCC, CEF) to overcome it, achieving practical one-round online signing with standard-compatible signatures. The impact spans cryptography theory and practice, directly enabling distributed key management for a mandated post-quantum standard. AIRGuard is a solid systems-security contribution for LLM agent safety, but addresses a more incremental, application-specific problem with less fundamental theoretical depth and narrower long-term impact.
TALUS addresses a fundamental open problem in post-quantum cryptography—threshold ML-DSA signing—which is critical for the imminent transition to FIPS 204 standards. It proves an impossibility result (Lattice Threshold Trilemma) and provides novel techniques (BCC, CEF) to circumvent it, achieving practical performance with formal security reductions. The breadth of impact spans cryptography, security infrastructure, and standards compliance. ChainCaps addresses an important but more niche problem in AI agent safety with a practical engineering contribution. TALUS's theoretical depth, standards relevance, and foundational nature give it higher long-term scientific impact.
TALUS addresses a fundamental open problem in post-quantum cryptography—threshold signing for ML-DSA (FIPS 204), the NIST standard. It introduces a novel impossibility result (Lattice Threshold Trilemma) and overcomes it with new techniques (BCC, CEF), achieving one-round online signing with standard-compatible signatures. This has broad impact: post-quantum migration is urgent across industries, and threshold signing is critical for key management. Paper 1 (Heimdall) is solid engineering combining LLMs with formal verification for eBPF migration, but is more narrowly scoped to Linux kernel tooling. Paper 2's theoretical contributions and alignment with the global post-quantum transition give it higher impact potential.