Chopsticks: Fork-Free Two-Round Multi-Signatures from Non-Interactive Assumptions

Jiaxin Pan; Benedikt Wagner

Paper 2023/198

Chopsticks: Fork-Free Two-Round Multi-Signatures from Non-Interactive Assumptions

Jiaxin Pan

, Norwegian University of Science and Technology

Benedikt Wagner

, CISPA Helmholtz Center for Information Security, Saarland University

Abstract

Multi-signatures have been drawing lots of attention in recent years, due to their applications in cryptocurrencies. Most early constructions require three-round signing, and recent constructions have managed to reduce the round complexity to two. However, their security proofs are mostly based on non-standard, interactive assumptions (e.g. one-more assumptions) and come with a huge security loss, due to multiple uses of rewinding (aka the Forking Lemma). This renders the quantitative guarantees given by the security proof useless. In this work, we improve the state of the art by proposing two efficient two-round multi-signature schemes from the (standard, non-interactive) Decisional Diffie-Hellman (DDH) assumption. Both schemes are proven secure in the random oracle model without rewinding. We do not require any pairing either. Our first scheme supports key aggregation but has a security loss linear in the number of signing queries, and our second scheme is the first tightly secure construction. A key ingredient in our constructions is a new homomorphic dual-mode commitment scheme for group elements, that allows to equivocate for messages of a certain structure. The definition and efficient construction of this commitment scheme is of independent interest.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in EUROCRYPT 2023
DOI: 10.1007/978-3-031-30589-4_21
Keywords: Multi-Signatures Tightness Forking Lemma Commitment Scheme Round Complexity
Contact author(s): jiaxin pan @ ntnu no
benedikt wagner @ cispa de
History: 2023-05-04: last of 2 revisions; 2023-02-15: received; See all versions
Short URL: https://ia.cr/2023/198
License: CC BY

BibTeX

@misc{cryptoeprint:2023/198,
      author = {Jiaxin Pan and Benedikt Wagner},
      title = {Chopsticks: Fork-Free Two-Round Multi-Signatures from Non-Interactive Assumptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/198},
      year = {2023},
      doi = {10.1007/978-3-031-30589-4_21},
      url = {https://eprint.iacr.org/2023/198}
}