International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Threshold and Multi-Signature Schemes from Linear Hash Functions

Authors:
Stefano Tessaro , University of Washington
Chenzhi Zhu , University of Washington
Download:
DOI: 10.1007/978-3-031-30589-4_22 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Abstract: This paper gives new constructions of two-round multi-signatures and threshold signatures for which security relies solely on either the hardness of the (plain) discrete logarithm problem or the hardness of RSA, in addition to assuming random oracles. Their signing protocol is partially non-interactive, i.e., the first round of the signing protocol is independent of the message being signed. We obtain our constructions by generalizing the most efficient discrete- logarithm based schemes, MuSig2 (Nick, Ruffing, and Seurin, CRYPTO ’21) and FROST (Komlo and Goldberg, SAC ’20), to work with suitably defined linear hash functions. While the original schemes rely on the stronger and more controversial one-more discrete logarithm assumption, we show that suitable instantiations of the hash functions enable security to be based on either the plain discrete logarithm assumption or on RSA. The signatures produced by our schemes are equivalent to those obtained from Okamoto’s identification schemes (CRYPTO ’92). More abstractly, our results suggest a general framework to transform schemes secure under OMDL into ones secure under the plain DL assumption and, with some restrictions, under RSA.
BibTeX
@inproceedings{eurocrypt-2023-32926,
  title={Threshold and Multi-Signature Schemes from Linear Hash Functions},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-30589-4_22},
  author={Stefano Tessaro and Chenzhi Zhu},
  year=2023
}