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 31 Jan 2020
Contact author: ariel gabizon at gmail com
Available format(s): PDF | BibTeX Citation
Version: 20200131:192310 (All versions of this report)
Short URL: ia.cr/2020/081
[ Cryptology ePrint archive ]