Efficient Threshold ML-DSA

Threshold signature schemes allow a group of users to jointly generate a digital signature, providing resilience against faults and enhancing decentralization. With the advent of post-quantum cryptography, lattice-based threshold signatures have gained attention as viable PQ-threshold solutions. Nevertheless, existing constructions are limited in terms of their scalability, robustness. Worse, none is compatible with standardized schemes, particularly with the NIST-selected and standardized Module-Lattice-based Digital Signature Algorithm (ML-DSA) algorithm. In this work, we present the first threshold signature scheme that is fully compatible with ML-DSA, supporting secure and efficient signing for a small number of parties, with an average communication per party upper bounded by 1 MB up to 6 parties. Our construction leverages advanced short secret sharing techniques and integrates optimized rejection sampling to achieve a favorable balance between communication efficiency and correctness in distributed environments. We implement our construction in Go and evaluate its performance across local, LAN, and WAN network settings. Our benchmarks demonstrate that our threshold ML-DSA scheme is not only practically deployable but also well-suited for real-world applications, including multi-device cryptocurrency wallets, threshold-based TLS authentication, and for Tor's directory authorities. Threshold signatures In all this work, we denote the security parameter by κ. Following the syntax of Katsumata et al. [46], a R-round threshold signature (without session identifiers) is as a tuple TSS = (Setup, Keygen, (Sign i ) i∈[R] , Combine, Verify). act ⊆ [N] denotes a set of T parties used for signing. Each signer i maintains a state st i : short-lived session-specific information. Setup(κ, N, T ) → pp. Takes as input a security parameter κ, the total number of parties N, the reconstruction threshold T ⩽ N. Outputs a set of public parameters pp. Keygen(pp) → (vk, (sk i ) i∈ [N] ). Takes as input the public parameters. Outputs a verification key vk, and partial private keys Sign r (vk, act, msg, (pm j r-1 ) j∈act , i, sk i , st i ) → (pm i r , st i ). For the r-th round (r ∈ 1, • • • , R), takes as input the verification key vk, the set of signers act, a message msg, the protocol messages exchanged during the previous round (pm j r-1 ) j∈act , as well as the partial private key sk i and state st i of user i. Outputs a new message pm i r and updated state st i . We define pm i 0 = ⊥. Note that msg and act may optionally be provided only from a round later than the first. Combine(vk, act, msg, (pm i r ) r∈[R],i∈act ) → sig. Takes as input the verification key vk, the set of signers act, the message msg, all messages exchanged during the protocol (pm i r ) r∈[R],i∈act . Outputs a signature sig. Verify(vk, msg, sig) → 0 or 1. Takes as input a verification key vk, a message msg, and a signature sig. Outputs 1 if sig is valid and 0 otherwise.