Paper 2022/1530
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.
Note: Clarified the trade-off between algebraic degree and the number of commitments, previously expressed by two protocol variants. Discussion of Polygon Miden’s bounded multiplicity encoding.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Lookup argumentsInteractive Oracle ProofsSNARKs
- Contact author(s)
- uhaboeck @ polygon technology
- History
- 2023-03-31: last of 2 revisions
- 2022-11-04: received
- See all versions
- Short URL
- https://ia.cr/2022/1530
- License
-
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},
url = {https://eprint.iacr.org/2022/1530}
}