International Association
for Cryptologic Research

We present STIR (Shift To Improve Rate), a concretely efficient interactive oracle proof of proximity (IOPP) for Reed--Solomon codes that achieves the best known query complexity of any concretely efficient IOPP for this problem. Roughly, in order to achieve $\lambda$ bits of security, STIR has query complexity $O(\log d + \lambda \cdot \loglog d )$, while the popular FRI protocol (including variants based on conjectured security assumptions) has query complexity $O(\lambda \cdot \log d )$. STIR relies on a new technique for recursively reducing the degree of the function being tested while simultaneously improving the rate. We provide an implementation of STIR compiled to a SNARK. Compared to FRI, our implementation achieves an improvement in argument size that ranges from $1.25\times$ to $2.46\times$ depending on the chosen parameters. For example, in order to achieve 128 bits of security for degree $2^{26}$ and rate $1/4$, STIR has argument size $114$~KiB, compared to $211$~KiB for FRI.

We provide a wide systematic study of proximity proofs with one-sided error for the Hamming weight problem Ham_alpha (the language of bit vectors with Hamming weight at least alpha), surpassing previously known results for this problem. We demonstrate the usefulness of the one-sided error property in applications: no malicious party can frame an honest prover as cheating by presenting verifier randomness that leads to a rejection. We show proofs of proximity for Ham_alpha with one-sided error and sublinear proof length in three models (MA, PCP, IOP), where stronger models allow for smaller query complexity. For n-bit input vectors, highlighting input query complexity, our MA has O(log n) query complexity, the PCP makes O(loglog n) queries, and the IOP makes a single input query. The prover in all of our applications runs in expected quasi-linear time. Additionally, we show that any perfectly complete IP of proximity for Ham_alpha with input query complexity n^{1-epsilon} has proof length Omega(log n). Furthermore, we study PCPs of proximity where the verifier is restricted to making a single input query (SIQ). We show that any SIQ-PCP for Ham_alpha must have a linear proof length, and complement this by presenting a SIQ-PCP with proof length n+o(n). As an application, we provide new methods that transform PCPs (and IOPs) for arbitrary languages with nonzero completeness error into PCPs (and IOPs) that exhibit perfect completeness. These transformations achieve parameters previously unattained.

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multiple rounds while reading a small number of bits from each prover message. While PCPs are relatively well understood, the power captured by IOPs (beyond $\NP$) has yet to be fully explored. We present a generalization of the PCP theorem for interactive languages. We show that any language decidable by a k(n)-round IP has a k(n)-round public-coin IOP, where the verifier makes its decision by reading only O(1) bits from each (polynomially long) prover message and $O(1)$ bits from each of its own (random) messages to the prover. Our result and the underlying techniques have several applications. We get a new hardness of approximation result for a stochastic satisfiability problem, we show IOP-to-IOP transformations that previously were known to hold only for IPs, and we formulate a new notion of PCPs (index-decodable PCPs) that enables us to obtain a commit-and-prove SNARK in the random oracle model for nondeterministic computations.

Interactive oracle proofs (IOPs) are a proof system model that combines features of interactive proofs (IPs) and probabilistically checkable proofs (PCPs). IOPs have prominent applications in complexity theory and cryptography, most notably to constructing succinct arguments. In this work, we study the limitations of IOPs, as well as their relation to those of PCPs. We present a versatile toolbox of IOP-to-IOP transformations containing tools for: (i) length and round reduction; (ii) improving completeness; and (iii) derandomization. We use this toolbox to establish several barriers for IOPs: \begin{itemize} \item Low-error IOPs can be transformed into low-error PCPs. In other words, interaction can be used to construct low-error PCPs; alternatively, low-error IOPs are as hard to construct as low-error PCPs. This relates IOPs to PCPs in the regime of the sliding scale conjecture for inverse-polynomial soundness error. \item Limitations of quasilinear-size IOPs for 3SAT with small soundness error. \item Limitations of IOPs where query complexity is much smaller than round complexity. \item Limitations of binary-alphabet constant-query IOPs. \end{itemize} We believe that our toolbox will prove useful to establish additional barriers beyond our work.