Paper 2022/1763
cq: Cached quotients for fast lookups
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. 1. As in [ZBKMNS,PK,ZGKMR] our construction relies on homomorphic table commitments, which makes them amenable to vector lookups. 2. 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.
Note: Fixes by Marek
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint.
 Keywords
 zksnarkslookup protocols
 Contact author(s)
 ariel gabizon @ gmail com
 History
 20240705: last of 5 revisions
 20221225: received
 See all versions
 Short URL
 https://ia.cr/2022/1763
 License

CC0
BibTeX
@misc{cryptoeprint:2022/1763, author = {Liam Eagen and Dario Fiore and Ariel Gabizon}, title = {cq: Cached quotients for fast lookups}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/1763}, year = {2022}, url = {https://eprint.iacr.org/2022/1763} }