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 .