Cryptology ePrint Archive: Report 2020/081

Efficient polynomial commitment schemes for multiple points and polynomials

Dan Boneh and Justin Drake and Ben Fisch and Ariel Gabizon

Abstract: We present an enhanced version of the Kate, Zaverucha and Goldberg polynomial commitment scheme [KZG, ASIACRYPT 2010] where a single group element can be an opening proof for multiple polynomials each evaluated at a different arbitrary subset of points. As a sample application we ``plug in'' this scheme into the PLONK proving system[GWC, 2019] to obtain improved proof size and prover run time at the expense of additional verifier ${\mathbb{G}}_2$ operations and pairings, and additional ${\mathbb{G}}_2$ SRS elements.

We also present a second scheme where the proof consists of two group elements and the verifier complexity is better than previously known batched verification methods for [KZG].

Category / Keywords: zk-SNARKs, Polynomial Commitment Schemes

Date: received 27 Jan 2020, last revised 27 May 2021

Contact author: ariel gabizon at gmail com

Available format(s): PDF | BibTeX Citation

Note: ack correction

Version: 20210527:135007 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]