Welcome to the resource topic for 2020/315
Title:
plookup: A simplified polynomial protocol for lookup tables
Authors: Ariel Gabizon, Zachary J. Williamson
Abstract:We present a protocol for checking the values of a committed polynomial f\in \mathbb{F}_{<n}[X] over a multiplicative subgroup H\subset \mathbb{F} of size n, are contained in the values of a table t\in \mathbb{F}^d. Our protocol can be viewed as a simplification of one from Bootle et. al [BCGJM, ASIACRYPT 2018] for a similar problem, with potential efficiency improvements when d\leq n. In particular, [BCGJM]‘s protocol requires comitting to several auxiliary polynomials of degree d\cdot \log n, whereas ours requires three commitments to auxiliary polynomials of degree n, which can be much smaller in the case d\sim n. One common use case of this primitive in the zk-SNARK setting is a ``batched range proof’', where one wishes to check all of f's values on H are in a range [0,\ldots,M]. We present a slightly optimized protocol for this special case, and pose improving it as an open problem.
ePrint: https://eprint.iacr.org/2020/315
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 .