Fast amortized KZG proofs

Dankrad Feist; Dmitry Khovratovich

Paper 2023/033 Original: eprint.iacr.org/2023/033 ↗

Fast amortized KZG proofs

Dankrad Feist

Dmitry Khovratovich

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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
History: 2025-05-18: last updated; 2023-01-11: published
Short URL: https://ia.cr/2023/033
License: https://creativecommons.org/publicdomain/zero/1.0/

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}
}