Document Open Access Logo

Fast Reed-Solomon Interactive Oracle Proofs of Proximity

Authors Eli Ben-Sasson , Iddo Bentov, Yinon Horesh, Michael Riabzev

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.14.pdf
  • Filesize: 0.53 MB
  • 17 pages

Document Identifiers

Author Details

Eli Ben-Sasson
  • Technion, Haifa, Israel
Iddo Bentov
  • Cornell University, Ithaca, NY, USA
Yinon Horesh
  • Technion - Israel Institute of Technology, Haifa, Israel
Michael Riabzev
  • Technion - Israel Institute of Technology, Haifa, Israel

Funding

Supported by the European Research Council under POC grant OMIP - DLV-693423, an Israel Science Foundation grant 1501/14 and the USA-Israel binational science fund, grant # 2014359.

Cite AsGet BibTex

Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.14

Abstract

The family of Reed-Solomon (RS) codes plays a prominent role in the construction of quasilinear probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs) with perfect zero knowledge and polylogarithmic verifiers. The large concrete computational complexity required to prove membership in RS codes is one of the biggest obstacles to deploying such PCP/IOP systems in practice. To advance on this problem we present a new interactive oracle proof of proximity (IOPP) for RS codes; we call it the Fast RS IOPP (FRI) because (i) it resembles the ubiquitous Fast Fourier Transform (FFT) and (ii) the arithmetic complexity of its prover is strictly linear and that of the verifier is strictly logarithmic (in comparison, FFT arithmetic complexity is quasi-linear but not strictly linear). Prior RS IOPPs and PCPs of proximity (PCPPs) required super-linear proving time even for polynomially large query complexity. For codes of block-length N, the arithmetic complexity of the (interactive) FRI prover is less than 6 * N, while the (interactive) FRI verifier has arithmetic complexity <= 21 * log N, query complexity 2 * log N and constant soundness - words that are delta-far from the code are rejected with probability min{delta * (1-o(1)),delta_0} where delta_0 is a positive constant that depends mainly on the code rate. The particular combination of query complexity and soundness obtained by FRI is better than that of the quasilinear PCPP of [Ben-Sasson and Sudan, SICOMP 2008], even with the tighter soundness analysis of [Ben-Sasson et al., STOC 2013; ECCC 2016]; consequently, FRI is likely to facilitate better concretely efficient zero knowledge proof and argument systems. Previous concretely efficient PCPPs and IOPPs suffered a constant multiplicative factor loss in soundness with each round of "proof composition" and thus used at most O(log log N) rounds. We show that when delta is smaller than the unique decoding radius of the code, FRI suffers only a negligible additive loss in soundness. This observation allows us to increase the number of "proof composition" rounds to Theta(log N) and thereby reduce prover and verifier running time for fixed soundness.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive proof systems
Keywords
  • Interactive proofs
  • low degree testing
  • Reed Solomon codes
  • proximity testing

Metrics

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

Related Versions

References

  1. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and hardness of approximation problems. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 14-23, 1992. Google Scholar
  2. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, 1998. Preliminary version in FOCS '92. Google Scholar
  3. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM, 45(1):70-122, 1998. Preliminary version in FOCS '92. Google Scholar
  4. László Babai. Trading group theory for randomness. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing, STOC '85, pages 421-429, 1985. Google Scholar
  5. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC '91, pages 21-32, 1991. Google Scholar
  6. László Babai, Lance Fortnow, and Carsten Lund. Nondeterministic exponential time has two-prover interactive protocols. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, FOCS '90, pages 16-25, 1990. Google Scholar
  7. Eli Ben-Sasson, Iddo Bentov, Alessandro Chiesa, Ariel Gabizon, Daniel Genkin, Matan Hamilis, Evgenya Pergament, Michael Riabzev, Mark Silberstein, Eran Tromer, and Madars Virza. Computational integrity with a public random string from quasi-linear PCPs. IACR Cryptology ePrint Archive, 2016:646, 2016. URL: http://eprint.iacr.org/2016/646.
  8. Eli Ben-Sasson, Iddo Bentov, Ariel Gabizon, and Michael Riabzev. A security analysis of probabilistically checkable proofs. Electronic Colloquium on Computational Complexity (ECCC), 23:149, 2016. URL: http://eccc.hpi-web.de/report/2016/149.
  9. Eli Ben-Sasson, Iddo Bentov, Ariel Gabizon, and Michael Riabzev. A security analysis of probabilistically checkable proofs. Electronic Colloquium on Computational Complexity (ECCC), 23:149, 2016. URL: http://eccc.hpi-web.de/report/2016/149.
  10. Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, and Michael Riabzev. Fast Reed-Solomon interactive oracle proofs of proximity (2nd revision). Electronic Colloquium on Computational Complexity (ECCC), 24:134, 2017. URL: https://eccc.weizmann.ac.il/report/2017/134.
  11. Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity, 2017. Unpublished manuscript. Google Scholar
  12. 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.
  13. Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Short interactive oracle proofs with constant query complexity, via composition and sumcheck. Electronic Colloquium on Computational Complexity (ECCC), 23:46, 2016. Google Scholar
  14. Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, and Madars Virza. Quasilinear-size zero knowledge from linear-algebraic PCPs. In Proceedings of the 13th Theory of Cryptography Conference, TCC '16, pages 33-64, 2016. Google Scholar
  15. Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from Bitcoin. In Proceedings of the 2014 IEEE Symposium on Security and Privacy, SP '14, 2014. Google Scholar
  16. Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. On the concrete efficiency of probabilistically-checkable proofs. In Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC '13, pages 585-594, 2013. Google Scholar
  17. Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. SNARKs for C: Verifying program executions succinctly and in zero knowledge. In Proceedings of the 33rd Annual International Cryptology Conference, CRYPTO '13, pages 90-108, 2013. Google Scholar
  18. Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. Tinyram architecture specification v2. 00, 2013. Technical report, SCIPR Lab, 2013. URL: http://www.scipr-lab.org/doc/TinyRAM-spec-0.991.pdf.
  19. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive Oracle Proofs, pages 31-60. Springer Berlin Heidelberg, Berlin, Heidelberg, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53644-5_2.
  20. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan. Short PCPs verifiable in polylogarithmic time. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, CCC '05, pages 120-134, 2005. Google Scholar
  21. 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
  22. Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and Henning Stichtenoth. Constant rate pcps for circuit-sat with sublinear query complexity. J. ACM, 63(4):32:1-32:57, 2016. URL: http://dx.doi.org/10.1145/2901294.
  23. 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
  24. Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, pages 326-349, 2012. Google Scholar
  25. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci., 47(3):549-595, 1993. URL: http://dx.doi.org/10.1016/0022-0000(93)90044-W.
  26. James W Cooley and John W Tukey. An algorithm for the machine calculation of complex fourier series. Mathematics of computation, 19(90):297-301, 1965. Google Scholar
  27. Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Practical verified computation with streaming interactive proofs. In Proceedings of the 4th Symposium on Innovations in Theoretical Computer Science, ITCS '12, pages 90-112, 2012. Google Scholar
  28. Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM, 54(3):12, 2007. Google Scholar
  29. Irit Dinur and Elazar Goldenberg. Locally testing direct product in the low error range. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 613-622, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.26.
  30. Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP theorem. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS '04, pages 155-164, 2004. Google Scholar
  31. Amos Fiat and Adi Shamir. How to prove yourself: practical solutions to identification and signature problems. In Proceedings of the 6th Annual International Cryptology Conference, CRYPTO '86, pages 186-194, 1986. Google Scholar
  32. K. Friedl and M. Sudan. Some improvements to total degree tests. In Proceedings Third Israel Symposium on the Theory of Computing and Systems, pages 190-198, Jan 1995. URL: http://dx.doi.org/10.1109/ISTCS.1995.377032.
  33. Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In Proceedings of the 32nd Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT '13, pages 626-645, 2013. Google Scholar
  34. Oded Goldreich and Shmuel Safra. A combinatorial consistency lemma with application to proving the pcp theorem. SIAM Journal on Computing, 29(4):1132-1154, 2000. URL: http://dx.doi.org/10.1137/S0097539797315744.
  35. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for Muggles. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC '08, pages 113-122, 2008. Google Scholar
  36. Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, and Shubhangi Saraf. Locally testable and locally correctable codes approaching the gilbert-varshamov bound. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2073-2091, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.135.
  37. Johan Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798-859, 2001. Google Scholar
  38. Daira Hopwood, Sean Bowe, Taylor Hornby, and Nathan Wilcox, March 2017. URL: https://github.com/zcash/zips/blob/master/protocol/protocol.pdf.
  39. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. New direct-product testers and 2-query pcps. SIAM Journal on Computing, 41(6):1722-1768, 2012. URL: http://dx.doi.org/10.1137/09077299X.
  40. Yuval Ishai, Mohammad Mahmoody, Amit Sahai, and David Xiao. On zero-knowledge PCPs: Limitations, simplifications, and applications, 2015. Available at URL: http://www.cs.virginia.edu/~mohammad/files/papers/ZKPCPs-Full.pdf.
  41. Yuval Ishai and Mor Weiss. Probabilistically checkable proofs of proximity with zero-knowledge. In Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings, pages 121-145, 2014. URL: http://dx.doi.org/10.1007/978-3-642-54242-8_6.
  42. Yael Kalai and Ran Raz. Interactive PCP. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP '08, pages 536-547, 2008. Google Scholar
  43. Joe Kilian. A note on efficient zero-knowledge proofs and arguments. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC '92, pages 723-732, 1992. Google Scholar
  44. Joe Kilian, Erez Petrank, and Gábor Tardos. Probabilistically checkable proofs with zero knowledge. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC '97, pages 496-505, 1997. Google Scholar
  45. Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 202-215, 2016. URL: http://dx.doi.org/10.1145/2897518.2897523.
  46. 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
  47. Gregory Maxwell. Zero knowledge contingent payment, 2011. [Online; accessed 13-October-2017]. Google Scholar
  48. Silvio Micali. Computationally sound proofs. SIAM Journal on Computing, 30(4):1253-1298, 2000. Preliminary version appeared in FOCS '94. Google Scholar
  49. Silvio Micali. Computationally sound proofs. SIAM J. Comput., 30(4):1253-1298, 2000. URL: http://dx.doi.org/10.1137/S0097539795284959.
  50. Thilo Mie. Short PCPPs verifiable in polylogarithmic time with o(1) queries. Annals of Mathematics and Artificial Intelligence, 56:313-338, 2009. Google Scholar
  51. Dana Moshkovitz and Ran Raz. Two-query PCP with subconstant error. J. ACM, 57(5):29:1-29:29, 2010. URL: http://dx.doi.org/10.1145/1754399.1754402.
  52. M. Peck. A blockchain currency that beat s bitcoin on privacy [news]. IEEE Spectrum, 53(12):11-13, December 2016. URL: http://dx.doi.org/10.1109/MSPEC.2016.7761864.
  53. 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
  54. John Proos and Christof Zalka. Shor’s discrete logarithm quantum algorithm for elliptic curves. Quantum Info. Comput., 3(4):317-344, 2003. URL: http://dl.acm.org/citation.cfm?id=2011528.2011531.
  55. Ran Raz. A parallel repetition theorem. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, STOC '95, pages 447-456, 1995. Google Scholar
  56. I. S. Reed and G. Solomon. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8(2):300-304, 1960. URL: http://dx.doi.org/10.1137/0108018.
  57. 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: http://dx.doi.org/10.1145/2897518.2897652.
  58. Ronitt Rubinfeld and Madhu Sudan. Self-testing polynomial functions efficiently and over rational domains. In Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 27-29 January 1992, Orlando, Florida., pages 23-32, 1992. URL: http://dl.acm.org/citation.cfm?id=139404.139410.
  59. Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869-877, 1992. Google Scholar
  60. P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124-134, Nov 1994. URL: http://dx.doi.org/10.1109/SFCS.1994.365700.
  61. Paul Valiant. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In Proceedings of the 5th Conference on Theory of Cryptography, TCC'08, pages 1-18, Berlin, Heidelberg, 2008. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=1802614.1802616.
  62. Michael Walfish and Andrew J. Blumberg. Verifying computations without reexecuting them. Commun. ACM, 58(2):74-84, 2015. URL: http://dx.doi.org/10.1145/2641562.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact