[Resource Topic] 2020/315: plookup: A simplified polynomial protocol for lookup tables

Welcome to the resource topic for 2020/315

plookup: A simplified polynomial protocol for lookup tables

Authors: Ariel Gabizon, Zachary J. Williamson


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 .

A post was split to a new topic: Question about Claim 3.1