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. Furthermore, we have designed the protocols so that the Verifier needs a constant amount of storage for verification despite the 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. Since all the protocols are public coin, they can be made non-interactive with a Fiat-Shamir heuristic.

Category / Keywords: public-key cryptography / Accumulators, Vector Commitments, bilinear pairings, zero knowledge, verifiable computation

Date: received 3 Oct 2019, last revised 27 Jan 2020

Contact author: stevethakur01 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200127:210703 (All versions of this report)

Short URL: ia.cr/2019/1147


[ Cryptology ePrint archive ]