Technical Summary: TALUS – Threshold ML-DSA with One-Round Online Signing

1. Problem Statement

Deploying ML-DSA (FIPS 204, based on CRYSTALS-Dilithium) in a threshold setting has remained an open problem due to the scheme's inherent non-linear rounding step. Unlike classical threshold signatures (e.g., FROST for Schnorr/ECDSA) which rely on additive homomorphism, ML-DSA requires a check on a secondary residual $r_0 - cs_2$ to ensure the signature hint remains within bounds. In a threshold setting, the secret key component $s_2$ is shared among parties. Prior approaches to handle this $r_0$-check have required:

1. Expensive MPC: Multi-party computation to evaluate $cs_2$ online.
2. Trusted Coordinators: Holding $s_2$ in a Trusted Execution Environment (TEE) or a single trusted party.
3. Noise Flooding: Degrading parameters to mask the check.

These methods either increase online latency (multiple rounds), restrict the trust model, or degrade security parameters. Furthermore, a fundamental "Lattice Threshold Trilemma" exists: no group homomorphism from the nonce space can simultaneously be hiding and binding, ruling out standard homomorphic commitment schemes used in discrete-log settings.

2. Methodology and Core Innovations

TALUS (Threshold Agile Lattice Unified Signatures) overcomes these barriers by decoupling the $r_0$-check from the online signing phase and solving the distributed commitment problem via a new algebraic framework.

2.1 Boundary Clearance Condition (BCC)

The paper identifies a geometric property of the ML-DSA commitment space. The signing process involves a residual $r_0 = \text{LowBits}(Ay)$. The secret-dependent shift $cs_2$ can only cause a rounding boundary crossing if $r_0$ is close to the modular boundaries ($\pm \gamma_2$).

• Observation: If every coefficient of $r_0$ is bounded away from the boundaries by more than $\beta = \tau\eta$ (where $\tau$ is the challenge weight and $\eta$ is the secret bound), then the shift $cs_2$ cannot cross any boundary.
• Implication: Under this Boundary Clearance Condition (BCC), the high-order part of the commitment ($w_1$) remains unchanged by $s_2$, and the hint $h$ becomes computable entirely from public values ($r = Az - ct_1 \cdot 2^d$ and $w_1$).
• Probability: BCC holds with probability $p_{BCC} \approx 31.7\%$ per nonce attempt.
• Strategy: TALUS performs offline preprocessing to generate nonces satisfying BCC. This filters out "bad" nonces before the online phase, eliminating the need to compute $cs_2$ or check $r_0$ during signing.

2.2 Carry Elimination Framework (CEF)

Even with BCC, parties must compute the commitment hash input $w_1 = \text{HighBits}(Ay)$ distributedly. Since $\text{HighBits}$ is not a group homomorphism, summing individual shares $w_{1,i}$ introduces "carries" that must be resolved without reconstructing the full nonce $y$.

• Key Identity: The paper exploits the modular identity $\alpha^{-1} \equiv -16 \pmod q$ (where $\alpha = 2\gamma_2$).
• Protocol:
  • TALUS-TEE: A trusted coordinator (in a TEE) holds the aggregate nonce and computes $w_1$ directly.
  • TALUS-MPC: Parties use a Carry-Safe Comparison Protocol (CSCP). They broadcast masked decompositions of their additive nonce pieces. Using Beaver triples and a prefix-tree comparison circuit, the parties compute a single carry bit $c$ and a FIPS correction bit $\delta$. This allows the coordinator to reconstruct the exact $w_1$ without learning the individual low-bits of the nonce.
• Efficiency: For $T=2$, this degenerates to a Distributed Comparison Function (DCF), reducing communication significantly. For $T \ge 3$, it requires $O(\log N)$ offline rounds but remains independent of the online phase.

3. Protocol Instantiations

The paper presents two deployment profiles:

TALUS-TEE (Trusted Execution Environment)

• Model: A coordinator holds $s_2$ and $t_0$ inside a TEE. Signers hold shares of $s_1$.
• Process: The TEE performs offline preprocessing to find a BCC-compliant nonce. It broadcasts $w_1$. Signers respond with $z_i = y_i + c \cdot s_{1,i}$. The TEE assembles the signature.
• Trust: Requires a semi-honest TEE coordinator; signers can be malicious (identifiable abort).
• Constraints: No honest-majority requirement ($N \ge T$).

TALUS-MPC (Fully Distributed)

• Model: Fully distributed; no party holds $s_2$ or the aggregate nonce.
• Process: Parties jointly compute $w_1$ via the CEF during offline preprocessing. Online signing is identical to TEE (one round).
• Trust: Malicious security with Identifiable Abort (IA) for $T \ge 2$.
• Constraints: For $T \ge 3$, requires an honest majority ($N \ge 2T - 1$) to prevent a rushing adversary from learning the low-bits of the nonce (The "Dishonest Majority Barrier"). For $T=2$, no honest majority is required.

4. Key Contributions

1. Lattice Threshold Trilemma: A proof that no group homomorphism from the lattice nonce space can be simultaneously hiding and binding. This establishes that carry resolution is a mathematical necessity for FIPS-compatible lattice threshold schemes, not a protocol artifact.
2. Boundary Clearance Condition: A formal proof that the $r_0$-check can be bypassed for $\approx 31.7\%$ of nonces, allowing the elimination of $s_2$ computation in the online phase.
3. Carry Elimination Framework: A distributed protocol to compute $\text{HighBits}(Ay)$ without reconstructing $y$, utilizing the specific modular arithmetic properties of ML-DSA.
4. One-Round Online Signing: Both variants achieve a single broadcast round for online signing, matching the latency of single-party signing and outperforming prior FIPS-compatible proposals (e.g., Mithril, Quorus) which require 2–3 rounds.
5. Implementation: A Rust reference implementation across all three FIPS 204 security levels (ML-DSA-44, 65, 87).

5. Results and Performance

• Success Rate: The expected number of preprocessing attempts per successful signature is $\approx 3.15$ (due to the $31.7\%$ BCC pass rate).
• Latency (ML-DSA-65, $T=3$):
  • TALUS-TEE: Online signing takes 0.29 ms; amortized total (including offline prep) is 1.52 ms.
  • TALUS-MPC: Online signing takes 0.68 ms; amortized total is 4.09 ms.
  • Comparison: TALUS-TEE is 2.4x faster than Mithril (3.6 ms) in online latency. TALUS-MPC is competitive with Mithril but achieves this with a single online round versus Mithril's 3 rounds.
• Communication:
  • T=2: Offline cost is $\approx 5$ KB per batch (DCF).
  • T $\ge$ 3: Offline cost is $\approx 350$ KB per batch (dominated by CarryCompare).
  • Online: Constant at $\approx 3.6$ KB per signer, independent of $T$ and $N$.
• Network Latency: In distributed experiments (GCP), end-to-end latency scales linearly with network RTT (e.g., $\approx 350$ ms for US-Europe), confirming the single-round advantage.

6. Significance and Claims

The paper claims TALUS is the first threshold ML-DSA construction to simultaneously achieve:

1. Full FIPS 204 Compatibility: Signatures are verifiable by unmodified standard verifiers.
2. Arbitrary Threshold: Supports $T$-of-$N$ for any $1 \le T \le N$ (with specific honest-majority constraints for MPC $T \ge 3$).
3. One-Round Online Signing: Matches the latency of single-party signing, a significant improvement over prior works requiring multiple online rounds.

The authors emphasize that the "carry cost" is an inherent algebraic price of the lattice setting, but TALUS minimizes this cost by moving it entirely to the offline phase. The work demonstrates that FIPS 204 compatibility does not necessitate a performance penalty in threshold settings.

Note on Cryptanalysis: The paper includes a note (dated 2026-07-09) acknowledging a cryptanalysis by G. Niot. The attacks confirm that the commitment scheme in TALUS-MPC is not hiding (recovering $x$ from $Ax$) and that the removal of the $s_2$ check introduces statistical leakage. The authors concede these points, withdraw specific claims regarding the hiding of $As_{1,i}$ and the redundancy of the $s_2$ check for secrecy, and state that a revised construction using genuinely hiding commitments is in preparation. They note that TALUS-TEE is not affected by the commitment attacks.