Paper 2022/1779

Batching, Aggregation, and Zero-Knowledge Proofs in Bilinear Accumulators

Shravan Srinivasan, University of Maryland, College Park
Ioanna Karantaidou, George Mason University
Foteini Baldimtsi, George Mason University
Charalampos Papamanthou, Yale University

An accumulator is a cryptographic primitive that allows a prover to succinctly commit to a set of values while being able to provide proofs of (non-)membership. A batch proof is an accumulator proof that can be used to prove (non-)membership of multiple values simultaneously. In this work, we present a zero-knowledge batch proof with constant proof size and constant verification in the Bilinear Pairings (BP) setting. Our scheme is 16x to 42x faster than state-of-the-art SNARK-based zero-knowledge batch proofs in the RSA setting. Additionally, we propose protocols that allow a prover to aggregate multiple individual non-membership proofs, in the BP setting, into a single batch proof of constant size. Our construction for aggregation satisfies a strong soundness definition - one where the accumulator value can be chosen arbitrarily. We evaluate our techniques and systematically compare them with RSA-based alternatives. Our evaluation results showcase several scenarios for which BP accumulators are clearly preferable and can serve as a guideline when choosing between the two types of accumulators.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2022
Contact author(s)
sshravan @ cs umd edu
ikaranta @ gmu edu
foteini @ gmu edu
charalampos papamanthou @ yale edu
2022-12-31: approved
2022-12-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shravan Srinivasan and Ioanna Karantaidou and Foteini Baldimtsi and Charalampos Papamanthou},
      title = {Batching, Aggregation, and Zero-Knowledge Proofs in Bilinear Accumulators},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1779},
      year = {2022},
      doi = {10.1145/3548606.3560676},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.