Paper 2023/1793

Accountable Multi-Signatures with Constant Size Public Keys

Dan Boneh, Stanford University
Aditi Partap, Stanford University
Brent Waters, The University of Texas at Austin, NTT Research

A multisignature scheme is used to aggregate signatures by multiple parties on a common message $m$ into a single short signature on $m$. Multisignatures are used widely in practice, most notably, in proof-of-stake consensus protocols. In existing multisignature schemes, the verifier needs the public keys of all the signers in order to verify a multisignature issued by some subset of signers. We construct new practical multisignature schemes with three properties: (i) the verifier only needs to store a constant size public key in order to verify a multisignature by an arbitrary subset of parties, (ii) signature size is constant beyond the description of the signing set, and (iii) signers generate their secret signing keys locally, that is, without a distributed key generation protocol. Existing schemes satisfy properties (ii) and (iii). The new capability is property (i) which dramatically reduces the verifier's memory requirements from linear in the number of signers to constant. We give two pairing-based constructions: one in the random oracle model and one in the plain model. We also show that by relaxing property (iii), that is, allowing for a simple distributed key generation protocol, we can further improve efficiency while continuing to satisfy properties (i) and (ii). We give a pairing-based scheme and a lattice-based scheme in this relaxed model. Our pairing based constructions are closely related to a multisignature scheme due to Boneh, Drijvers, and Neven (Asiacrypt 2018), but with several key differences.

Available format(s)
Public-key cryptography
Publication info
Contact author(s)
dabo @ cs stanford edu
aditi712 @ cs stanford edu
bwaters @ cs utexas edu
2024-04-05: last of 5 revisions
2023-11-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dan Boneh and Aditi Partap and Brent Waters},
      title = {Accountable Multi-Signatures with Constant Size Public Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1793},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.