Welcome to the resource topic for 2022/1763
Title:
cq: Cached quotients for fast lookups
Authors: Liam Eagen, Dario Fiore, Ariel Gabizon
Abstract:We present a protocol called \mathsf{cq} for checking the values of a committed polynomial f(X)\in \mathbb{F}_{<n}(X) over a multiplicative subgroup H\subset \mathbb{F} of size n are contained in a
table t\in \mathbb{F}^N. After an O(N \log N) preprocessing step, the prover algorithm runs in time O(n\log n).
Thus, we continue to improve upon the recent breakthrough sequence of results [ZBKMNS,PK,GK,ZGKMR] starting from \mathsf{Caulk} [ZBKMNS], which achieve sublinear complexity in the table size N. The two most recent works in this sequence \mathsf{Ba}\mathit{loo} [ZGKMR] and \mathsf{flookup} [GK] achieved prover complexity O(n\log^2 n).
Moreover, \mathsf{cq} has the following attractive features.
- As in [ZBKMNS,PK,ZGKMR] our construction relies on homomorphic table commitments, which makes them amenable to vector lookups.
- As opposed to the previous four works, our verifier doesn’t involve pairings with prover defined \mathbb{G}_2 points, which makes recursive aggregation of proofs more convenient.
ePrint: https://eprint.iacr.org/2022/1763
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 .