Paper 2023/393
cqlin: Efficient linear operations on KZG commitments with cached quotients
Abstract
Given two KZG-committed polynomials $f(X),g(X)\in \mathbb{F}_{<n}[X]$, a matrix $M\in \mathbb{F}^{n\times n}$, and subgroup $H\subset \mathbb{F}^*$ of order $n$, we present a protocol for checking that $f|_{H}\cdot M = g|_{H}$. After preprocessing, the prover makes $O(n)$ field and group operations. This presents a significant improvement over the lincheck protocols in [CHMMVW, COS], where the prover's run-time (also after preprocessing) was quasilinear in the number of non-zeroes of $M$, which could be $n^2$.
Note: Small corrections, ack - Josh Beal
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- zk-snarkspolynomial commitment schemespairings
- Contact author(s)
- ariel gabizon @ gmail com
- History
- 2023-10-16: last of 4 revisions
- 2023-03-19: received
- See all versions
- Short URL
- https://ia.cr/2023/393
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/393,
author = {Liam Eagen and Ariel Gabizon},
title = {cqlin: Efficient linear operations on KZG commitments with cached quotients},
howpublished = {Cryptology ePrint Archive, Paper 2023/393},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/393}},
url = {https://eprint.iacr.org/2023/393}
}
