### 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.

Note: typo, ack: Luke Pearson

Available format(s)
Publication info
Preprint. MINOR revision.
Keywords
zk-SNARKsPolynomial Commitment Schemes
Contact author(s)
ariel @ aztecprotocol com
History
2020-11-20: last of 4 revisions
See all versions
Short URL
https://ia.cr/2020/315

CC BY

BibTeX

@misc{cryptoeprint:2020/315,
author = {Ariel Gabizon and Zachary J.  Williamson},
title = {plookup: A simplified polynomial protocol for lookup tables},
howpublished = {Cryptology ePrint Archive, Paper 2020/315},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/315}},
url = {https://eprint.iacr.org/2020/315}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.