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 $$ and show that the average distance of $$ from $$ is nearly $$ for any worst-case distance $$ smaller than $$. 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 $$ outside the box $$ on which codewords are evaluated, and asks the prover for the value at $$ of the interpolating polynomial of a random element of $$. Intuitively, the answer provided by the prover “forces” it to choose one codeword from a list of “pretenders” that are close to $$. 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 $$ for all $$. Under a plausible conjecture about the list decoding radius of Reed-Solomon codes, average distance from $$ is approximately $$ for all $$. 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 $$ to a constant arbitrarily close to $$.