Fast Reed-Solomon interactive oracle proofs of proximity. (English) Zbl 1499.68141
Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 14, 17 p. (2018).
Summary: 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\cdot N\), while the (interactive) FRI verifier has arithmetic complexity \(\le 21\cdot\log N\), query complexity \(2\cdot\log N\) and constant soundness – words that are \(\delta\)-far from the code are rejected with probability \(\min\{\delta\cdot(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 [E. Ben-Sasson and M. Sudan, SIAM J. Comput. 38, No. 2, 551–607 (2009; Zbl 1172.68025)], even with the tighter soundness analysis of [E. Ben-Sasson et al., in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. New York, NY: Association for Computing Machinery (ACM). 585–594 (2013; Zbl 1293.94054); A security analysis of probabilistically checkable proofs. Electronic Colloquium on Computational Complexity (ECCC), Techn. Rep. TR16-149 (2016), http://eccc.hpi-web.de/report/2016/149]; 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.
For the entire collection see [Zbl 1392.68012].
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\cdot N\), while the (interactive) FRI verifier has arithmetic complexity \(\le 21\cdot\log N\), query complexity \(2\cdot\log N\) and constant soundness – words that are \(\delta\)-far from the code are rejected with probability \(\min\{\delta\cdot(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 [E. Ben-Sasson and M. Sudan, SIAM J. Comput. 38, No. 2, 551–607 (2009; Zbl 1172.68025)], even with the tighter soundness analysis of [E. Ben-Sasson et al., in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. New York, NY: Association for Computing Machinery (ACM). 585–594 (2013; Zbl 1293.94054); A security analysis of probabilistically checkable proofs. Electronic Colloquium on Computational Complexity (ECCC), Techn. Rep. TR16-149 (2016), http://eccc.hpi-web.de/report/2016/149]; 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.
For the entire collection see [Zbl 1392.68012].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 94A60 | Cryptography |
| 94B15 | Cyclic codes |
Software:
SNARKs for CReferences:
| [1] | Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and hardness of approximation problems. In {\it Proceedings of the 33rd Annual} {\it Symposium on Foundations of Computer Science}, pages 14-23, 1992. · Zbl 0977.68539 |
| [2] | Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. {\it Journal of the ACM}, 45(3):501- 555, 1998. Preliminary version in FOCS ’92. · Zbl 1065.68570 |
| [3] | Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of NP. {\it Journal of the ACM}, 45(1):70-122, 1998. Preliminary version in FOCS ’92. · Zbl 0903.68076 |
| [4] | László Babai. Trading group theory for randomness. In {\it Proceedings of the 17th Annual} {\it ACM Symposium on Theory of Computing}, STOC ’85, pages 421-429, 1985. |
| [5] | László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In {\it Proceedings of the 23rd Annual ACM Symposium on Theory of} {\it Computing}, STOC ’91, pages 21-32, 1991. |
| [6] | László Babai, Lance Fortnow, and Carsten Lund. Nondeterministic exponential time has two-prover interactive protocols. In {\it Proceedings of the 31st Annual Symposium on Found-} {\it ations of Computer Science}, FOCS ’90, pages 16-25, 1990. |
| [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.{\it 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. {\it Electronic Colloquium on Computational Complexity} {\it (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. {\it Electronic Colloquium on Computational Complexity} {\it (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). {\it Electronic Colloquium on Computational} {\it 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. |
| [12] | Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. On probabilistic checking in perfect zero knowledge. {\it Electronic} {\it 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. {\it Electronic Colloquium on Computational Complexity (ECCC)}, 23:46, 2016. |
| [14] | :14 |
| [15] | :16 |
| [16] | :17 |
| [17] | Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, and Madars Virza. Quasilinear-size zero knowledge from linear-algebraic PCPs. In {\it Proceedings of the 13th Theory of Cryptography} {\it Conference}, TCC ’16, pages 33-64, 2016. · Zbl 1375.94101 |
| [18] | :15 |
| [19] | Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from Bitcoin. In {\it Proceedings of the 2014 IEEE Symposium on Security and Privacy}, SP ’14, 2014. |
| [20] | Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. On the concrete efficiency of probabilistically-checkable proofs. In {\it Proceedings of the 45th ACM Symposium} {\it on the Theory of Computing}, STOC ’13, pages 585-594, 2013. · Zbl 1293.94054 |
| [21] | Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. SNARKs for C: Verifying program executions succinctly and in zero knowledge. In {\it Proceed-} {\it ings of the 33rd Annual International Cryptology Conference}, CRYPTO ’13, pages 90-108, 2013. · Zbl 1317.68050 |
| [22] | 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. |
| [23] | Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner.{\it Interactive Oracle Proofs}, pages 31-60.Springer Berlin Heidelberg, Berlin, Heidelberg, 2016.doi:10.1007/ 978-3-662-53644-5_2. |
| [24] | Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan. Short PCPs verifiable in polylogarithmic time. In {\it Proceedings of the 20th Annual IEEE Confer-} {\it ence on Computational Complexity}, CCC ’05, pages 120-134, 2005. |
| [25] | Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCPs of proximity, shorter PCPs, and applications to coding. {\it SIAM Journal on} {\it Computing}, 36(4):889-974, 2006. · Zbl 1118.68071 |
| [26] | Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and Henning Stichtenoth. Constant rate pcps for circuit-sat with sublinear query complexity. {\it J. ACM}, 63(4):32:1-32:57, 2016. doi:10.1145/2901294. · Zbl 1410.68140 |
| [27] | Eli Ben-Sasson and Madhu Sudan. Short PCPs with polylog query complexity. {\it SIAM} {\it Journal on Computing}, 38(2):551-607, 2008. Preliminary version appeared in STOC ’05. · Zbl 1172.68025 |
| [28] | Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In {\it Proceedings of the 3rd Innovations in Theoretical Computer Science Conference}, ITCS ’12, pages 326-349, 2012. · Zbl 1347.68129 |
| [29] | Manuel Blum, Michael Luby, and Ronitt Rubinfeld.Self-testing/correcting with applications to numerical problems.{\it J. Comput. Syst. Sci.}, 47(3):549-595, 1993.doi: 10.1016/0022-0000(93)90044-W. · Zbl 0795.68131 |
| [30] | James W Cooley and John W Tukey. An algorithm for the machine calculation of complex fourier series. {\it Mathematics of computation}, 19(90):297-301, 1965. · Zbl 0127.09002 |
| [31] | Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Practical verified computation with streaming interactive proofs. In {\it Proceedings of the 4th Symposium on Innovations} {\it in Theoretical Computer Science}, ITCS ’12, pages 90-112, 2012. · Zbl 1347.68157 |
| [32] | Irit Dinur. The PCP theorem by gap amplification. {\it Journal of the ACM}, 54(3):12, 2007. · Zbl 1292.68074 |
| [33] | Irit Dinur and Elazar Goldenberg. Locally testing direct product in the low error range. In {\it 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October} {\it 25-28, 2008, Philadelphia, PA, USA}, pages 613-622, 2008. doi:10.1109/FOCS.2008.26. |
| [34] | Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP theorem. In {\it Proceedings of the 45th Annual IEEE Symposium on Foundations of} {\it Computer Science}, FOCS ’04, pages 155-164, 2004. |
| [35] | Amos Fiat and Adi Shamir. How to prove yourself: practical solutions to identification and signature problems. In {\it Proceedings of the 6th Annual International Cryptology Conference}, CRYPTO ’86, pages 186-194, 1986. · Zbl 0636.94012 |
| [36] | K. Friedl and M. Sudan. Some improvements to total degree tests. In {\it Proceedings Third} {\it Israel Symposium on the Theory of Computing and Systems}, pages 190-198, Jan 1995. doi:10.1109/ISTCS.1995.377032. |
| [37] | Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In {\it Proceedings of the 32nd Annual International} {\it Conference on Theory and Application of Cryptographic Techniques}, EUROCRYPT ’13, pages 626-645, 2013. · Zbl 1300.94056 |
| [38] | Oded Goldreich and Shmuel Safra. A combinatorial consistency lemma with application to proving the pcp theorem. {\it SIAM Journal on Computing}, 29(4):1132-1154, 2000. doi: 10.1137/S0097539797315744. · Zbl 0948.68084 |
| [39] | Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for Muggles. In {\it Proceedings of the 40th Annual ACM Symposium on} {\it Theory of Computing}, STOC ’08, pages 113-122, 2008. · Zbl 1231.68135 |
| [40] | Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, and Shubhangi Saraf. Locally testable and locally correctable codes approaching the gilbertvarshamov bound. In {\it Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium} {\it on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19}, pages 2073-2091, 2017. doi:10.1137/1.9781611974782.135. · Zbl 1443.94111 |
| [41] | Johan Hr astad. Some optimal inapproximability results. {\it Journal of the ACM}, 48(4):798- 859, 2001. · Zbl 1127.68405 |
| [42] | Daira Hopwood, Sean Bowe, Taylor Hornby, and Nathan Wilcox, March 2017. URL: https: //github.com/zcash/zips/blob/master/protocol/protocol.pdf. |
| [43] | Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. New direct-product testers and 2-query pcps. {\it SIAM Journal on Computing}, 41(6):1722-1768, 2012. doi:10.1137/ 09077299X. · Zbl 1275.68069 |
| [44] | Yuval Ishai, Mohammad Mahmoody, Amit Sahai, and David Xiao. On zero-knowledge PCPs: Limitations, simplifications, and applications, 2015. Available at http://www.cs. virginia.edu/ mohammad/files/papers/ZKPCPs-Full.pdf. |
| [45] | Yuval Ishai and Mor Weiss.Probabilistically checkable proofs of proximity with zeroknowledge. In {\it Theory of Cryptography - 11th Theory of Cryptography Conference, TCC} {\it 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings}, pages 121-145, 2014. doi: 10.1007/978-3-642-54242-8_6. · Zbl 1323.94117 |
| [46] | Yael Kalai and Ran Raz. Interactive PCP. In {\it Proceedings of the 35th International Col-} {\it loquium on Automata, Languages and Programming}, ICALP ’08, pages 536-547, 2008. · Zbl 1155.68504 |
| [47] | Joe Kilian. A note on efficient zero-knowledge proofs and arguments. In {\it Proceedings of the} {\it 24th Annual ACM Symposium on Theory of Computing}, STOC ’92, pages 723-732, 1992. |
| [48] | Joe Kilian, Erez Petrank, and Gábor Tardos. Probabilistically checkable proofs with zero knowledge. In {\it Proceedings of the 29th Annual ACM Symposium on Theory of Computing}, STOC ’97, pages 496-505, 1997. · Zbl 0963.68192 |
| [49] | Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf.High-rate locallycorrectable and locally-testable codes with sub-polynomial query complexity. In {\it Proceed-} {\it ings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016,} {\it Cambridge, MA, USA, June 18-21, 2016}, pages 202-215, 2016. doi:10.1145/2897518. 2897523. · Zbl 1377.94077 |
| [50] | Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. {\it Journal of the ACM}, 39(4):859-868, 1992. · Zbl 0799.68097 |
| [51] | Gregory Maxwell. Zero knowledge contingent payment, 2011. [Online; accessed 13-October2017]. |
| [52] | Silvio Micali. Computationally sound proofs. {\it SIAM Journal on Computing}, 30(4):1253- 1298, 2000. Preliminary version appeared in FOCS ’94. · Zbl 1009.68053 |
| [53] | Silvio Micali. Computationally sound proofs. {\it SIAM J. Comput.}, 30(4):1253-1298, 2000. doi:10.1137/S0097539795284959. · Zbl 1009.68053 |
| [54] | Thilo Mie. Short PCPPs verifiable in polylogarithmic time with o(1) queries. {\it Annals of} {\it Mathematics and Artificial Intelligence}, 56:313-338, 2009. · Zbl 1184.68464 |
| [55] | Dana Moshkovitz and Ran Raz.Two-query PCP with subconstant error.{\it J. ACM}, 57(5):29:1-29:29, 2010. doi:10.1145/1754399.1754402. · Zbl 1327.68110 |
| [56] | M. Peck. A blockchain currency that beat s bitcoin on privacy [news]. {\it IEEE Spectrum}, 53(12):11-13, December 2016. doi:10.1109/MSPEC.2016.7761864. |
| [57] | Alexander Polishchuk and Daniel A. Spielman. Nearly-linear size holographic proofs. In {\it Proceedings of the 26th Annual ACM Symposium on Theory of Computing}, STOC ’94, pages 194-203, 1994. · Zbl 1345.68180 |
| [58] | John Proos and Christof Zalka. Shor’s discrete logarithm quantum algorithm for elliptic curves. {\it Quantum Info. Comput.}, 3(4):317-344, 2003. URL: http://dl.acm.org/citation. cfm?id=2011528.2011531. · Zbl 1152.81800 |
| [59] | Ran Raz. A parallel repetition theorem. In {\it Proceedings of the 27th Annual ACM Symposium} {\it on Theory of Computing}, STOC ’95, pages 447-456, 1995. · Zbl 0978.68527 |
| [60] | I. S. Reed and G. Solomon. Polynomial codes over certain finite fields. {\it Journal of the Society} {\it for Industrial and Applied Mathematics}, 8(2):300-304, 1960. doi:10.1137/0108018. · Zbl 0099.34403 |
| [61] | Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. In {\it Proceedings of the 48th Annual ACM SIGACT Sym-} {\it posium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016}, pages 49-62, 2016. doi:10.1145/2897518.2897652. · Zbl 1373.68274 |
| [62] | Ronitt Rubinfeld and Madhu Sudan. Self-testing polynomial functions efficiently and over rational domains. In {\it Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium} {\it on Discrete Algorithms, 27-29 January 1992, Orlando, Florida.}, pages 23-32, 1992. URL: http://dl.acm.org/citation.cfm?id=139404.139410. · Zbl 0834.68076 |
| [63] | Adi Shamir. IP = PSPACE. {\it Journal of the ACM}, 39(4):869-877, 1992. · Zbl 0799.68096 |
| [64] | P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In {\it Proceedings 35th Annual Symposium on Foundations of Computer Science}, pages 124-134, Nov 1994. doi:10.1109/SFCS.1994.365700. |
| [65] | Paul Valiant. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In {\it 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. · Zbl 1162.68448 |
| [66] | Michael Walfish and Andrew J. Blumberg. Verifying computations without reexecuting them. {\it Commun. ACM}, 58(2):74-84, 2015. doi:10.1145/2641562. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
