Paper 2023/276

Threshold and Multi-Signature Schemes from Linear Hash Functions

Stefano Tessaro, University of Washington
Chenzhi Zhu, University of Washington

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.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Threshold SignaturesMulti-SignaturesDL AssumptionRSA Assumption
Contact author(s)
tessaro @ cs washington edu
zhucz20 @ cs washington edu
2023-02-27: approved
2023-02-24: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.