Efficient polynomial commitment schemes for multiple points and polynomials

Dan Boneh; Justin Drake; Ben Fisch; Ariel Gabizon

Paper 2020/081

Efficient polynomial commitment schemes for multiple points and polynomials

Dan Boneh, Justin Drake, 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].

Note: ack correction

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: zk-SNARKs Polynomial Commitment Schemes
Contact author(s): ariel gabizon @ gmail com
History: 2021-05-27: last of 5 revisions; 2020-01-28: received; See all versions
Short URL: https://ia.cr/2020/081
License: CC BY

BibTeX

@misc{cryptoeprint:2020/081,
      author = {Dan Boneh and Justin Drake and Ben Fisch and Ariel Gabizon},
      title = {Efficient polynomial commitment schemes for multiple points and polynomials},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/081},
      year = {2020},
      url = {https://eprint.iacr.org/2020/081}
}