Paper 2020/081

Efficient polynomial commitment schemes for multiple points and polynomials

Dan Boneh, Justin Drake, Ben Fisch, and Ariel Gabizon


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

Available format(s)
Publication info
Preprint. MINOR revision.
zk-SNARKsPolynomial Commitment Schemes
Contact author(s)
ariel gabizon @ gmail com
2021-05-27: last of 5 revisions
2020-01-28: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.