Two-round n-out-of-n and Multi-Signatures and Trapdoor Commitment from Lattices

Ivan Damgård, Claudio Orlandi, Akira Takahashi, Mehdi Tibouchi

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:

  1. 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.
  2. 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.
Comparison of the 3-round DS3 and 2-round DS2 protocols.

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.

Comparison of the proposed schemes with prior work in terms of rounds, assumptions, and building blocks.

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

BibTeX
@inproceedings{damgard2021two,
  author = {Ivan Damgård and Claudio Orlandi and Akira Takahashi and Mehdi Tibouchi},
  title = {{Two-round n-out-of-n and Multi-Signatures and Trapdoor Commitment from Lattices}},
  booktitle = {Public Key Cryptography},
  year = {2021},
  doi = {10.1007/978-3-030-75245-3\_5},
}
Figure