Improving logarithmic derivative lookups using GKR

Shahar Papini; Ulrich Haböck

Paper 2023/1284

Improving logarithmic derivative lookups using GKR

Shahar Papini, StarkWare

Ulrich Haböck, Polygon Labs

Abstract

In this informal note, we instantiate the Goldwasser-Kalai-Rothblum (GKR) protocol to prove fractional sumchecks as present in lookup arguments based on logarithmic derivatives, with the following impact on the prover cost of logUp (IACR eprint 2022/1530): When looking up $M \geq 1$ columns in a (for the sake of simplicity) single column table, the prover has to commit only to a single extra column, i.e. the multiplicities of the table entries. In order to carry over the GKR fractional sumcheck to the univariate setting, we furthermore introduce a simple, yet (as far as we know) novel transformation for turning a univariate polynomial commitment scheme into a multilinear one. The transformation complements existing approaches and might be of independent interest for its elegant way to prove arbitrary powers of the lexicographic shift over the Boolean hypercube.

Note: Further typos corrected.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: lookup arguments GKR multilinear commitment scheme
Contact author(s): spapini @ starkware co
ulrich haboeck @ gmail com
History: 2025-02-20: last of 3 revisions; 2023-08-27: received; See all versions
Short URL: https://ia.cr/2023/1284
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1284,
      author = {Shahar Papini and Ulrich Haböck},
      title = {Improving logarithmic derivative lookups using {GKR}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1284},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1284}
}