Paper 2023/276

Threshold and Multi-Signature Schemes from Linear Hash Functions

Stefano Tessaro, University of Washington
Chenzhi Zhu, University of Washington
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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Keywords
Threshold SignaturesMulti-SignaturesDL AssumptionRSA Assumption
Contact author(s)
tessaro @ cs washington edu
zhucz20 @ cs washington edu
History
2023-02-27: approved
2023-02-24: received
See all versions
Short URL
https://ia.cr/2023/276
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/276,
      author = {Stefano Tessaro and Chenzhi Zhu},
      title = {Threshold and Multi-Signature Schemes from Linear Hash Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/276},
      year = {2023},
      url = {https://eprint.iacr.org/2023/276}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.