Threshold signature schemes enable a group of users to collaboratively produce digital signatures without revealing any individual share. With the current NIST post-quantum standardization underway, the lack of efficient and practical threshold variants of standardized schemes hinders adoption. We introduce the first threshold signature scheme compatible with the ML-DSA standard (Module-Lattice-based Digital Signature Algorithm), supporting up to 6 parties, while retaining efficient signing. Our work uses advanced short secret sharing techniques and optimized rejection sampling to balance communication and correctness in distributed settings. We implement our construction in Go and benchmark it in local, LAN, and WAN deployments. Results show that our threshold ML-DSA is both practical and compatible with real-world applications such as multi-device cryptocurrency wallets, threshold TLS, and Tor's directory authorities.
Threshold signature schemes enable a group of users to collaboratively produce digital signatures without revealing any individual share. With the current NIST post-quantum standardization underway, the lack of efficient and practical threshold variants of standardized schemes hinders adoption. We introduce the first threshold signature scheme compatible with the ML-DSA standard (Module-Lattice-based Digital Signature Algorithm), supporting up to 6 parties, while retaining efficient signing. Our work uses advanced short secret sharing techniques and optimized rejection sampling to balance communication and correctness in distributed settings. We implement our construction in Go and benchmark it in local, LAN, and WAN deployments. Results show that our threshold ML-DSA is both practical and compatible with real-world applications such as multi-device cryptocurrency wallets, threshold TLS, and Tor's directory authorities.
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.
Abstract The development of threshold protocols based on lattice-signature schemes has been of increasing interest in the past several years. The main research focus has been towards protocols constructed for various variants of Crystals-Dilithium, future NIST digital signature standard known as ML-DSA. In this work, we propose TOPCOAT, a two-party lattice-based signature algorithm that embodies Dilithium’s compression techniques. The aforesaid result is achieved by introducing a new hinting mechanism that allows parties to collaboratively calculate HighBits HighBits . Our hinting mechanism allows public key compression similar to Dilithium. Additionally, we suggest an optimization technique to minimize number of restarts both parties need to produce a valid signature. Our approach allows to produce ≈10 ≈ 10 KB signatures within 3 rounds of communication. We prove security of our scheme under MLWE and MSIS assumptions in ROM, and provide implementation of our proposed scheme. As additional contribution, we present vulnerabilities and inconsistencies found in Liu et al. work (Future Generation Computer Systems 2023) which aimed to construct distributed lattice-based signature protocol.
A threshold signature scheme splits the signing key amongℓparties, such that anyt-subset of parties can jointly generate signatures on a given message. Designing concretely efficient post-quantum threshold signatures is a pressing question, as evidenced by NIST's recent call. In this work, we propose, implement, and evaluate a lattice-based threshold signature scheme, Ringtail, which is the first to achieve a combination of desirable properties: (i) The signing protocol consists of only two rounds, where the first round is message-independent and can thus be preprocessed offline. (ii) The scheme is concretely efficient and scalable tot≤1024parties. For 128-bit security andt=1024parties, we achieve 13.4 KB signature size and 10.5 KB of online communication. (iii) The security is based on the standard learning with errors (LWE) assumption in the random oracle model. This improves upon the state-of-the-art (with comparable efficiency) which either has a three-round signing protocol [Eurocrypt'24] or relies on a new non-standard assumption [Crypto'24]. To substantiate the practicality of our scheme, we conduct the first WAN experiment deploying a lattice-based threshold signature, across 8 countries in 5 continents. We observe that an overwhelming majority of the end-to-end latency is consumed by network latency, underscoring the need for round-optimized schemes.
Threshold signatures allow a quorum of parties to jointly produce a signature while preventing any smaller subset from doing so. Following NIST's post-quantum standardization, designing threshold schemes compatible with the newly selected primitives is a pressing task. In particular, no prior threshold signature scheme produces signatures verifiable under the unmodified FALCON verification algorithm --- the NIST-selected post-quantum scheme with the smallest signatures and keys. In this work, we present the first such threshold FALCON signing protocol, establishing its feasibility. Our technical contributions are threefold. First, as required by FALCON's signing process, we extend prior works on MPC-based discrete Gaussian sampling protocol to support private centers and standard deviations. Second, we carry out a Rényi divergence analysis of the Klein sampler under fixed-point arithmetic, showing that 73 bits of precision suffice to achieve the same security as the FALCON specification. Third, we design an efficient MPC protocol for the Klein sampler that exploits the fixed trapdoor basis to construct a pseudorandom correlation generator for authenticated VOLE using only two-party DPFs, reducing per-signature communication significantly over standard authenticated triple generation. We implement and benchmark our protocol in two settings: N -party signing with all-but-one corruption, and 3-party signing with honest majority, demonstrating that threshold FALCON signing is feasible for applications where compatibility with the FALCON standard is required.
This article provides an expanded computational evaluation of three standardized lattice-based post-quantum signature schemes—ML-DSA-44, ML-DSA-65 and Falcon-512—using reference implementations from the Open Quantum Safe (liboqs) project. Unlike prior benchmarking efforts that rely on optimized implementations or hardware-specific tuning, this work focuses on reproducible baseline performance on a conventional CPU platform. We measure key generation, signing and verification times across 5,000 iterations and analyze the effect of message length on signing cost. Results confirm that ML-DSA variants achieve significantly faster signing and key generation, whereas Falcon-512 produces substantially smaller keys and signatures. The study further highlights the computational dominance of lattice operations over hashing, explaining the weak dependence of signing cost on message size. These findings aim to support system architects evaluating the practical feasibility of standardized post-quantum signature algorithms.
A threshold signature scheme distributes the ability to generate signatures through distributed key generation and signing protocols. A threshold signature scheme should be functionally interchangeable, meaning that a signature produced by a threshold scheme should be verifiable by the same algorithm used for non-threshold signatures. To resist future attacks from quantum adversaries, lattice-based threshold signatures are desirable. However, the performance of existing lattice-based threshold signing protocols is still far from practical. This paper presents the first lattice-basedt-out-of-nthreshold signature scheme with functional interchangeability that has been implemented. To build ant-out-of-naccess structure for arbitraryt≤n, we first present a novelt-out-of-nversion of the SPDZ MPC protocol. For high concrete efficiency, we avoid using the MPC protocol to evaluate hash operations. Moreover, we design an efficient distributed rejection sampling protocol. As a consequence, the online phase of our distributed signing protocol takes only 0.5 seconds in the two-party setting and 7.3 seconds in the 12-party setting according to our implementation. As a byproduct, our scheme also presents a periodic key refreshment mechanism and offers proactive security.