Paper 2021/1672

Succinct Zero-Knowledge Batch Proofs for Set Accumulators

Matteo Campanelli, Dario Fiore, Semin Han, Jihye Kim, Dimitris Kolonelos, and Hyunok Oh

Abstract

Cryptographic accumulators are a common solution to proving information about a large set $S$. They allow to compute a short digest of $S$ and short certificates of some of its basic properties, notably membership of an element. Accumulators also allow to track set updates: a new accumulator is obtained by inserting/deleting a given element. In this work we consider the problem of generating membership and update proofs for batchesof elements so that we can succinctly prove additional properties of the elements (i.e., proofs are of constant size regardless of the batch size), and we can preserve privacy. Solving this problem would allow to obtain blockchain systems with improved privacy and scalability. The state-of-the-art approach to achieve this goal is to combine accumulators (typically Merkle trees) with zkSNARKs. This solution is however expensive for provers and does not scale for large batches of elements. In particular, there is no scalable solution for proving batch membership proofs when we require zero-knowledge (a standard definition of privacy-preserving protocols). In this work we propose new techniques to efficiently use zkSNARKs with RSA accumulators. We design and implement two main schemes: 1) HARiSA, which proves batch membership in zero-knowledge; 2) B-INS-HARiSA, which proves batch updates. For batch membership, the prover in HARiSA is orders of magnitude faster than existing approaches based on Merkle trees (depending on the hash function). For batch updates we get similar cost savings compared to approaches based on Merkle tree; we also improve over the recent solution of Ozdemir et al. [USENIX’20].

Note: Updated benchmarks; included witness generation discussion; other editorial changes.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
snarkszero-knowledgeset-membershiprsaaccumulators
Contact author(s)
matteo campanelli @ gmail com
matteo @ protocol ai
dario fiore @ imdea org
dimitris kolonelos @ imdea org
hoh @ hanyang ac kr
seminhan @ hanyang ac kr
jihyek @ kookmin ac kr
History
2022-05-03: last of 3 revisions
2021-12-21: received
See all versions
Short URL
https://ia.cr/2021/1672
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1672,
      author = {Matteo Campanelli and Dario Fiore and Semin Han and Jihye Kim and Dimitris Kolonelos and Hyunok Oh},
      title = {Succinct Zero-Knowledge Batch Proofs for Set Accumulators},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1672},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1672}},
      url = {https://eprint.iacr.org/2021/1672}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.