Paper 2022/1763

cq: Cached quotients for fast lookups

Liam Eagen, Blockstream
Dario Fiore, IMDEA Software
Ariel Gabizon, Zeta Function Technologies

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: Fix by Kobi

Available format(s)
Cryptographic protocols
Publication info
zk-snarkslookup protocols
Contact author(s)
ariel gabizon @ gmail com
2023-01-08: last of 4 revisions
2022-12-25: received
See all versions
Short URL
No rights reserved


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.