The family of Reed-Solomon (RS) codes plays a prominent role in the construction of quasilinear probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs) with perfect zero knowledge and polylogarithmic verifiers. The large concrete computational complexity required to prove membership in RS codes is one of the biggest obstacles to deploying such
PCP/IOP systems in practice.

To advance on this problem we present a new interactive oracle proof of proximity (IOPP) for RS codes; we call it the Fast RS IOPP (FRI) because (i) it resembles the ubiquitous Fast Fourier Transform (FFT) and (ii) the arithmetic complexity of its prover is strictly linear and that of the verifier is strictly logarithmic (in comparison, FFT arithmetic complexity is quasi-linear but not strictly linear). Prior RS IOPPs and PCPs of proximity (PCPPs) required super-linear proving time even for polynomially large query complexity.

For codes of block-length n, the arithmetic complexity of the (interactive) FRI prover is less than 6 · n, while the (interactive) FRI verifier has arithmetic complexity ? 21 · log n, query complexity 2 · log n and constant soundness — words that are ?-far from the code are rejected with probability min {? · (1 ? o(1)), ?' } where ?' is a positive constant that depends only on the code rate. The particular combination of query complexity and soundness obtained by FRI is better than that of the quasilinear PCPP of [Ben-Sasson and Sudan, SICOMP 2008], even with the tighter soundness analysis of [Ben-Sasson et al., STOC 2013; ECCC 2016]; consequently, FRI is likely to facilitate better concretely efficient zero knowledge proof and argument systems.

Previous concretely efficient PCPPs and IOPPs suffered a constant multiplicative factor loss in soundness with each round of “proof composition” and thus used at most O(log log n) rounds. We show that when ? is smaller than the unique decoding radius of the code (? < (1 ? ?)/2), FRI suffers only a negligible additive loss in soundness. This observation allows us to increase the number of “proof composition” rounds to ?(log n) and thereby improve prover running time.

Modify Conjecture 1.5, add Conjecutre 3.4, and discuss them in Section 4.5. Minor typos and errors fixed.

The family of Reed-Solomon (RS) codes plays a prominent role in the construction of quasilinear probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs) with perfect zero knowledge and polylogarithmic verifiers. The large concrete computational complexity required to prove membership in RS codes is one of the biggest obstacles to deploying such
PCP/IOP systems in practice.

To advance on this problem we present a new interactive oracle proof of proximity (IOPP) for RS codes; we call it the Fast RS IOPP (FRI) because (i) it resembles the ubiquitous Fast Fourier Transform (FFT) and (ii) the arithmetic complexity of its prover is strictly linear and that of the verifier is strictly logarithmic (in comparison, FFT arithmetic complexity is quasi-linear but not strictly linear). Prior RS IOPPs and PCPs of proximity (PCPPs) required super-linear proving time even for polynomially large query complexity.

For codes of block-length n, the arithmetic complexity of the (interactive) FRI prover is less than 6 · n, while the (interactive) FRI verifier has arithmetic complexity $\leq$ 21 · log n, query complexity 2 · log n and constant soundness — words that are $\delta$-far from the code are rejected with probability min {$\delta$ · (1 - o(1)), $\delta_0$ } where $\delta_0$ is a positive constant that depends only on the code rate. The particular combination of query complexity and soundness obtained by FRI is better than that of the quasilinear PCPP of [Ben-Sasson and Sudan, SICOMP 2008], even with the tighter soundness analysis of [Ben-Sasson et al., STOC 2013; ECCC 2016]; consequently, FRI is likely to facilitate better concretely efficient zero knowledge proof and argument systems.

Previous concretely efficient PCPPs and IOPPs suffered a constant multiplicative factor loss in soundness with each round of “proof composition” and thus used at most O(log log n) rounds. We show that when $\delta$ is smaller than the unique decoding radius of the code, FRI suffers only a negligible additive loss in soundness. This observation allows us to increase the number of “proof composition” rounds to $\Theta$(log n) and thereby improve prover running time.

Fixed typos; added section 1.3 explaining "practical considerrations"

The family of Reed-Solomon (RS) codes plays a prominent role in the construction of quasilinear probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs) with perfect zero knowledge and polylogarithmic verifiers. The large concrete computational complexity required to prove membership in RS codes is one of the biggest obstacles to deploying such
PCP/IOP systems in practice.

To advance on this problem we present a new interactive oracle proof of proximity (IOPP) for RS codes; we call it the Fast RS IOPP (FRI) because (i) it resembles the ubiquitous Fast Fourier Transform (FFT) and (ii) the arithmetic complexity of its prover is strictly linear and that of the verifier is strictly logarithmic (in comparison, FFT arithmetic complexity is quasi-linear but not strictly linear). Prior RS IOPPs and PCPs of proximity (PCPPs) required super-linear proving time even for polynomially large query complexity.

For codes of block-length n, the arithmetic complexity of the (interactive) FRI prover is less than 6 · n, while the (interactive) FRI verifier has arithmetic complexity ? 21 · log n, query complexity 2 · log n and constant soundness — words that are ?-far from the code are rejected with probability min {? · (1 ? o(1)), ?' } where ?' is a positive constant that depends only on the code rate. The particular combination of query complexity and soundness obtained by FRI is better than that of the quasilinear PCPP of [Ben-Sasson and Sudan, SICOMP 2008], even with the tighter soundness analysis of [Ben-Sasson et al., STOC 2013; ECCC 2016]; consequently, FRI is likely to facilitate better concretely efficient zero knowledge proof and argument systems.

Previous concretely efficient PCPPs and IOPPs suffered a constant multiplicative factor loss in soundness with each round of “proof composition” and thus used at most O(log log n) rounds. We show that when ? is smaller than the unique decoding radius of the code (? < (1 ? ?)/2), FRI suffers only a negligible additive loss in soundness. This observation allows us to increase the number of “proof composition” rounds to ?(log n) and thereby improve prover running time.