International Association
for Cryptologic Research

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$.