Fast amortized KZG proofs

Dankrad Feist; Dmitry Khovratovich

Paper 2023/033

Fast amortized KZG proofs

Dankrad Feist, Ethereum Foundation

Dmitry Khovratovich, Ethereum Foundation

Abstract

In this note we explain how to compute $n$ KZG proofs for a polynomial of degree $d$ in time superlinear of $(n+d)$. Our technique is used in lookup arguments and vector commitment schemes.

Note: Also known as "Fast amortized Kate proofs". A bug in section 2.2 is fixed.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: KZG toeplitz fft multiple proofs lookup vector commitments
Contact author(s): dankrad feist @ ethereum org
khovratovich @ gmail com
History: 2023-08-10: last of 2 revisions; 2023-01-11: received; See all versions
Short URL: https://ia.cr/2023/033
License: CC0

BibTeX

@misc{cryptoeprint:2023/033,
      author = {Dankrad Feist and Dmitry Khovratovich},
      title = {Fast amortized {KZG} proofs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/033},
      year = {2023},
      url = {https://eprint.iacr.org/2023/033}
}