**plookup: A simplified polynomial protocol for lookup tables**

*Ariel Gabizon and 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.

**Category / Keywords: **zk-SNARKs, Polynomial Commitment Schemes

**Date: **received 13 Mar 2020, last revised 21 Mar 2020

**Contact author: **ariel at aztecprotocol com

**Available format(s): **PDF | BibTeX Citation

**Note: **small corrections

**Version: **20200321:163518 (All versions of this report)

**Short URL: **ia.cr/2020/315

[ Cryptology ePrint archive ]