License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.8
URN: urn:nbn:de:0030-drops-163491
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16349/
Go to the corresponding LIPIcs Volume Portal

Agrawal, Shweta ; Stehlé, Damien ; Yadav, Anshu

Round-Optimal Lattice-Based Threshold Signatures, Revisited

pdf-format:
LIPIcs-ICALP-2022-8.pdf (0.9 MB)

Abstract

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^Ω(λ) down to √Q, where Q is the bound on the number of generated signatures and λ is the security parameter. By using lattice hardness assumptions over polynomial rings, this allows to decrease the signature bit-lengths from Õ(λ³) to Õ(λ), 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 √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.

BibTeX - Entry

@InProceedings{agrawal_et_al:LIPIcs.ICALP.2022.8,
  author =	{Agrawal, Shweta and Stehl\'{e}, Damien and Yadav, Anshu},
  title =	{{Round-Optimal Lattice-Based Threshold Signatures, Revisited}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16349},
  URN =		{urn:nbn:de:0030-drops-163491},
  doi =		{10.4230/LIPIcs.ICALP.2022.8},
  annote =	{Keywords: Post-Quantum Cryptography, Lattices, Threshold Signatures}
}

Keywords: Post-Quantum Cryptography, Lattices, Threshold Signatures
Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue Date: 2022
Date of publication: 28.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI