Paper 2019/336

DEEP-FRI: Sampling Outside the Box Improves Soundness

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf

Abstract

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]. The previous state of the art by [Ben-Sasson, Kopparty, Saraf, CCC 2018] showed that if some member of 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. However, this result was known to hold only below the “double Johnson” function of the relative distance $\delta_V$ of the code $V$ , i.e., only when $\delta < 1 - \sqrt[4]{1 - \delta_V}$. First, we increase the soundness-bound to the “one-and-a-half Johnson” function of $\delta_V$ and show that the average distance of $U$ from $V$ is nearly $\delta$ for any worst-case distance $\delta$ smaller than $1 - \sqrt[3]{1 - \delta_V}$. This bound is tight, which is somewhat surprising because the one-and-a-half Johnson function is unfamiliar in the literature on error correcting codes. To improve soundness further for Reed Solomon codes we sample outside the box. We suggest a new protocol in which the verifier samples a single point $z$ outside the box $D$ on which codewords are evaluated, and asks the prover for the value at $z$ of the interpolating polynomial of a random element of $U$. Intuitively, the answer provided by the prover “forces” it to choose one codeword from a list of “pretenders” that are close to $U$. We call this technique Domain Extending for Eliminating Pretenders (DEEP). The DEEP method improves the soundness of the worst-case-to-average-case reduction for RS codes up their list decoding radius. This radius is bounded from below by the Johnson bound, implying average distance is approximately $\delta$ for all $\delta < 1 - \sqrt{1 - \delta_V}$. Under a plausible conjecture about the list decoding radius of Reed-Solomon codes, average distance from $V$ is approximately $\delta$ for all $\delta$. The DEEP technique can be generalized to all linear codes, giving improved reductions for capacity-achieving list-decodable codes. Finally, we use the DEEP technique to devise two new protocols: • 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 of [Ben-Sasson et al., ICALP 2018] while retaining linear arithmetic proving complexity and logarithmic verifier arithmetic complexity. • 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$.