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}}^{\ast }$ 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 $$, which could be $$.

Note: Small corrections, ack - Josh Beal