Plonkup scheme with multiple queries

Alexandr Bulkin; Tim Dokchitser

Paper 2023/066

Plonkup scheme with multiple queries

Alexandr Bulkin, Adapt Framework solutions

Tim Dokchitser

Abstract

There is a line of 'lookup' protocols to show that all elements of a sequence $f \in F^{n}$ are contained in a table $t \in F^{d}$ , for some field $F$ . Lookup has become an important primitive in Zero Knowledge Virtual Machines, and is used for range checks and other parts of the proofs of a correct program execution. In this note we give several variants of the protocol. We adapt it to the situation when there are multiple lookups with the same table (as is usually the case with range checks), and handle also 'bounded lookup' that caps the number of repetitions.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Lookup zero knowledge virtual machine
Contact author(s): alex @ adaptframework solutions
timdok @ gmail com
History: 2023-01-20: approved; 2023-01-20: received; See all versions
Short URL: https://ia.cr/2023/066
License: CC BY

BibTeX

@misc{cryptoeprint:2023/066,
      author = {Alexandr Bulkin and Tim Dokchitser},
      title = {Plonkup scheme with multiple queries},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/066},
      year = {2023},
      url = {https://eprint.iacr.org/2023/066}
}