Cryptology ePrint Archive: Report 2021/1167

fflonk: a Fast-Fourier inspired verifier efficient version of PlonK

Ariel Gabizon and Zachary J. Williamson

Abstract: We present a variant of the Kate, Zaverucha and Goldberg polynomial commitment scheme [KZG] where $d$ polynomials can be opened at a point that is a $d$'th power, such that the amount of verifier group operations does not depend on $d$. Our method works by reducing opening multiple polynomials at a single point $x$, to opening a single polynomial at many points via an ``FFT-like identity''.

As an application we present a version of the PlonK zk-SNARK[GWC] with significantly improved verifier performance, at the cost roughly tripling the prover time. Specifically, in addition to the two pairings, the verifier only performs five scalar multiplications, rather than 16 or 18 as in the versions presented in [GWC].

Category / Keywords: cryptographic protocols / zk-SNARKs, Polynomial Commitment Schemes

Date: received 12 Sep 2021, last revised 20 Sep 2021

Contact author: ariel gabizon at gmail com

Available format(s): PDF | BibTeX Citation

Note: typos

Version: 20210920:114023 (All versions of this report)

Short URL: ia.cr/2021/1167


[ Cryptology ePrint archive ]