{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T16:03:23Z","timestamp":1780934603472,"version":"3.54.1"},"publisher-location":"Cham","reference-count":77,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319566160","type":"print"},{"value":"9783319566177","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-56617-7_19","type":"book-chapter","created":{"date-parts":[[2017,3,30]],"date-time":"2017-03-30T22:33:34Z","timestamp":1490913214000},"page":"551-579","source":"Crossref","is-referenced-by-count":37,"title":["Computational Integrity with a Public Random String from Quasi-Linear PCPs"],"prefix":"10.1007","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Iddo","family":"Bentov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessandro","family":"Chiesa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ariel","family":"Gabizon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Genkin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matan","family":"Hamilis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Evgenya","family":"Pergament","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Riabzev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Silberstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eran","family":"Tromer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madars","family":"Virza","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,4,1]]},"reference":[{"issue":"3","key":"19_CR1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501\u2013555 (1998). Preliminary version in FOCS 1992","journal-title":"J. ACM"},{"issue":"1","key":"19_CR2","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70\u2013122 (1998). Preliminary version in FOCS 1992","journal-title":"J. ACM"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 21\u201332, STOC 1991(1991)","DOI":"10.1145\/103418.103428"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Lund, C.: Nondeterministic exponential time has two-prover interactive protocols. In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pp. 16\u201325, SFCS 1990 (1990)","DOI":"10.1109\/FSCS.1990.89520"},{"issue":"2","key":"19_CR5","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L Babai","year":"1988","unstructured":"Babai, L., Moran, S.: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class. J. Comput. Syst. Sci. 36(2), 254\u2013276 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"19_CR6","unstructured":"Bellare, M., Fuchsbauer, G., Scafuro, A.: Nizks with an untrusted CRS: Security in the face of parameter subversion. Cryptology ePrint Archive, Report 2016\/372 (2016). http:\/\/eprint.iacr.org\/"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/3-540-48071-4_28","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 92","author":"M Bellare","year":"1993","unstructured":"Bellare, M., Goldreich, O.: On defining proofs of knowledge. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 390\u2013420. Springer, Heidelberg (1993). doi: 10.1007\/3-540-48071-4_28"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: how to remove intractability assumptions. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pp. 113\u2013131, STOC 1988 (1988)","DOI":"10.1145\/62212.62223"},{"key":"19_CR9","unstructured":"Ben-Sasson, E., Ben-Tov, I., Gabizon, A., Riabzev, M.: Improved concrete efficiency and security analysis of Reed-Solomon PCPPS (2016). http:\/\/eccc.hpi-web.de\/report\/2016\/073"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Gabizon, A., Riabzev, M., Spooner, N.: Short interactive oracle proofs with constant query complexity, via composition and sumcheck. Electronic Colloquium on Computational Complexity, p. tR16-046 (2016)","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"19_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-662-49099-0_2","volume-title":"Theory of Cryptography","author":"E Ben-Sasson","year":"2016","unstructured":"Ben-Sasson, E., Chiesa, A., Gabizon, A., Virza, M.: Quasi-Linear size zero knowledge from linear-algebraic PCPs. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 33\u201364. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-49099-0_2"},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., Virza, M.: Zerocash: decentralized anonymous payments from Bitcoin. In: Proceedings of the 2014 IEEE Symposium on Security and Privacy, pp. 459\u2013474, SP 2014 (2014)","DOI":"10.1109\/SP.2014.36"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: Fast reductions from RAMs to delegatable succinct constraint satisfaction problems. In: Proceedings of the 4th Innovations in Theoretical Computer Science Conference, pp. 401\u2013414, ITCS 2013 (2013)","DOI":"10.1145\/2422436.2422481"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concrete efficiency of probabilistically-checkable proofs. In: Proceedings of the 45th ACM Symposium on the Theory of Computing, pp. 585\u2013594, STOC 2013 (2013)","DOI":"10.1145\/2488608.2488681"},{"key":"19_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-40084-1_6","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"E Ben-Sasson","year":"2013","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: verifying program executions succinctly and in zero knowledge. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 90\u2013108. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40084-1_6"},{"key":"19_CR16","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: TinyRAM Architecture Specification (2013). http:\/\/scipr-lab.org\/tinyram"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Green, M., Tromer, E., Virza, M.: Secure sampling of public parameters for succinct zero knowledge proofs. In: 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, 17\u201321 May 2015, pp. 287\u2013304, (2015). http:\/\/dx.doi.org\/10.1109\/SP.2015.25","DOI":"10.1109\/SP.2015.25"},{"key":"19_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-662-44381-1_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2014","author":"E Ben-Sasson","year":"2014","unstructured":"Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Scalable zero knowledge via cycles of elliptic curves. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 276\u2013294. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-44381-1_16"},{"key":"19_CR19","unstructured":"Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Succinct non-interactive zero knowledge for a von Neumann architecture. In: Proceedings of the 23rd USENIX Security Symposium, San Diego, 20\u201322 August 2014, pp. 781\u2013796 (2014)"},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Short PCPs verifiable in polylogarithmic time. In: Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pp. 120\u2013134, CCC 2005 (2005)","DOI":"10.1109\/CCC.2005.27"},{"issue":"4","key":"19_CR21","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1137\/S0097539705446810","volume":"36","author":"E Ben-Sasson","year":"2006","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput. 36(4), 889\u2013974 (2006). Preliminary versions of this paper have appeared in Proceedings of the 36th ACM Symposium on Theory of Computing and in Electronic Colloquium on Computational Complexity","journal-title":"SIAM J. Comput."},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Hamilis, M., Silberstein, M., Tromer, E.: Fast multiplication in binary fields on GPUS via register cache. In: Proceedings of the 2016 International Conference on Supercomputing, ICS 2016 (2016)","DOI":"10.1145\/2925426.2926259"},{"issue":"2","key":"19_CR23","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/050646445","volume":"38","author":"E Ben-Sasson","year":"2008","unstructured":"Ben-Sasson, E., Sudan, M.: Short PCPs with polylog query complexity. SIAM J. Comput. 38(2), 551\u2013607 (2008). Preliminary version appeared in STOC 2005","journal-title":"SIAM J. Comput."},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Sudan, M., Vadhan, S., Wigderson, A.: Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 612\u2013621, STOC 2003 (2003)","DOI":"10.1145\/780542.780631"},{"key":"19_CR25","volume-title":"Mathematical Theory of Connecting Networks and Telephone Traffic","author":"VE Bene\u0161","year":"1965","unstructured":"Bene\u0161, V.E.: Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press, New York (1965). http:\/\/opac.inria.fr\/record=b1083990"},{"key":"19_CR26","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: 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, pp. 326\u2013349, ITCS 2012 (2012)","DOI":"10.1145\/2090236.2090263"},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKs and proof-carrying data. In: Proceedings of the 45th ACM Symposium on the Theory of Computing, pp. 111\u2013120, STOC 2013 (2013)","DOI":"10.1145\/2488608.2488623"},{"key":"19_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-36594-2_18","volume-title":"Theory of Cryptography","author":"N Bitansky","year":"2013","unstructured":"Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., Ostrovsky, R.: Succinct non-interactive arguments via linear interactive proofs. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 315\u2013333. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-36594-2_18"},{"key":"19_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-662-49896-5_12","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"J Bootle","year":"2016","unstructured":"Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C.: Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 327\u2013357. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-49896-5_12"},{"key":"19_CR30","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/j.tcs.2015.07.030","volume":"600","author":"A Chiesa","year":"2015","unstructured":"Chiesa, A., Zhu, Z.A.: Shorter arithmetization of nondeterministic computations. Theor. Comput. Sci. 600, 107\u2013131 (2015). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397515006647","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"19_CR31","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1002\/j.1538-7305.1953.tb01433.x","volume":"32","author":"C Clos","year":"1953","unstructured":"Clos, C.: A study of non-blocking switching networks. Bell Syst. Tech. J. 32(2), 406\u2013424 (1953). http:\/\/dx.doi.org\/10.1002\/j.1538-7305.1953.tb01433.x","journal-title":"Bell Syst. Tech. J."},{"key":"19_CR32","doi-asserted-by":"crossref","unstructured":"Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: Proceedings of the 4th Symposium on Innovations in Theoretical Computer Science, pp. 90\u2013112, ITCS 2012 (2012)","DOI":"10.1145\/2090236.2090245"},{"issue":"1","key":"19_CR33","doi-asserted-by":"crossref","first-page":"25","DOI":"10.14778\/2047485.2047488","volume":"5","author":"G Cormode","year":"2011","unstructured":"Cormode, G., Thaler, J., Yi, K.: Verifying computations with streaming interactive proofs. Proc. VLDB Endowment 5(1), 25\u201336 (2011)","journal-title":"Proc. VLDB Endowment"},{"issue":"3","key":"19_CR34","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I Dinur","year":"2007","unstructured":"Dinur, I.: The PCP theorem by gap amplification. J. ACM 54(3), 12 (2007)","journal-title":"J. ACM"},{"issue":"4","key":"19_CR35","doi-asserted-by":"crossref","first-page":"975","DOI":"10.1137\/S0097539705446962","volume":"36","author":"I Dinur","year":"2006","unstructured":"Dinur, I., Reingold, O.: Assignment testers: towards a combinatorial proof of the PCP theorem. SIAM J. Comput. 36(4), 975\u20131024 (2006). http:\/\/dx.doi.org\/10.1137\/S0097539705446962","journal-title":"SIAM J. Comput."},{"key":"19_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/3-540-48071-4_15","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 92","author":"C Dwork","year":"1993","unstructured":"Dwork, C., Feige, U., Kilian, J., Naor, M., Safra, M.: Low communication 2-prover zero-knowledge proofs for NP. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 215\u2013227. Springer, Heidelberg (1993). doi: 10.1007\/3-540-48071-4_15"},{"key":"19_CR37","unstructured":"Ben-Sasson, E., Chiesa, N.S.A.: Interactive oracle proofs. IACR Cryptology ePrint Archive 2016, 116 (2016). http:\/\/eprint.iacr.org\/2016\/116"},{"key":"19_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 86","author":"A Fiat","year":"1987","unstructured":"Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186\u2013194. Springer, Heidelberg (1987). doi: 10.1007\/3-540-47721-7_12"},{"issue":"12","key":"19_CR39","doi-asserted-by":"crossref","first-page":"6265","DOI":"10.1109\/TIT.2010.2079016","volume":"56","author":"S Gao","year":"2010","unstructured":"Gao, S., Mateer, T.: Additive fast fourier transforms over finite fields. IEEE Trans. Inf. Theor. 56(12), 6265\u20136272 (2010). http:\/\/dx.doi.org\/10.1109\/TIT.2010.2079016","journal-title":"IEEE Trans. Inf. Theor."},{"key":"19_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-642-14623-7_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"R Gennaro","year":"2010","unstructured":"Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465\u2013482. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-14623-7_25"},{"key":"19_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1007\/978-3-642-38348-9_37","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"R Gennaro","year":"2013","unstructured":"Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626\u2013645. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-38348-9_37"},{"key":"19_CR42","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1145\/1162349.1162351","volume":"53","author":"O Goldreich","year":"2006","unstructured":"Goldreich, O., Sudan, M.: Locally testable codes and PCPs of almost-linear length. J. ACM 53, 558\u2013655 (2006). Preliminary version in STOC 2002","journal-title":"J. ACM"},{"key":"19_CR43","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 113\u2013122, STOC 2008 (2008)","DOI":"10.1145\/1374376.1374396"},{"issue":"1","key":"19_CR44","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S Goldwasser","year":"1989","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186\u2013208 (1989). Preliminary version appeared in STOC 1985","journal-title":"SIAM J. Comput."},{"key":"19_CR45","doi-asserted-by":"crossref","unstructured":"Greenberg, A.: Zcash, an untraceable bitcoin alternative, launches in alpha (January 2016). Wired.com . Accessed 20 Jan 2016","DOI":"10.1044\/leader.PPL.21012016.20"},{"key":"19_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-642-17373-8_19","volume-title":"Advances in Cryptology - ASIACRYPT 2010","author":"J Groth","year":"2010","unstructured":"Groth, J.: Short pairing-based non-interactive zero-knowledge arguments. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 321\u2013340. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-17373-8_19"},{"key":"19_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/978-3-642-25385-0_23","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2011","author":"J Groth","year":"2011","unstructured":"Groth, J.: Efficient zero-knowledge arguments from two-tiered homomorphic commitments. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 431\u2013448. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-25385-0_23"},{"issue":"3\u20134","key":"19_CR48","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/PL00001606","volume":"9","author":"P Harsha","year":"2000","unstructured":"Harsha, P., Sudan, M.: Small PCPs with low query complexity. Comput. Complex. 9(3\u20134), 157\u2013201 (2000). Preliminary version in STACS 1991","journal-title":"Comput. Complex."},{"issue":"4","key":"19_CR49","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"issue":"2","key":"19_CR50","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. J. ACM 21(2), 277\u2013292 (1974). http:\/\/doi.acm.org\/10.1145\/321812.321823","journal-title":"J. ACM"},{"key":"19_CR51","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Efficient arguments without short PCPs. In: Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, pp. 278\u2013291, CCC 2007 (2007)","DOI":"10.1109\/CCC.2007.10"},{"issue":"3","key":"19_CR52","doi-asserted-by":"crossref","first-page":"1121","DOI":"10.1137\/080725398","volume":"39","author":"Y Ishai","year":"2009","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge proofs from secure multiparty computation. SIAM J. Comput. 39(3), 1121\u20131152 (2009)","journal-title":"SIAM J. Comput."},{"key":"19_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/978-3-642-28914-9_9","volume-title":"Theory of Cryptography","author":"Y Ishai","year":"2012","unstructured":"Ishai, Y., Mahmoody, M., Sahai, A.: On efficient zero-knowledge PCPs. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 151\u2013168. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-28914-9_9"},{"key":"19_CR54","unstructured":"Ishai, Y., Mahmoody, M., Sahai, A., Xiao, D.: On zero-knowledge PCPs: Limitations, simplifications, and applications (2015). http:\/\/www.cs.virginia.edu\/mohammad\/files\/papers\/ZKPCPs-Full.pdf"},{"key":"19_CR55","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pp. 723\u2013732, STOC 1992 (1992)","DOI":"10.1145\/129712.129782"},{"key":"19_CR56","doi-asserted-by":"crossref","unstructured":"Kilian, J., Petrank, E., Tardos, G.: Probabilistically checkable proofs with zero knowledge. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 496\u2013505, STOC 1997 (1997)","DOI":"10.1145\/258533.258643"},{"key":"19_CR57","unstructured":"Kosba, A., Miller, A., Shi, E., Wen, Z., Papamanthou, C.: Hawk: The blockchain model of cryptography and privacy-preserving smart contracts. Cryptology ePrint Archive, Report 2015\/675 (2015). http:\/\/eprint.iacr.org\/"},{"key":"19_CR58","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-28914-9_10","volume-title":"Theory of Cryptography","author":"H Lipmaa","year":"2012","unstructured":"Lipmaa, H.: Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 169\u2013189. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-28914-9_10"},{"issue":"4","key":"19_CR59","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. J. ACM 39(4), 859\u2013868 (1992). http:\/\/doi.acm.org\/10.1145\/146585.146605","journal-title":"J. ACM"},{"key":"19_CR60","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/978-3-642-36594-2_17","volume-title":"Theory of Cryptography","author":"M Mahmoody","year":"2013","unstructured":"Mahmoody, M., Xiao, D.: Languages with efficient zero-knowledge PCPs are in SZK. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 297\u2013314. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-36594-2_17"},{"issue":"4","key":"19_CR61","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/S0097539795284959","volume":"30","author":"S Micali","year":"2000","unstructured":"Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253\u20131298 (2000). Preliminary version appeared in FOCS 1994","journal-title":"SIAM J. Comput."},{"key":"19_CR62","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/s10472-009-9169-y","volume":"56","author":"T Mie","year":"2009","unstructured":"Mie, T.: Short PCPPs verifiable in polylogarithmic time with O(1) queries. Ann. Math. Artif. Intell. 56, 313\u2013338 (2009)","journal-title":"Ann. Math. Artif. Intell."},{"key":"19_CR63","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1754399.1754402","volume":"57","author":"D Moshkovitz","year":"2008","unstructured":"Moshkovitz, D., Raz, R.: Two-query PCP with subconstant error. J. ACM 57, 1\u201329 (2008). Preliminary version appeared in FOCS 2008","journal-title":"J. ACM"},{"key":"19_CR64","unstructured":"Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (May 2009). http:\/\/www.bitcoin.org\/bitcoin.pdf"},{"key":"19_CR65","doi-asserted-by":"crossref","unstructured":"Parno, B., Gentry, C., Howell, J., Raykova, M.: Pinocchio: Nearly practical verifiable computation. In: Proceedings of the 34th IEEE Symposium on Security and Privacy, Oakland 2013, pp. 238\u2013252 (2013)","DOI":"10.1109\/SP.2013.47"},{"key":"19_CR66","doi-asserted-by":"crossref","unstructured":"Raz, R.: A parallel repetition theorem. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp. 447\u2013456, STOC 1995 (1995)","DOI":"10.1145\/225058.225181"},{"issue":"2","key":"19_CR67","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0108018","volume":"8","author":"IS Reed","year":"1960","unstructured":"Reed, I.S., Solomon, G.: Polynomial codes over certain finite fields. J. Soc. Industr. Appl. Math. 8(2), 300\u2013304 (1960). http:\/\/dx.doi.org\/10.1137\/0108018","journal-title":"J. Soc. Industr. Appl. Math."},{"key":"19_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-642-19379-8_24","volume-title":"Public Key Cryptography \u2013 PKC 2011","author":"JH Seo","year":"2011","unstructured":"Seo, J.H.: Round-efficient sub-linear zero-knowledge arguments for linear algebra. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 387\u2013402. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-19379-8_24"},{"key":"19_CR69","unstructured":"Setty, S., Blumberg, A.J., Walfish, M.: Toward practical and unconditional verification of remote computations. In: Proceedings of the 13th USENIX Conference on Hot Topics in Operating Systems, p. 29, HotOS 2011 (2011)"},{"key":"19_CR70","doi-asserted-by":"crossref","unstructured":"Setty, S., Braun, B., Vu, V., Blumberg, A.J., Parno, B., Walfish, M.: Resolving the conflict between generality and plausibility in verified computation. In: Proceedings of the 8th EuoroSys Conference, pp. 71\u201384, EuroSys 2013 (2013)","DOI":"10.1145\/2465351.2465359"},{"key":"19_CR71","unstructured":"Setty, S., McPherson, M., Blumberg, A.J., Walfish, M.: Making argument systems for outsourced computation practical (sometimes). In: Proceedings of the 2012 Network and Distributed System Security Symposium, NDSS 2012 (2012)"},{"key":"19_CR72","unstructured":"Setty, S., Vu, V., Panpalia, N., Braun, B., Blumberg, A.J., Walfish, M.: Taking proof-based verified computation a few steps closer to practicality. In: Proceedings of the 21st USENIX Security Symposium, pp. 253\u2013268, Security 2012 (2012)"},{"key":"19_CR73","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-642-40084-1_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"J Thaler","year":"2013","unstructured":"Thaler, J.: Time-optimal interactive proofs for circuit evaluation. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 71\u201389. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40084-1_5"},{"key":"19_CR74","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-78524-8_1","volume-title":"Theory of Cryptography","author":"P Valiant","year":"2008","unstructured":"Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time\/space efficiency. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 1\u201318. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-78524-8_1"},{"key":"19_CR75","doi-asserted-by":"crossref","unstructured":"Vu, V., Setty, S., Blumberg, A.J., Walfish, M.: A hybrid architecture for interactive verifiable computation. In: Proceedings of the 34th IEEE Symposium on Security and Privacy, Oakland 2013, pp. 223\u2013237 (2013)","DOI":"10.1109\/SP.2013.48"},{"key":"19_CR76","doi-asserted-by":"crossref","unstructured":"Wahby, R.S., Setty, S.T.V., Ren, Z., Blumberg, A.J., Walfish, M.: Efficient RAM and control flow in verifiable outsourced computation. In: 22nd Annual Network and Distributed System Security Symposium, NDSS 2015, San Diego, February 8\u201311 2014 (2015)","DOI":"10.14722\/ndss.2015.23097"},{"issue":"2","key":"19_CR77","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/2641562","volume":"58","author":"M Walfish","year":"2015","unstructured":"Walfish, M., Blumberg, A.J.: Verifying computations without reexecuting them. Commun. ACM 58(2), 74\u201384 (2015). http:\/\/doi.acm.org\/10.1145\/2641562","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2017"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-56617-7_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T08:02:35Z","timestamp":1568966555000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-56617-7_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319566160","9783319566177"],"references-count":77,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-56617-7_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}