BenSasson, Eli ;
Goldberg, Lior ;
Kopparty, Swastik ;
Saraf, Shubhangi
DEEPFRI: Sampling Outside the Box Improves Soundness
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 δfar in relative Hamming distance from a linear code V  this is the worstcase assumption  then most elements of U are almostδ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 δ_V of the code V, i.e., only when δ < 1(1δ_V)^(1/4).
First, we increase the soundnessbound to the "oneandahalf Johnson" function of δ_V and show that the average distance of U from V is nearly δ for any worstcase distance δ smaller than 1(1δ_V)^(1/3). 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 δ for all δ < 1(1δ_V)^(1/2). Under a plausible conjecture about the list decoding radius of ReedSolomon codes, average distance from V is approximately δ for all δ. 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. The 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.
BibTeX  Entry
@InProceedings{bensasson_et_al:LIPIcs:2020:11690,
author = {Eli BenSasson and Lior Goldberg and Swastik Kopparty and Shubhangi Saraf},
title = {{DEEPFRI: Sampling Outside the Box Improves Soundness}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {5:15:32},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11690},
URN = {urn:nbn:de:0030drops116901},
doi = {10.4230/LIPIcs.ITCS.2020.5},
annote = {Keywords: Interactive Oracle Proofs of Proximity, STARK, Low Degree Testing}
}
06.01.2020
Keywords: 

Interactive Oracle Proofs of Proximity, STARK, Low Degree Testing 
Seminar: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Issue date: 

2020 
Date of publication: 

06.01.2020 