Fall 2019

Improved Soundness Proving Proximity to Reed-Solomon Codes and STARKs

Wednesday, Sep. 25, 2019 2:00 pm2:30 pm PDT

Add to Calendar


Swastik Kopparty (Rutgers University) 

Given oracle access to some string w, we would like to verify (using few queries, 
with the aid of an interactive prover), that w is a codeword of the Reed-Solomon code.
An ingenious FFT-based protocol called FRI (Fast Reed-Solomon IOPP)
with low (and practical) complexity for both prover and verifier was recently given by [BBHR]. Follow-up work of [BKS] showed that FRI
rejects any w that is very far from the Reed-Solomon code with quite large probability.

* We give an improved (and tight) analysis for the soundness of FRI.

* We then give a new protocol called *DEEP-FRI* which has both (a) a better name, and
(b) further improved (and possibly optimal) soundness for this problem. It is based on querying
the polynomial outside the domain where it was initially evaluated.

* Finally we use this out-of-domain-sampling idea to improve the soundness of STARK proofs for
general computation.

Based on joint work with Eli Ben-Sasson, Lior Goldberg, and Shubhangi Saraf