Paper 2019/1147

Batching non-membership proofs with bilinear accumulators

Steve Thakur, Panther Protocol

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.

Available format(s)
Public-key cryptography
Publication info
Accumulators Vector Commitments bilinear pairings zero knowledge verifiable computation AoKs
Contact author(s)
stevethakur01 @ gmail com
2022-10-04: last of 21 revisions
2019-10-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Steve Thakur},
      title = {Batching non-membership proofs with bilinear accumulators},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1147},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.