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