Cryptology ePrint Archive: Report 2019/1147

Batching non-membership proofs with bilinear accumulators

Steve Thakur

Abstract: In this short paper, we provide protocols to batch and aggregate multiple non-membership proofs into a single proof of constant size with bilinear accumulators. We subsequently use the accumulator to construct a bilinear Vector Commitment with constant sized openings and a linear public parameter. 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. Furthermore, we have designed the protocols so that the Verifier needs a constant amount of storage for verification despite the linear public parameter. Since all the protocols are public coin, they can me made non-interactive with a Fiat-Shamir heuristic.

Category / Keywords: public-key cryptography / Accumulators, Vector Commitments, bilinear pairings

Date: received 3 Oct 2019

Contact author: stevethakur01 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20191007:081853 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]