Paper 2024/449

Practical Lattice-Based Distributed Signatures for a Small Number of Signers

Nabil Alkeilani Alkadri, CISPA Helmholtz Center for Information Security
Nico Döttling, CISPA Helmholtz Center for Information Security
Sihang Pu, CISPA Helmholtz Center for Information Security

$n$-out-of-$n$ distributed signatures are a special type of threshold $t$-out-of-$n$ signatures. They are created by a group of $n$ signers, each holding a share of the secret key, in a collaborative way. This kind of signatures has been studied intensively in recent years, motivated by different applications such as reducing the risk of compromising secret keys in cryptocurrencies. Towards maintaining security in the presence of quantum adversaries, Damgård et al. (J Cryptol 35(2), 2022) proposed lattice-based constructions of $n$-out-of-$n$ distributed signatures and multi-signatures following the Fiat-Shamir with aborts paradigm (ASIACRYPT 2009). Due to the inherent issue of aborts, the protocols either require to increase their parameters by a factor of $n$, or they suffer from a large number of restarts that grows with $n$. This has a significant impact on their efficiency, even if $n$ is small. Moreover, the protocols use trapdoor homomorphic commitments as a further cryptographic building block, making their deployment in practice not as easy as standard lattice-based Fiat-Shamir signatures. In this work, we present a new construction of $n$-out-of-$n$ distributed signatures. It is designed specifically for applications with small number of signers. Our construction follows the Fiat-Shamir with aborts paradigm, but solves the problem of large number of restarts without increasing the parameters by a factor of $n$ and utilizing any further cryptographic primitive. To demonstrate the practicality of our protocol, we provide a software implementation and concrete parameters aiming at 128 bits of security. Furthermore, we select concrete parameters for the construction by Damgård et al. and for the most recent lattice-based multi-signature scheme by Chen (CRYPTO 2023), and show that our approach provides a significant improvement in terms of all efficiency metrics. Our results also show that the multi-signature schemes by Damgård et al. and Chen as well as a multi-signature variant of our protocol produce signatures that are not smaller than a naive multi-signature derived from the concatenation of multiple standard signatures.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Applied Cryptography and Network Security, 22nd International Conference, ACNS 2024, volume 14583, pp 376–402
n-out-of-n distributed signaturesthreshold n-out-of-n signaturesFiat-Shamir with abortslattice-based cryptography
Contact author(s)
nabil alkadri @ cispa de
doettling @ cispa de
sihang pu @ cispa de
2024-03-18: approved
2024-03-15: received
See all versions
Short URL
Creative Commons Attribution-ShareAlike


      author = {Nabil Alkeilani Alkadri and Nico Döttling and Sihang Pu},
      title = {Practical Lattice-Based Distributed Signatures for a Small Number of Signers},
      howpublished = {Cryptology ePrint Archive, Paper 2024/449},
      year = {2024},
      doi = {10.1007/978-3-031-54770-6_15},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.