{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:59:28Z","timestamp":1781078368309,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642033551","type":"print"},{"value":"9783642033568","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-03356-8_9","type":"book-chapter","created":{"date-parts":[[2009,8,18]],"date-time":"2009-08-18T14:00:39Z","timestamp":1250604039000},"page":"143-159","source":"Crossref","is-referenced-by-count":39,"title":["Probabilistically Checkable Arguments"],"prefix":"10.1007","author":[{"given":"Yael Tauman","family":"Kalai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/3-540-45022-X_39","volume-title":"Automata, Languages and Programming","author":"W. Aiello","year":"2000","unstructured":"Aiello, W., Bhatt, S.N., Ostrovsky, R., Rajagopalan, S.: Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, p. 463. Springer, Heidelberg (2000) (manuscript withdrown by the authors prior to ICALP)"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan. M., Szegedy, M.: Proof Verification and Hardness of Approximation Problems. In: FOCS 1992, pp. 14\u201323 (1992); also in J. ACM 45(3), 501\u2013555 (1998)","DOI":"10.1109\/SFCS.1992.267823"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Safra, S.: Probabilistic Checking of Proofs: A New Characterization of NP. In: FOCS 1992, pp. 2\u201313 (1992); also in J. ACM 45(1), 70\u2013122 (1998)","DOI":"10.1145\/273865.273901"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Barak, B.: How to Go Beyond the Black-Box Simulation Barrier. In: FOCS 2001, pp. 106\u2013115 (2001)","DOI":"10.1109\/SFCS.2001.959885"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. In: FOCS 1990, pp. 16\u201325 (1990); also In Computational Complexity 1, 3\u201340 (1991)","DOI":"10.1007\/BF01200056"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/3-540-48910-X_28","volume-title":"Advances in Cryptology - EUROCRYPT \u201999","author":"C. Cachin","year":"1999","unstructured":"Cachin, C., Micali, S., Stadler, M.: Computationally Private Information Retrieval with Polylogarithmic Communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.\u00a01592, pp. 402\u2013414. Springer, Heidelberg (1999)"},{"issue":"6","key":"9_CR7","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/293347.293350","volume":"45","author":"B. Chor","year":"1998","unstructured":"Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private Information Retrieval. J. ACM\u00a045(6), 965\u2013981 (1998)","journal-title":"J. ACM"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/11681878_3","volume-title":"Theory of Cryptography","author":"I. Damgard","year":"2006","unstructured":"Damgard, I., Fazio, N., Nicolosi, A.: Non-interactive Zero-Knowledge from Homomorphic Encryption. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol.\u00a03876, pp. 41\u201359. Springer, Heidelberg (2006)"},{"key":"9_CR9","unstructured":"Dwork, C., Langberg, M., Naor, M., Nissim, K., Reingold, O.: Succinct Proofs for NP and Spooky Interactions (unpublished manuscript)"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Feige, U., Goldwasser, S., Lovasz, L., Safra, S., Szegedy, M.: Interactive Proofs and the Hardness of Approximating Cliques. In: FOCS 1991, pp. 2\u201312 (1991); also in J. ACM 43(2), 268\u2013292 (1996)","DOI":"10.1145\/226643.226652"},{"key":"9_CR11","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 - CRYPTO \u201986","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.\u00a0263, pp. 186\u2013194. Springer, Heidelberg (1987)"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of Instance Compression and Succinct PCPs for NP. In: STOC 2008, pp. 133\u2013142 (2008)","DOI":"10.1145\/1374376.1374398"},{"key":"9_CR13","unstructured":"Goldwasser, S., Kalai, Y.T.: On the (In)security of the Fiat-Shamir Paradigm. In: FOCS 2003 (2003)"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Rothblum, G.: Delegating Computation: Interactive Proofs for Muggles. In: FOCS 2007, pp. 113\u2013122 (2007)","DOI":"10.1145\/1374376.1374396"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Harnik, H., Naor, M.: On the Compressibility of NP instances and Cryptographic Applications. In: FOCS 2006, pp. 719\u2013728 (2006)","DOI":"10.1109\/FOCS.2006.54"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. In: FOCS 1997, pp. 364\u2013373 (1997)","DOI":"10.1109\/SFCS.1997.646125"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Kalai, Y.T., Raz, R.: Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP. In: FOCS 2006, pp. 355\u2013366 (2006)","DOI":"10.1109\/FOCS.2006.74"},{"key":"9_CR18","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":"Y.T. 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.\u00a05126, pp. 536\u2013547. Springer, Heidelberg (2008)"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: STOC 1992, pp. 723\u2013732 (1992)","DOI":"10.1145\/129712.129782"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic Methods for Interactive Proof Systems. In: FOCS 1990, pp. 2\u201310 (1990); also in J. ACM 39(4), 859\u2013868 (1992)","DOI":"10.1145\/146585.146605"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Micali, S.: CS Proofs (Extended Abstracts). In: FOCS 1994, pp. 436\u2013453 (1994)","DOI":"10.1109\/SFCS.1994.365746"},{"issue":"4","key":"9_CR22","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"Shamir, A.: IP=PSPACE. J. ACM\u00a039(4), 869\u2013877 (1992)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology - CRYPTO 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03356-8_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T19:46:25Z","timestamp":1739303185000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03356-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642033551","9783642033568"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03356-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}