Paper 2023/1318

Two-Round Threshold Lattice Signatures from Threshold Homomorphic Encryption

Kamil Doruk Gur, University of Maryland, College Park
Jonathan Katz, University of Maryland, College Park
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. based on lattices that support only the full threshold case (i.e., $t=n$). We show here a two-round threshold signature scheme based on standard lattice assumptions that support arbitrary thresholds $t\leq n$. Estimates of our scheme's performance at the $128$-bit security level with a trusted setup show that in the $3$-out-of-$5$ case, we obtain signatures of size $11.5$ KB and public keys of size $13.6$ KB, with an execution of the signing protocol using roughly $1.5$ MB of communication per party. We achieve improved parameters if only a small bounded number of signatures are ever issued with the same key. As an essential building block and independent contribution, we construct a maliciously secure threshold (linearly) homomorphic encryption scheme that supports arbitrary thresholds $t \leq n$.

Available format(s)
Cryptographic protocols
Publication info
Lattice-Based CryptographyThreshold SignaturesThreshold Homomorphic EncryptionZero-Knowledge Proofs
Contact author(s)
dgur1 @ cs umd edu
jkatz2 @ gmail com
tjerand silde @ ntnu no
2023-09-08: approved
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 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.