Abstract
This paper introduces the first provably secure, two-round distributed signature schemes based on lattice problems. By integrating a novel lattice-based trapdoor commitment scheme, the authors address the "leakage via aborts" challenge inherent in Fiat-Shamir with Aborts (FSwA) paradigms. The resulting $n$-out-of-$n$ and multi-signature schemes are secure against quantum adversaries and maintain high efficiency, providing a practical path for post-quantum distributed cryptography.
Introduction
Distributed signatures, where multiple parties cooperate to sign a message, are critical for blockchain security and high-stakes administrative tasks. While current protocols often rely on discrete logarithm problems (e.g., ECDSA, Schnorr), these are vulnerable to quantum computing. Transitioning to lattice-based signatures is non-trivial due to the Fiat-Shamir with Aborts (FSwA) paradigm. In FSwA, signers may need to abort to prevent secret key leakage. In a distributed setting, a partial contribution shared before an abort can still leak sensitive data. Previous solutions either required excessive communication rounds or lacked rigorous security proofs.
Methods
The authors build upon Dilithium-G, a variant of the NIST-standardized Dilithium signature scheme. To achieve a two-round protocol, they utilize two key cryptographic innovations:
- Homomorphic Commitments: Parties send additively homomorphic commitments of their initial messages. This allows them to sum contributions into a joint value without revealing individual data until the "abort" risk is cleared.
- Lattice-Based Trapdoor Commitments: Using the "Micciancio-Peikert" technique, the authors developed a trapdoor commitment scheme. This enables "straight-line simulation" in security proofs, allowing a simulator to modify a commitment after it has been sent—a crucial step for proving security against malicious actors in just two rounds.
The security of these protocols rests on the Module-LWE (Learning With Errors) and Module-SIS (Short Integer Solution) problems. To prevent "Wagner-style" generalized birthday attacks, the authors derive unique commitment keys for every message, ensuring robustness across multiple signature executions.
Key Results
The research yields two primary protocols: $DS_2$ (a two-round $n$-out-of-$n$ scheme) and $MS_2$ (a two-round multi-signature scheme). Both are proven secure in the Classical Random Oracle Model (ROM) against rushing adversaries.
As shown in the comparison table, the proposed $DS_2$ and $MS_2$ schemes achieve a minimal 2-round complexity while relying on standard lattice assumptions (MLWE & MSIS). While signature sizes are slightly larger than single-user Dilithium due to commitment openings, they scale by a factor of $O(\log n)$, remaining practical for real-world deployment.
Conclusion and Future Work
This work provides a significant advancement in post-quantum distributed signatures. Future research directions include proving security in the Quantum Random Oracle Model (QROM), further optimizing signature sizes (potentially using NTRU-based assumptions), and developing tighter security reductions to avoid the quadratic loss associated with the Forking Lemma.
Summary updated