DEEP-FRI: Sampling Outside the Box Improves Soundness

Authors Eli Ben-Sasson , Lior Goldberg, Swastik Kopparty, Shubhangi Saraf



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.5.pdf
  • Filesize: 0.69 MB
  • 32 pages

Document Identifiers

Author Details

Eli Ben-Sasson
  • StarkWare Industries Ltd., Netanya, Israel
Lior Goldberg
  • StarkWare Industries Ltd., Netanya, Israel
Swastik Kopparty
  • StarkWare Industries Ltd., Netanya, Israel
Shubhangi Saraf
  • Department of Mathematics and Department of Computer Science, Rutgers University

Acknowledgements

We thank Rishabh Bhadauria for pointing out an omission in a previous version of the paper.

Cite AsGet BibTex

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: Sampling Outside the Box Improves Soundness. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 5:1-5:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.5

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 δ-far in relative Hamming distance from a linear code V - this is the worst-case 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 soundness-bound to the "one-and-a-half Johnson" function of δ_V and show that the average distance of U from V is nearly δ for any worst-case distance δ smaller than 1-(1-δ_V)^(1/3). 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 δ for all δ < 1-(1-δ_V)^(1/2). Under a plausible conjecture about the list decoding radius of Reed-Solomon codes, average distance from V 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. The 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive proof systems
  • Mathematics of computing → Coding theory
Keywords
  • Interactive Oracle Proofs of Proximity
  • STARK
  • Low Degree Testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: Lightweight Sublinear Arguments Without a Trusted Setup. In Proceedings of the 24th ACM Conference on Computer and Communications Security, October 2017. Google Scholar
  2. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Report 2018/046, 2018. Available at URL: https://eprint.iacr.org/2018/046.
  3. Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, and Michael Riabzev. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), 2018. URL: https://eccc.weizmann.ac.il/report/2017/134.
  4. Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. On Probabilistic Checking in Perfect Zero Knowledge. Electronic Colloquium on Computational Complexity (ECCC), 23:156, 2016. URL: http://eccc.hpi-web.de/report/2016/156.
  5. Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent Succinct Arguments for R1CS. IACR Cryptology ePrint Archive, 2018:828, 2018. URL: https://eprint.iacr.org/2018/828.
  6. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive Oracle Proofs. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, Oct. 31 - Nov. 3, 2016, Proceedings, Part II, pages 31-60, 2016. URL: https://doi.org/10.1007/978-3-662-53644-5_2.
  7. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM Journal on Computing, 36(4):889-974, 2006. Google Scholar
  8. Eli Ben-Sasson, Swastik Kopparty, and Jaikumar Radhakrishnan. Subspace polynomials and limits to list decoding of Reed-Solomon codes. IEEE Trans. Information Theory, 56(1):113-120, 2010. Google Scholar
  9. Eli Ben-Sasson, Swastik Kopparty, and Shubhangi Saraf. Worst-Case to Average Case Reductions for the Distance to a Code. In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, pages 24:1-24:23, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.24.
  10. Eli Ben-Sasson, Swastik Kopparty, and Shubhangi Saraf. Worst-case to average case reductions for the distance to a code. Electronic Colloquium on Computational Complexity (ECCC), 25:90, 2018. URL: https://eccc.weizmann.ac.il/report/2018/090.
  11. Eli Ben-Sasson and Madhu Sudan. Short PCPs with Polylog Query Complexity. SIAM Journal on Computing, 38(2):551-607, 2008. Preliminary version appeared in STOC '05. Google Scholar
  12. Alessandro Chiesa, Peter Manohar, and Igor Shinkar. On Axis-Parallel Tests for Tensor Product Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, pages 39:1-39:22, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.39.
  13. Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM, 54(3):12, 2007. Google Scholar
  14. Venkatesan Guruswami. Algorithmic Results in List Decoding. Foundations and Trends® in Theoretical Computer Science, 2(2):107-195, 2007. URL: https://doi.org/10.1561/0400000007.
  15. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic Methods for Interactive Proof Systems. Journal of the ACM, 39(4):859-868, 1992. Google Scholar
  16. Alexander Polishchuk and Daniel A. Spielman. Nearly-linear size holographic proofs. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC '94, pages 194-203, 1994. Google Scholar
  17. Alexander A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987. Google Scholar
  18. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 49-62, 2016. URL: https://doi.org/10.1145/2897518.2897652.
  19. Ron M. Roth. Introduction to coding theory. Cambridge University Press, 2006. Google Scholar
  20. Guy N. Rothblum, Salil Vadhan, and Avi Wigderson. Interactive proofs of proximity: delegating computation in sublinear time. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 793-802. ACM, 2013. Google Scholar
  21. Atri Rudra and Mary Wootters. Every list-decodable code for high noise has abundant near-optimal rate puncturings. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 764-773, 2014. URL: https://doi.org/10.1145/2591796.2591797.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail