Paper 2022/634

Round-Optimal Lattice-Based Threshold Signatures, Revisited

Shweta Agrawal, Damien Stehle, and Anshu Yadav


Threshold signature schemes enable distribution of the signature issuing capability to multiple users, to mitigate the threat of signing key compromise. Though a classic primitive, these signatures have witnessed a surge of interest in recent times due to relevance to modern applications like blockchains and cryptocurrencies. In this work, we study round-optimal threshold signatures in the post- quantum regime and improve the only known lattice-based construction by Boneh et al [CRYPTO’18] as follows: • Efficiency. We reduce the amount of noise flooding used in the construction from $2^{\Omega(\lambda)}$ down to $\sqrt{Q}$, where $Q$ is the bound on the number of generated signatures and $\lambda$ is the security parameter. By using lattice hardness assumptions over polynomial rings, this allows to decrease the signature bit-lengths from $\widetilde{O}(\lambda^3)$ to~$\widetilde{O}(\lambda)$, bringing them significantly closer to practice. Our improvement relies on a careful analysis using Rényi divergence rather than statistical distance in the security proof. • Instantiation. The construction of Boneh et al requires a standard signature scheme to be evaluated homomorphically. To instantiate this, we provide a homomorphism-friendly variant of Lyubashevsky’s signature [EUROCRYPT ’12] which achieves low circuit depth by being “rejection-free” and uses an optimal, moderate noise flooding of $\sqrt{Q}$, matching the above. • Towards Adaptive Security. The construction of Boneh et al satisfies only selective security, where all the corrupted parties must be announced before any signing query is made. We improve this in two ways: in the Random Oracle Model, we obtain partial adaptivity where signing queries can be made before the corrupted parties are announced but the set of corrupted parties must be announced all at once. In the standard model, we obtain full adaptivity, where parties can be corrupted at any time but this construction is in a weaker pre-processing model where signers must be provided correlated randomness of length proportional to the number of signatures, in an offline preprocessing phase.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.Leibniz International Proceedings in Informatics (LIPIcs) series
Post-Quantum CryptographyLatticesThreshold Signatures
Contact author(s)
shweta a @ cse iitm ac in
damien stehle @ ens-lyon fr
anshu yadav06 @ gmail com
2022-05-23: received
Short URL
Creative Commons Attribution


      author = {Shweta Agrawal and Damien Stehle and Anshu Yadav},
      title = {Round-Optimal Lattice-Based Threshold Signatures, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2022/634},
      year = {2022},
      doi = {10.4230/LIPIcs.ICALP.2022.41},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.