Welcome to the resource topic for 2019/336
Title:
DEEP-FRI: Sampling Outside the Box Improves Soundness
Authors: Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, 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.
ePrint: https://eprint.iacr.org/2019/336
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .