Paper 2020/1568

Compact Certificates of Collective Knowledge

Silvio Micali, Leonid Reyzin, Georgios Vlachos, Riad S. Wahby, and Nickolai Zeldovich

Abstract

We introduce compact certificate schemes, which allow any party to take a large number of signatures on a message $M$, by many signers of different weights, and compress them to a much shorter certificate. This certificate convinces the verifiers that signers with sufficient total weight signed $M$, even though the verifier will not see---let alone verify---all of the signatures. Thus, for example, a compact certificate can be used to prove that parties who jointly have a sufficient total account balance have attested to a given block in a blockchain. After defining compact certificates, we demonstrate an efficient compact certificate scheme. We then show how to implement such a scheme in a decentralized setting over an unreliable network and in the presence of adversarial parties who wish to disrupt certificate creation. Our evaluation shows that compact certificates are 50-280$\times$ smaller and 300-4000$\times$ cheaper to verify than a natural baseline approach.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. IEEE S&P 2021
Keywords
digital signaturesproof systemsimplementationblockchainconsensus
Contact author(s)
rsw @ cs stanford edu
reyzin @ cs bu edu
History
2021-03-30: revised
2020-12-17: received
See all versions
Short URL
https://ia.cr/2020/1568
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1568,
      author = {Silvio Micali and Leonid Reyzin and Georgios Vlachos and Riad S.  Wahby and Nickolai Zeldovich},
      title = {Compact Certificates of Collective Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1568},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1568}},
      url = {https://eprint.iacr.org/2020/1568}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.