Paper 2023/1318

Two-Round Threshold Lattice-Based Signatures from Threshold Homomorphic Encryption

Kamil Doruk Gur, University of Maryland, College Park
Jonathan Katz, Google (United States)
Tjerand Silde, Norwegian University of Science and Technology

Much recent work has developed efficient protocols for threshold signatures, where $n$ parties share a signing key and some threshold $t$ of those parties must interact to produce a signature. Yet efficient threshold signatures with post-quantum security have been elusive, with the state-of-the-art being a two-round scheme by Damgård et al. (PKC'21) based on lattices that supports only the full threshold case (i.e., $t=n$). We show here a two-round threshold signature scheme based on standard lattice assumptions that supports arbitrary thresholds $t\leq n$. Estimates of our scheme's performance at the $128$-bit security level show that in the 3-out-of-5 case, we obtain signatures of size $46.6$ KB and public keys of size $13.6$ KB. We achieve $\approx 5\times$ improved parameters if only a small number of signatures are ever issued with the same key. As an essential building block and independent contribution, we construct an actively secure threshold (linearly) homomorphic encryption scheme that supports arbitrary thresholds $t \leq n$.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. PQCrypto 2024
Lattice-Based CryptographyThreshold SignaturesThreshold Homomorphic EncryptionZero-Knowledge Proofs
Contact author(s)
dgur1 @ cs umd edu
jkatz2 @ gmail com
tjerand silde @ ntnu no
2024-04-13: last of 4 revisions
2023-09-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kamil Doruk Gur and Jonathan Katz and Tjerand Silde},
      title = {Two-Round Threshold Lattice-Based Signatures from Threshold Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1318},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.