Query-Optimal IOPPs for Linear-Time Encodable Codes

We present the first Interactive Oracle Proof of Proximity (IOPP) for linear-time encodable codes that achieves $\lambda$-bit security with linear prover time and optimal $O(\lambda)$ query complexity. This implies (via standard techniques) the first IOP for NP with $O(n)$ prover time and $O(\lambda)$ query complexity, and hence also the first SNARK for NP in the random oracle model with linear prover time and $O(\lambda^2 \log n)$ proof size.

The technical core of our result is a novel IOPP for tensor codes. Our tensor IOPP leverages error correction in a novel way to reduce checking proximity of a purported codeword to the tensor code to checking the proximity of $\Theta(\lambda)$-many of its columns to the column code. Our key insight is that it in fact suffices to just prove that a constant fraction of these new proximity claims hold (as opposed to all of them). We devise a new lossy batching protocol that provides the foregoing guarantee with just $O(\lambda)$ query complexity. By combining this tensor IOPP with prior "codeswitching" reductions, we obtain IOPPs for a large class of linear-time encodable codes.

We complement our IOPP construction with a lower bound that shows that, when proving proximity to constant-rate codes, one cannot construct IOPPs with query complexity better than $O(\lambda)$. This establishes the optimality of our IOPP's query complexity.