Batching non-membership proofs with bilinear accumulators

Steve Thakur

Paper 2019/1147

Batching non-membership proofs with bilinear accumulators

Steve Thakur, Panther Protocol

Abstract

In this short paper, we provide a protocol to batch multiple non-membership proofs into a single proof of constant size with bilinear accumulators via a succinct argument of knowledge for polynomial commitments. We use similar techniques to provide a constant-sized proof that a polynomial commitment as in [KZG10] is a commitment to a separable (square-free) polynomial. In the context of the bilinear accumulator, this can be used to prove that a committed multiset is, in fact, a set. This has applications to any setting where a Verifier needs to be convinced that no element was added more than once. This protocol easily generalizes to a succinct protocol that shows that no element was inserted more than k times. We use the protocol for the derivative to link a committed polynomial to a commitment to its degree, in zero-knowledge. We have designed all of the protocols so that the Verifier needs to store just four elliptic curve points for any verification, despite the linear CRS. We also provide ways to speed up the verification of membership and non-membership proofs and to shift most of the computational burden from the Verifier to the Prover. Since all the challenges are public coin, the protocols can be made non-interactive with a Fiat-Shamir heuristic.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Accumulators Vector Commitments bilinear pairings zero knowledge verifiable computation AoKs
Contact author(s): stevethakur01 @ gmail com
History: 2022-10-04: last of 21 revisions; 2019-10-07: received; See all versions
Short URL: https://ia.cr/2019/1147
License: CC BY

BibTeX

@misc{cryptoeprint:2019/1147,
      author = {Steve Thakur},
      title = {Batching non-membership proofs with bilinear accumulators},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1147},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1147}},
      url = {https://eprint.iacr.org/2019/1147}
}