International Association
for Cryptologic Research

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.