Paper 2019/336
DEEPFRI: Sampling Outside the Box Improves Soundness
Eli BenSasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf
Abstract
Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worstcasetoaveragecase reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. The previous state of the art by [BenSasson, 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 worstcase 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 soundnessbound to the “oneandahalf Johnson” function of $\delta_V$ and show that the average distance of $U$ from $V$ is nearly $\delta$ for any worstcase distance $\delta$ smaller than $1  \sqrt[3]{1  \delta_V}$. This bound is tight, which is somewhat surprising because the oneandahalf 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 worstcasetoaveragecase 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 ReedSolomon 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 capacityachieving listdecodable codes. Finally, we use the DEEP technique to devise two new protocols: • An Interactive Oracle Proof of Proximity (IOPP) for RS codes, called DEEPFRI. This soundness of the protocol improves upon that of the FRI protocol of [BenSasson 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 (ZKSTARKs) in [BenSasson et al., eprint 2018]. The new protocol, called DEEPALI, improves soundness of this crucial step from a small constant $< 1/8$ to a constant arbitrarily close to $1$.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 STARKIOPInteractive ProofsInteractive Oracle Proofs of Proximity
 Contact author(s)

eli @ starkware co
lior @ starkware co
swastik kopparty @ gmail com
shubhangi saraf @ gmail com  History
 20190403: received
 Short URL
 https://ia.cr/2019/336
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/336, author = {Eli BenSasson and Lior Goldberg and Swastik Kopparty and Shubhangi Saraf}, title = {DEEPFRI: Sampling Outside the Box Improves Soundness}, howpublished = {Cryptology ePrint Archive, Paper 2019/336}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/336}}, url = {https://eprint.iacr.org/2019/336} }