One-More Unforgeability for Multi- and Threshold Signatures

Sela Navot; Stefano Tessaro

Paper 2024/1947

One-More Unforgeability for Multi- and Threshold Signatures

Sela Navot

, University of Washington

Stefano Tessaro

, University of Washington

Abstract

This paper initiates the study of one-more unforgeability for multi-signatures and threshold signatures as a stronger security goal, ensuring that ℓ executions of a signing protocol cannot result in more than ℓ signatures. This notion is widely used in the context of blind signatures, but we argue that it is a convenient way to model strong unforgeability for other types of distributed signing protocols. We provide formal security definitions for one-more unforgeability (OMUF) and show that the HBMS multi-signature scheme does not satisfy this definition, whereas MuSig and MuSig2 do. We also show that mBCJ multi-signatures do not satisfy OMUF, as well as expose a subtle issue with their existential unforgeability (which does not contradict their original security proof). For threshold signatures, we show that FROST satisfies OMUF, but ROAST does not.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in ASIACRYPT 2024
Keywords: multi-signatures threshold signatures strong unforgeability
Contact author(s): senavot @ cs washington edu
tessaro @ cs washington edu
History: 2024-12-02: revised; 2024-12-01: received; See all versions
Short URL: https://ia.cr/2024/1947
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1947,
      author = {Sela Navot and Stefano Tessaro},
      title = {One-More Unforgeability for Multi- and Threshold Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1947},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1947}
}