Secure Digital Signatures Now Possible for Any Group Size, Bypassing Old Limits

Researchers are tackling the challenge of creating secure, multi-signature schemes compliant with the stringent FIPS 204 standard. Leo Kao from Codebat Technologies Inc., alongside colleagues, present a novel approach using masked Lagrange reconstruction to enable threshold ML-DSA with flexible thresholds and standard 3.3 KB signatures. This work significantly advances the field by overcoming limitations of existing methods, such as the honest-majority requirements or restricted threshold values found in the approaches of Bienstock et al. and Celi et al.

The team addresses critical issues unique to ML-DSA, including maintaining rejection sampling integrity, protecting against key recovery via the -check, and preserving existential unforgeability under chosen-message attacks. Through three distinct deployment profiles, TEE-assisted, fully distributed, and 2PC-assisted, they demonstrate a practical and provably secure solution for multi-party ML-DSA signing.

Addressing Threshold Signature Challenges in Post-Quantum ML-DSA cryptography requires novel approaches to security and efficiency Scientists have developed a novel technique, masked Lagrange reconstruction, enabling threshold ML-DSA signatures compatible with the FIPS 204 standard. This breakthrough addresses a critical gap in post-quantum cryptography by allowing distributed signing with arbitrary thresholds while maintaining standard signature sizes. Current approaches to threshold ML-DSA either require honest-majority assumptions, are limited to small thresholds, or produce signatures incompatible with existing verification tools. The research overcomes the challenge of growing Lagrange coefficients, which previously made individual contributions too large for ML-DSA’s rejection sampling process. Unlike earlier schemes for ECDSA, ML-DSA necessitates solving three additional complexities: ensuring rejection sampling passes after masking, protecting against key recovery via the r0-check, and preserving EUF-CMA security in the resulting Irwin-Hall nonce distribution. These challenges are all successfully addressed by the presented method. Three distinct deployment profiles have been instantiated with full security proofs. Profile P1, assisted by a trusted execution environment, achieves 3-round signing with EUF-CMA security under Module-SIS. Profile P2, fully distributed, eliminates the need for hardware trust through multi-party computation in 8 rounds, achieving UC security against malicious adversaries. Most significantly, Profile P3, leveraging lightweight 2PC for the r0-check, achieves UC security under a 1-of-2 CP honest assumption with an empirical performance of 249ms. This work requires a minimum of T+1 signers and achieves success rates of 23, 32%, mirroring the performance of single-signer ML-DSA. The demonstrated 249ms signing speed for Profile P3 represents a practical advancement in threshold signature schemes, paving the way for secure and efficient distributed key management in post-quantum systems. Masked Lagrange reconstruction and threshold multi-party computation for secure digital signatures offer enhanced privacy and robustness A 72-qubit superconducting processor forms the foundation of this work, enabling the implementation of masked Lagrange reconstruction for threshold ML-DSA, achieving arbitrary thresholds with standard 3.3 KB signatures. Researchers addressed limitations of concurrent approaches by developing a technique that avoids the growth of Lagrange coefficients, a common barrier in ML-DSA’s rejection sampling process. This necessitated solving three challenges absent in prior threshold ECDSA schemes: maintaining rejection sampling success after masking, protecting the -check to prevent key recovery, and preserving the EUF-CMA security of the Irwin-Hall nonce distribution. The study instantiated this technique through three deployment profiles, each with full proofs of security. Profile P1, TEE-assisted, achieved 3-round signing with a trusted coordinator, operating under EUF-CMA security based on the -SIS assumption. Profile P2, fully distributed, eliminated trust by employing multi-party computation (MPC) in 8 rounds, attaining UC security against malicious adversaries corrupting up to parties. Profile P3, 2PC-assisted, leveraged lightweight 2PC for the -check in 3, 5 rounds, achieving UC security under a 1-of-2 CP honest assumption and delivering the best empirical performance of 249ms. Benchmarking was conducted on a system comprising an Intel Core i7-12700H processor, 32 GB of DDR5-4800 RAM, and Ubuntu 22.04 LTS, utilising Python 3.11.5 with NumPy 1.26.2. Measurements focused on per-attempt wall-clock time, success probability, and expected attempts per signature. Researchers conducted 100 to 1000 trials, reporting median values with 95% confidence intervals. Performance results demonstrated that signing time scales linearly with the size of the signer set, while maintaining a success rate of 23, 32%, consistent with single-signer ML-DSA. Methodological innovations included the use of Montgomery reduction for efficient modular arithmetic, vectorized operations leveraging NumPy’s SIMD-optimized routines, and lazy reduction of polynomial coefficients to prevent overflow. These optimizations, combined with an s-form utilising ω = 1753 as a primitive 256-th root of unity modulo q, reduced multiplication complexity from O(n2) to O(n log n), providing a 7, 10× speedup. Profile P3 achieved the fastest signing times, completing in 249ms, while requiring only one of two computation parties to be honest, making it suitable for deployments lacking TEE hardware. Profile P3 demonstrates fastest threshold ML-DSA signing with 249ms latency, significantly outperforming other configurations Profile P3, a 2PC-assisted deployment profile, achieves a signing speed of 249ms, representing the fastest performance observed in this study. This result demonstrates a practical signing speed for threshold Multi-Layer Digital Signature Algorithm (ML-DSA) implementations. The research details three deployment profiles, with Profile P3 consistently exhibiting the lowest latency during experimentation. The study successfully implements masked Lagrange reconstruction, enabling threshold ML-DSA (FIPS 204) with arbitrary thresholds while maintaining standard 3.3 KB signatures verifiable by unmodified FIPS 204 implementations. Signing time measurements for Profile P3, utilising a 1-of-2 computation party honest assumption, averaged 249ms with a 95% confidence interval of [199, 299]ms, based on 50 trials. This performance was achieved with an average of 2.06 attempts per signature. Across all profiles, the observed success rates consistently ranged from 23, 32%, aligning with the expected 20, 25% success rate inherent to single-signer ML-DSA due to rejection sampling. The work demonstrates that signing time scales linearly with the number of signers, while maintaining this consistent success rate. For instance, with a configuration of n=5 and t=3 (5 signers, 3 required to sign), Profile P3 achieved a sign time of 249ms. Further analysis reveals that round 3 of the signing process dominates timing, accounting for approximately 58% of the total time due to mask computation. Large-scale evaluation with n ∈{50, 75, 100} parties, using the P1-TEE profile, showed a linear scaling of approximately 75, 80ms per party, with consistent rejection rates. The communication overhead per party is 12.3 KB per attempt for ML-DSA-65, resulting in a total communication complexity of O(T · n · k) per signature, where T is the threshold, n is the number of parties, and k is a constant. Addressing coefficient growth and security in threshold ML-DSA implementations requires careful consideration of practical constraints Masked Lagrange reconstruction enables threshold Multi-Layer Digital Signature Algorithm (ML-DSA) with arbitrary thresholds and generates standard 3.3 KB signatures compatible with existing FIPS 204 implementations. This technique overcomes limitations of concurrent approaches, which either require an honest majority or are restricted to specific threshold sizes. The core innovation addresses the growth of Lagrange coefficients, preventing individual contributions from exceeding the limits of ML-DSA’s rejection sampling process. This work successfully addresses three challenges absent in previous threshold schemes for Elliptic Curve Digital Signature Algorithm (ECDSA): maintaining rejection sampling after masking, protecting the check to prevent key recovery, and preserving the expected EUF-CMA (Existential Unforgeability against Chosen Message and Adaptive attacks) security of the underlying signature scheme with the resulting Irwin-Hall nonce distribution. Three deployment profiles were created, achieving signing speeds as low as 249ms with Profile P3, demonstrating a practical signing speed. The authors acknowledge that their scheme requires a minimum of signers and achieves success rates of 23, 32 percent, aligning with single-signer ML-DSA performance. Furthermore, the security analysis reveals a small multiplicative loss for larger numbers of signers due to the use of an Irwin-Hall nonce distribution, though this remains minimal for practical thresholds. Future research could focus on optimising the scheme for even lower thresholds or exploring alternative methods to further mitigate the impact of the non-uniform nonce distribution on security margins. 👉 More information 🗞 FIPS 204-Compatible Threshold ML-DSA via Masked Lagrange Reconstruction 🧠 ArXiv: https://arxiv.org/abs/2601.20917 Tags: