Paper 2024/1531

FLI: Folding Lookup Instances

Albert Garreta, Methermind Research
Ignacio Manzur, Nethermind Research
Abstract

We introduce two folding schemes for lookup instances: FLI and FLI+SOS. Both use a PIOP to check that a matrix has elementary basis vectors as rows, with FLI+SOS adding a twist based on Lasso’s SOS-decomposability. FLI takes two lookup instances , and expresses them as matrix equations for , where each matrix has rows which are elementary basis vectors in . Matrices that satisfy this condition are said to be in . Then, a folding scheme for into a relaxed relation is used, which combines the matrices as for a random . Finally, the lookup equations are combined as . In FLI, only the property that a matrix is in is folded, and this makes the FLI folding step the cheapest among existing solutions. The price to pay is in the cost for proving accumulated instances. FLI+SOS builds upon FLI to enable folding of large SOS-decomposable tables. This is achieved through a variation of Lasso's approach to SOS-decomposability, which fits FLI naturally. For comparison, we describe (for the first time to our knowledge) straightforward variations of Protostar and Proofs for Deep Thought that also benefit from SOS-decomposability. We see that for many reasonable parameter choices, and especially those arising from lookup-based zkVMs, FLI+SOS can concretely be the cheapest folding solution.

Note: Added acknowledgements

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2024
Keywords
zero knowledgeinteractive proofsSNARKlookup argumentfolding scheme
Contact author(s)
albert @ nethermind io
ignacio @ nethermind io
History
2024-10-28: last of 2 revisions
2024-09-30: received
See all versions
Short URL
https://ia.cr/2024/1531
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1531,
      author = {Albert Garreta and Ignacio Manzur},
      title = {{FLI}: Folding Lookup Instances},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1531},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1531}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.