Welcome to the resource topic for 2022/1447
Title:
flookup: Fractional decomposition-based lookups in quasi-linear time independent of table size
Authors: Ariel Gabizon, Dmitry Khovratovich
Abstract:We present a protocol for checking the values of a committed polynomial \phi(X) over a mutliplicative subgroup V\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.
ePrint: https://eprint.iacr.org/2022/1447
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 .