Paper 2023/393 Original: eprint.iacr.org/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$.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2023-10-16: last updated
- 2023-03-19: published
- Short URL
- https://ia.cr/2023/393
- License
- https://creativecommons.org/publicdomain/zero/1.0/
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},
url = {https://eprint.iacr.org/2023/393}
}