Welcome to the resource topic for
**2023/393**

**Title:**

cqlin: Efficient linear operations on KZG commitments with cached quotients

**Authors:**
Liam Eagen, Ariel Gabizon

**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.

**ePrint:**
https://eprint.iacr.org/2023/393

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .