{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T10:58:22Z","timestamp":1772276302951,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662490983","type":"print"},{"value":"9783662490990","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,12,24]],"date-time":"2015-12-24T00:00:00Z","timestamp":1450915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49099-0_2","type":"book-chapter","created":{"date-parts":[[2015,12,23]],"date-time":"2015-12-23T13:42:48Z","timestamp":1450878168000},"page":"33-64","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs"],"prefix":"10.1007","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Chiesa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ariel","family":"Gabizon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madars","family":"Virza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,12,24]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1017\/S0963548398003411","volume":"8","author":"N Alon","year":"1999","unstructured":"Alon, N.: Combinatorial Nullstellensatz. Comb. Probab. Comput. 8, 7\u201329 (1999)","journal-title":"Comb. Probab. Comput."},{"key":"2_CR2","doi-asserted-by":"publisher","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. JACM 45, 501\u2013555 (1998)","journal-title":"JACM"},{"key":"2_CR3","doi-asserted-by":"publisher","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. JACM 45, 70\u2013122 (1998)","journal-title":"JACM"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC 1991 (1991)","DOI":"10.1145\/103418.103428"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex. 1, 3\u201340 (1991)","journal-title":"Comput. Complex."},{"key":"2_CR6","doi-asserted-by":"publisher","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, 254\u2013276 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/3-540-48071-4_28","volume-title":"Advances in Cryptology - CRYPTO 1992","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)"},{"key":"2_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/0-387-34799-2_4","volume-title":"Advances in Cryptology - CRYPTO 1988","author":"M Ben-Or","year":"1990","unstructured":"Ben-Or, M., Goldreich, O., Goldwasser, S., H\u00e5stad, J., Kilian, J., Micali, S., Rogaway, P.: Everything provable is provable in zero-knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 37\u201356. Springer, Heidelberg (1990)"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: how to remove intractability assumptions. In: STOC 1988 (1988)","DOI":"10.1145\/62212.62223"},{"key":"2_CR10","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: ITCS 2013 (2013)","DOI":"10.1145\/2422436.2422481"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concrete efficiency of probabilistically-checkable proofs. In: STOC 2013 (2013)","DOI":"10.1145\/2488608.2488681"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Robust PCPs of proximity, shorter PCPs and applications to coding. In: STOC 2004 (2004)","DOI":"10.1145\/1007352.1007361"},{"key":"2_CR13","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Short PCPs verifiable in polylogarithmic time. In: CCC 2005 (2005)"},{"key":"2_CR14","doi-asserted-by":"publisher","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, 889\u2013974 (2006)","journal-title":"SIAM J. Comput."},{"key":"2_CR15","doi-asserted-by":"publisher","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, 551\u2013607 (2008)","journal-title":"SIAM J. Comput."},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/978-3-662-43948-7_14","volume-title":"Automata, Languages, and Programming","author":"E Ben-Sasson","year":"2014","unstructured":"Ben-Sasson, E., Viola, E.: Short PCPs with projection queries. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 163\u2013173. Springer, Heidelberg (2014)"},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"12:1","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I Dinur","year":"2007","unstructured":"Dinur, I.: The PCP theorem by gap amplification. JACM 54, 12:1\u201312:44 (2007)","journal-title":"JACM"},{"key":"2_CR18","unstructured":"Dinur, I., Reingold, O.: Assignment testers: towards a combinatorial proof of the PCP theorem. In: FOCS 2004 (2004)"},{"key":"2_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/3-540-48071-4_15","volume-title":"Advances in Cryptology - CRYPTO 1992","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)"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: STOC 1985 (1985)","DOI":"10.1145\/22145.22178"},{"key":"2_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-642-14623-7_10","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"V Goyal","year":"2010","unstructured":"Goyal, V., Ishai, Y., Mahmoody, M., Sahai, A.: Interactive locking, zero-knowledge PCPs, and unconditional cryptography. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 173\u2013190. Springer, Heidelberg (2010)"},{"key":"2_CR22","doi-asserted-by":"publisher","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, 157\u2013201 (2000)","journal-title":"Comput. Complex."},{"key":"2_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/3-540-48184-2_4","volume-title":"Advances in Cryptology - CRYPTO 1987","author":"R Impagliazzo","year":"1988","unstructured":"Impagliazzo, R., Yung, M.: Direct minimum knowledge computations. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 40\u201351. Springer, Heidelberg (1988)"},{"key":"2_CR24","doi-asserted-by":"publisher","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, 1121\u20131152 (2009)","journal-title":"SIAM J. Comput."},{"key":"2_CR25","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)"},{"key":"2_CR26","unstructured":"Ishai, Y., Mahmoody, M., Sahai, A., Xiao, D.: On zero-knowledge PCPs: limitations, simplifications, and applications (2015). \n                      http:\/\/www.cs.virginia.edu\/mohammad\/files\/papers\/ZKPCPs-Full.pdf"},{"key":"2_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/978-3-540-70583-3_44","volume-title":"Automata, Languages and Programming","author":"YT Kalai","year":"2008","unstructured":"Kalai, Y.T., Raz, R.: Interactive PCP. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 536\u2013547. Springer, Heidelberg (2008)"},{"key":"2_CR28","doi-asserted-by":"crossref","unstructured":"Kilian, J., Petrank, E., Tardos, G.: Probabilistically checkable proofs with zero knowledge. In: STOC 1997 (1997)","DOI":"10.1145\/258533.258643"},{"key":"2_CR29","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1007\/BF01200756","volume":"15","author":"D Lapidot","year":"1995","unstructured":"Lapidot, D., Shamir, A.: A one-round, two-prover, zero-knowledge protocol for NP. Combinatorica 15, 204\u2013214 (1995)","journal-title":"Combinatorica"},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H., Noam, N.: Algebraic methods for interactive proof systems. JACM 39, 859\u2013868 (1992)","journal-title":"JACM"},{"key":"2_CR31","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)"},{"key":"2_CR32","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1515\/JMC.2008.016","volume":"2","author":"T Mie","year":"2008","unstructured":"Mie, T.: Polylogarithmic two-round argument systems. J. Math. Cryptol. 2, 343\u2013363 (2008)","journal-title":"J. Math. Cryptol."},{"key":"2_CR33","unstructured":"Ostrovsky, R., Wigderson, A.: One-way functions are essential for non-trivial zero-knowledge. In: ISTCS 1993 (1993)"},{"key":"2_CR34","doi-asserted-by":"crossref","unstructured":"Polishchuk, A., Spielman, D.A.: Nearly-linear size holographic proofs. In: STOC 1994 (1994)","DOI":"10.1145\/195058.195132"},{"key":"2_CR35","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A Shamir","year":"1992","unstructured":"Shamir, A.: IP = PSPACE. JACM 39, 869\u2013877 (1992)","journal-title":"JACM"},{"key":"2_CR36","unstructured":"Spielman, D.: Computationally efficient error-correcting codes and holographic proofs. Ph.D. thesis, Massachusetts Institute of Technology (1995)"},{"key":"2_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1007\/3-540-48523-6_64","volume-title":"Automata, Languages and Programming","author":"M Szegedy","year":"1999","unstructured":"Szegedy, M.: Many-valued logics and holographic proofs. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 676\u2013686. Springer, Heidelberg (1999)"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49099-0_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T20:05:17Z","timestamp":1578513917000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49099-0_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,24]]},"ISBN":["9783662490983","9783662490990"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49099-0_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,24]]},"assertion":[{"value":"24 December 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}