CryptoDB
FLI: Folding Lookup Instances
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | ASIACRYPT 2024 |
| 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 [STW23] SOS-decomposability. FLI takes two lookup instances {a_1}, {a_2} β {t}, and expresses them as matrix equations π_π Β· t^T = a_i^T for i=1,2, where each matrix π_π β F^{π Γ π} has rows which are elementary basis vectors in F^π. Matrices that satisfy this condition are said to be in R_{elem}. Then, a folding scheme for R_{elem} into a relaxed relation is used, which combines the matrices π_1, π_2 as π_1 + πΌ π_2 for a random πΌ β F. Finally, the lookup equations are combined as (π_1 + πΌ π_2)* t^T = (a_1 + πΌ a_2)^T. In FLI, only the property that a matrix is in R_{elem} 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 [STW23] 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 [BC23] and Proofs for Deep Thought [BC24] that also benefit from SOS-decomposability. We see that for many reasonable parameter choices, and especially those arising from lookup-based zkVMs [AST23], FLI+SOS can concretely be the cheapest folding solution. |
BibTeX
@inproceedings{asiacrypt-2024-34605,
title={FLI: Folding Lookup Instances},
publisher={Springer-Verlag},
author={Albert Garreta and Ignacio Manzur},
year=2024
}