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{\mathbb F}^n$ are contained in a table $t\in{\mathbb F}^d$, for some field ${\mathbb 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
Lookupzero knowledgevirtual 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2023/066}},
      url = {https://eprint.iacr.org/2023/066}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.