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

Shravan Srinivasan; Ioanna Karantaidou; Foteini Baldimtsi; Charalampos Papamanthou

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. ACM CCS 2022
DOI: 10.1145/3548606.3560676
Keywords: accumulators zero-knowledge aggregation
Contact author(s): sshravan @ cs umd edu
ikaranta @ gmu edu
foteini @ gmu edu
charalampos papamanthou @ yale edu
History: 2022-12-31: approved; 2022-12-31: received; See all versions
Short URL: https://ia.cr/2022/1779
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1779,
      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},
      url = {https://eprint.iacr.org/2022/1779}
}