Two-Round n-out-of-n and Multi-signatures and Trapdoor Commitment from Lattices

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Although they have been studied for a long time, distributed signature protocols have garnered renewed interest in recent years in view of novel applications to topics like blockchains. Most recent works have focused on distributed versions of ECDSA or variants of Schnorr signatures, however, and in particular, little attention has been given to constructions based on post-quantum secure assumptions like the hardness of lattice problems. A few lattice-based threshold signature and multi-signatureschemes have been proposed in the literature, but they either rely on hash-and-sign lattice signatures (which tend to be comparatively inefficient), use expensive generic transformations, or only come with incomplete security proofs.

In this paper, we construct several lattice-based distributed signing protocols with low round complexity followingthe Fiat–Shamir with Aborts (FSwA) paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed variants of the fast Dilithium-G signature scheme and the full security proof can be made assuming the hardness of module SIS and LWE problems. A key step to achieving security (unexplained in some earlier papers) is to prevent the leakage that can occur when parties abort after their first message—which can inevitably happen in the Fiat–Shamir with Aborts setting. We manage to do so using homomorphic commitments.

Exploiting the similarities between FSwA and Schnorr-style signatures, our approach makes the most of observations from recent advancements in the discrete log setting, such as Drijvers et al.’s seminal work on two-round multi-signatures (S&P 2019). In particular, we observe that the use of commitment not only resolves the subtle issue with aborts, but also makes it possible to realize secure two-round n-out-of-n distributed signing and multi-signature in the plain public key model, by equipping the commitment with a trapdoor feature. The construction of suitable trapdoor commitment from lattices is a side contribution of this paper.
Original languageEnglish
Title of host publicationPublic-Key Cryptography – PKC 2021: 24th IACR International Conference on Practice and Theory of Public Key Cryptography, Virtual Event, May 10–13, 2021, Proceedings, Part I
EditorsJuan A. Garay
PublisherSpringer, Cham
Number of pages32
ISBN (Electronic)978-3-030-75244-6
ISBN (Print)978-3-030-75245-3
Publication statusPublished - 1 May 2021
Event24th IACR International Conference on Practice and Theory of Public Key Cryptography - Online
Duration: 10 May 202113 May 2021

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Cham
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th IACR International Conference on Practice and Theory of Public Key Cryptography
Abbreviated titlePKC 2021
Internet address


Dive into the research topics of 'Two-Round n-out-of-n and Multi-signatures and Trapdoor Commitment from Lattices'. Together they form a unique fingerprint.

Cite this