### Multivariate lookups based on logarithmic derivatives

##### Abstract

Logarithmic derivatives translate products of linear factors into sums of their reciprocals, turning zeroes into simple poles of same multiplicity. Based on this simple fact, we construct an interactive oracle proof for multi-column lookups over the boolean hypercube, which makes use of a single multiplicity function instead of working with a rearranged union of table and witnesses. For single-column lookups the performance is comparable to the well-known Plookup strategy used by Hyperplonk+. However, the real power of our argument unfolds in the case of batch lookups when multiple columns are subject to a single-table lookup: While the number of field operations is comparable to the Hyperplonk+ lookup (extended to multiple columns), the oracles provided by our prover are much less expensive. For example, for columns of length 2^12, paper-pencil operation counts indicate that the logarithmic derivative lookup is between 1.5 and 4 times faster, depending on the number of columns.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Lookup arguments Multivariate Oracle Proofs SNARKs
Contact author(s)
team @ orbislabs com
History
2022-11-07: revised
See all versions
Short URL
https://ia.cr/2022/1530

CC BY

BibTeX

@misc{cryptoeprint:2022/1530,
author = {Ulrich Haböck},
title = {Multivariate lookups based on logarithmic derivatives},
howpublished = {Cryptology ePrint Archive, Paper 2022/1530},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1530}},
url = {https://eprint.iacr.org/2022/1530}
}

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