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.

We establish new results on the Fiat-Shamir (FS) security of several protocols that are widely used in practice, and we provide general tools for establishing similar results for others. More precisely, we: (1) prove the FS security of the FRI and batched FRI protocols; (2) analyze a general class of protocols, which we call \emph{$\delta$-correlated}, that use low-degree proximity testing as a subroutine (this includes many ``Plonk-like'' protocols (e.g., Plonky2 and Redshift), ethSTARK, RISC Zero, etc.); and (3) prove FS security of the aforementioned ``Plonk-like'' protocols, and sketch how to prove the same for the others. We obtain our first result by analyzing the round-by-round (RBR) soundness and RBR knowledge soundness of FRI. For the second result, we prove that if a $\delta$-correlated protocol is RBR (knowledge) sound under the assumption that adversaries always send low-degree polynomials, then it is RBR (knowledge) sound in general. Equipped with this tool, we prove our third result by formally showing that ``Plonk-like'' protocols are RBR (knowledge) sound under the assumption that adversaries always send low-degree polynomials. We then outline analogous arguments for the remainder of the aforementioned protocols. To the best of our knowledge, ours is the first formal analysis of the Fiat-Shamir security of FRI and widely deployed protocols that invoke it.