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.
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 was 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. 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. 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 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.
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.
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.
Threshold signatures distribute trust across multiple parties, eliminating single points of failure and reducing insider and key-exfiltration risks—properties that are increasingly important for high-assurance deployments and recently emphasized by NIST’s Multi-Party Threshold Cryptography (MPTC) initiative. We present a practical t-out-of-n threshold variant and emulation of MAYO, a post-quantum signature candidate to NIST’s call for additional signatures. Our proposal builds upon the threshold MAYO design of Celi, Escudero and Niot (PQCrypto 2025), which we significantly refine to achieve practical performance. To this end, we introduce two algorithmic modifications to MAYO tailored for the distributed setting: (1) Explicit- Salt MAYO, which allows for pre-determined salts to enable a single-round online phase; and (2) Depth-Reduced MAYO, which restructures the signing algorithm to minimize the depth of secret-dependent operations. We then propose a unified protocol framework that integrate these techniques, plus other MPC specific optimizations, with the goal of minimizing online latency. Finally, we provide a concrete instantiation and local emulation in the dishonest majority setting, secure against active adversaries. Our emulation shows that threshold signing is practical at typical threshold sizes and amenable to deployment. By releasing an open-source implementation and reporting end-to-end performance, this work offers a concrete reference for the thresholdization of post-quantum signatures. Clearly the aforementioned framework is not limited to MAYO, and can be applied to the UOV family of signatures more generally.
Threshold signature schemes enable distribution of the signature issuing capability to multiple users, to mitigate the threat of signing key compromise. Though a classic primitive, these signatures have witnessed a surge of interest in recent times due to relevance to modern applications like blockchains and cryptocurrencies. In this work, we study round-optimal threshold signatures in the post-quantum regime and improve the only known lattice-based construction by Boneh et al. [CRYPTO'18] as follows: - Efficiency. We reduce the amount of noise flooding used in the construction from 2^Ω(λ) down to √Q, where Q is the bound on the number of generated signatures and λ is the security parameter. By using lattice hardness assumptions over polynomial rings, this allows to decrease the signature bit-lengths from Õ(λ³) to Õ(λ), bringing them significantly closer to practice. Our improvement relies on a careful analysis using Rényi divergence rather than statistical distance in the security proof. - Instantiation. The construction of Boneh et al. requires a standard signature scheme to be evaluated homomorphically. To instantiate this, we provide a homomorphism-friendly variant of Lyubashevsky’s signature [EUROCRYPT '12] which achieves low circuit depth by being "rejection-free" and uses an optimal, moderate noise flooding of √Q, matching the above. - Towards Adaptive Security. The construction of Boneh et al. satisfies only selective security, where all the corrupted parties must be announced before any signing query is made. We improve this in two ways: in the Random Oracle Model, we obtain partial adaptivity where signing queries can be made before the corrupted parties are announced but the set of corrupted parties must be announced all at once. In the standard model, we obtain full adaptivity, where parties can be corrupted at any time but this construction is in a weaker pre-processing model where signers must be provided correlated randomness of length proportional to the number of signatures, in an offline preprocessing phase.