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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2019/1147}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.