Paper 2022/1530

Multivariate lookups based on logarithmic derivatives

Ulrich Haböck, Orbis Labs
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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Lookup arguments Multivariate Oracle Proofs SNARKs
Contact author(s)
team @ orbislabs com
History
2022-11-07: revised
2022-11-04: received
See all versions
Short URL
https://ia.cr/2022/1530
License
Creative Commons Attribution
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.