Paper 2022/1447

flookup: Fractional decomposition-based lookups in quasi-linear time independent of table size

Ariel Gabizon, Zeta Function Technologies
Dmitry Khovratovich, Ethereum Foundation
Abstract

We present a protocol for checking the values of a committed polynomial $\phi(X)$ over a multiplicative subgroup $H\subset \mathbb{F}$ of size $m$ are contained in a table $T\in \mathbb{F}^N$. After an $O(N \log^2 N)$ preprocessing step, the prover algorithm runs in *quasilinear* time $O(m\log ^2 m)$. We improve upon the recent breakthrough results Caulk[ZBK+22] and Caulk+[PK22], which were the first to achieve the complexity sublinear in the full table size $N$ with prover time being $O(m^2+m\log N)$ and $O(m^2)$, respectively. We pose further improving this complexity to $O(m\log m)$ as the next important milestone for efficient zk-SNARK lookups.

Note: Fixes by Piotr M.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
zk-SNARKslookupspairings
Contact author(s)
ariel gabizon @ gmail com
khovratovich @ gmail com
History
2024-02-23: last of 7 revisions
2022-10-23: received
See all versions
Short URL
https://ia.cr/2022/1447
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2022/1447,
      author = {Ariel Gabizon and Dmitry Khovratovich},
      title = {flookup: Fractional decomposition-based lookups in quasi-linear time independent of table size},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1447},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1447}},
      url = {https://eprint.iacr.org/2022/1447}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.