DEEP-FRI: Sampling outside the box improves soundness

Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. We first show a sharp quantitative form of a theorem which says that if an affine space $U$ is $\delta$-far in relative Hamming distance from a linear code $V$ - this is the worst-case assumption - then most elements of $U$ are almost $\delta$-far from $V$ - this is the average case. This leads to an optimal analysis of the soundness of the FRI protocol of [Ben-Sasson, et.al., eprint 2018] for proving proximity to Reed-Solomon codes. To further improve soundness, we sample outside the box. We suggest a new protocol which asks a prover for values of a polynomial at points outside the domain of evaluation of the Reed-Solomon code. We call this technique Domain Extending for Eliminating Pretenders (DEEP). We use the DEEP technique to devise two new protocols: (1) An Interactive Oracle Proof of Proximity (IOPP) for RS codes, called DEEP-FRI. This soundness of the protocol improves upon that of the FRI protocol while retaining linear arithmetic proving complexity and logarithmic verifier arithmetic complexity. (2) An Interactive Oracle Proof (IOP) for the Algebraic Linking IOP (ALI) protocol used to construct zero knowledge scalable transparent arguments of knowledge (ZK-STARKs) in [Ben-Sasson et al., eprint 2018]. The new protocol, called DEEP-ALI, improves soundness of this crucial step from a small constant $< 1/8$ to a constant arbitrarily close to $1$.