{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T11:04:59Z","timestamp":1777287899335,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":52,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642320088","type":"print"},{"value":"9783642320095","type":"electronic"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"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":[[2012]]},"DOI":"10.1007\/978-3-642-32009-5_16","type":"book-chapter","created":{"date-parts":[[2012,8,6]],"date-time":"2012-08-06T06:40:28Z","timestamp":1344235228000},"page":"255-272","source":"Crossref","is-referenced-by-count":39,"title":["Succinct Arguments from Multi-prover Interactive Proofs and Their Efficiency Benefits"],"prefix":"10.1007","author":[{"given":"Nir","family":"Bitansky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Chiesa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_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., Ostrovsky, R., Rajagopalan, S.R.: 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. 1853, pp. 463\u2013474. Springer, Heidelberg (2000)"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Chiesa, A.: Succinct arguments from multi-prover interactive proofs and their efficiency benefits. Cryptology ePrint Archive (2012)","DOI":"10.1007\/978-3-642-32009-5_16"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Brassard, G., Chaum, D., Cr\u00e9peau, C.: Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences 37(2), 156\u2013189 (1988)","DOI":"10.1016\/0022-0000(88)90005-0"},{"key":"16_CR4","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. Cryptology ePrint Archive, Report 2011\/443 (2011)","DOI":"10.1145\/2090236.2090263"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for snarks and proof-carrying data. Cryptology ePrint Archive, Report 2012\/095 (2012)","DOI":"10.1145\/2488608.2488623"},{"key":"16_CR6","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, SFCS 1990, pp. 16\u201325 (1990)","DOI":"10.1109\/FSCS.1990.89520"},{"key":"16_CR7","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, STOC 1991, pp. 21\u201332 (1991)","DOI":"10.1145\/103418.103428"},{"key":"#cr-split#-16_CR8.1","doi-asserted-by":"crossref","unstructured":"Barak, B., Goldreich, O.: Universal arguments and their applications. SIAMJournal on Computing 38(5), 1661\u20131694 (2008);","DOI":"10.1137\/070709244"},{"key":"#cr-split#-16_CR8.2","unstructured":"Preliminary version appeared in CCC 2002"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Boppana, R.B., H\u00e5stad, J., Zachos, S.: Does co-NP have short interactive proofs? Information Processing Letters 25(2), 127\u2013132 (1987)","DOI":"10.1016\/0020-0190(87)90232-8"},{"key":"16_CR10","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, STOC 1988, pp. 113\u2013131 (1988)","DOI":"10.1145\/62212.62223"},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/978-3-540-28628-8_17","volume-title":"Advances in Cryptology \u2013 CRYPTO 2004","author":"M Bellare","year":"2004","unstructured":"Bellare, M., Palacio, A.: The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 273\u2013289. Springer, Heidelberg (2004)"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-540-30539-2_4","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2004","author":"M Bellare","year":"2004","unstructured":"Bellare, M., Palacio, A.: Towards Plaintext-Aware Public-Key Encryption Without Random Oracles. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 48\u201362. Springer, Heidelberg (2004)"},{"key":"16_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. Cryptology ePrint Archive, Report Report 2012\/071 (2012)","DOI":"10.1145\/2422436.2422481"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concrete-efficiency threshold of probabilistically-checkable proofs. Electronic Colloquium on Computational Complexity, TR12-045 (2012)","DOI":"10.1145\/2488608.2488681"},{"key":"16_CR15","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, CCC 2005, pp. 120\u2013134 (2005)","DOI":"10.1109\/CCC.2005.27"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Sudan, M.: Short PCPs with polylog query complexity. SIAM Journal on Computing 38(2), 551\u2013607 (2008)","DOI":"10.1137\/050646445"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Boneh, D., Segev, G., Waters, B.: Targeted malleability: Homomorphic encryption for restricted computations. Cryptology ePrint Archive, Report 2011\/311 (2011)","DOI":"10.1145\/2090236.2090264"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011 (2011)","DOI":"10.1109\/FOCS.2011.12"},{"key":"16_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-540-30576-7_2","volume-title":"Theory of Cryptography","author":"R Canetti","year":"2005","unstructured":"Canetti, R., Halevi, S., Steiner, M.: Hardness Amplification of Weakly Verifiable Puzzles. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 17\u201333. Springer, Heidelberg (2005)"},{"key":"16_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-3-642-14623-7_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"K-M Chung","year":"2010","unstructured":"Chung, K.-M., Kalai, Y., Vadhan, S.: Improved Delegation of Computation Using Fully Homomorphic Encryption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 483\u2013501. Springer, Heidelberg (2010)"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Chung, K.-M., Liu, F.-H.: Parallel Repetition Theorems for Interactive Arguments. In:Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 19\u201336. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-11799-2_2"},{"key":"16_CR22","unstructured":"Chiesa, A., Tromer, E.: Proof-carrying data and hearsay arguments from signature cards. In: Proceedings of the 1st Symposium on Innovations in Computer Science, ICS 2010, pp. 310\u2013331 (2010)"},{"key":"16_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1007\/3-540-46766-1_36","volume-title":"Advances in Cryptology \u2013 CRYPTO \u201991","author":"I Damg\u00e5rd","year":"1992","unstructured":"Damg\u00e5rd, I.: Towards Practical Public Key Systems Secure against Chosen Ciphertext Attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 445\u2013456. Springer, Heidelberg (1992)"},{"key":"16_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-540-69407-6_21","volume-title":"Logic and Theory of Algorithms","author":"G Crescenzo Di","year":"2008","unstructured":"Di Crescenzo, G., Lipmaa, H.: Succinct NP Proofs from an Extractability Assumption. In: Beckmann, A., Dimitracopoulos, C., L\u00f6we, B. (eds.) CiE 2008. LNCS, vol. 5028, pp. 175\u2013185. Springer, Heidelberg (2008)"},{"key":"16_CR25","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I., Faust, S., Hazay, C.: Secure two-party computation with low communication. Cryptology ePrint Archive, Report 2011\/508 (2011)","DOI":"10.1007\/978-3-642-28914-9_4"},{"key":"16_CR26","unstructured":"Dwork, C., Langberg,M., Naor,M., Nissim, K., Reingold, O.: Succinct NP proofs and spooky interactions (December 2004), http:\/\/www.openu.ac.il\/home\/mikel\/papers\/spooky.ps"},{"key":"16_CR27","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 \u2013 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. 263, pp. 186\u2013194. Springer, Heidelberg (1987)"},{"key":"16_CR28","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. Cryptology ePrint Archive, Report 2012\/215 (2012)","DOI":"10.1007\/978-3-642-38348-9_37"},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"Goldreich, O., H\u00e5stad, J.: On the complexity of interactive proofs with bounded communication. Information Processing Letters 67(4), 205\u2013214 (1998)","DOI":"10.1016\/S0020-0190(98)00116-1"},{"key":"16_CR30","unstructured":"Goldwasser, S., Lin, H., Rubinstein, A.: Delegation of computation without rejection problem from designated verifier CS-proofs. Cryptology ePrint Archive, Report 2011\/456 (2011)"},{"key":"#cr-split#-16_CR31.1","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(1), 186\u2013208 (1989);","DOI":"10.1137\/0218012"},{"key":"#cr-split#-16_CR31.2","unstructured":"Preliminary version appeared in STOC 1985"},{"key":"16_CR32","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 \u2013 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)"},{"key":"16_CR33","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Vadhan, S., Wigderson, A.: On interactive proofs with a laconic prover. Computational Complexity 11(1\/2), 1\u201353 (2002)","DOI":"10.1007\/s00037-002-0169-0"},{"key":"16_CR34","doi-asserted-by":"crossref","unstructured":"Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 99\u2013108 (2011)","DOI":"10.1145\/1993636.1993651"},{"key":"16_CR35","doi-asserted-by":"crossref","unstructured":"Haitner, I.: A parallel repetition theorem for any interactive argument. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 241\u2013250 (2009)","DOI":"10.1109\/FOCS.2009.50"},{"key":"16_CR36","unstructured":"Harsha, P.: Robust PCPs of Proximity and Shorter PCPs. PhD thesis, MIT, EECS (September 2004)"},{"key":"16_CR37","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, CCC 2007, pp. 278\u2013291 (2007)","DOI":"10.1109\/CCC.2007.10"},{"key":"16_CR38","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, STOC 1992, pp. 723\u2013732 (1992)","DOI":"10.1145\/129712.129782"},{"key":"16_CR39","doi-asserted-by":"crossref","unstructured":"Lipmaa, H.: Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. Cryptology ePrint Archive, Report 2011\/009 (2011)","DOI":"10.1007\/978-3-642-28914-9_10"},{"key":"#cr-split#-16_CR40.1","doi-asserted-by":"crossref","unstructured":"Micali, S.: Computationally sound proofs. SIAM Journal on Computing 30(4), 1253\u20131298 (2000);","DOI":"10.1137\/S0097539795284959"},{"key":"#cr-split#-16_CR40.2","unstructured":"Preliminary version appeared in FOCS 1994"},{"key":"#cr-split#-16_CR41.1","doi-asserted-by":"crossref","unstructured":"Moshkovitz, D., Raz, R.: Two-query PCP with subconstant error. Journal of the ACM 57, 1\u201329 (2008);","DOI":"10.1145\/1754399.1754402"},{"key":"#cr-split#-16_CR41.2","unstructured":"Preliminary version appeared in FOCS 2008"},{"key":"16_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-540-45146-4_6","volume-title":"Advances in Cryptology \u2013 CRYPTO 2003","author":"M Naor","year":"2003","unstructured":"Naor, M.: On Cryptographic Assumptions and Challenges. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 96\u2013109. Springer, Heidelberg (2003)"},{"key":"16_CR43","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC 1997, pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"16_CR44","doi-asserted-by":"crossref","unstructured":"Rothblum, G.N., Vadhan, S.: Are PCPs inherent in efficient arguments? In: Proceedings of the 24th IEEE Annual Conference on Computational Complexity, CCC 2009, pp. 81\u201392 (2009)","DOI":"10.1109\/CCC.2009.40"},{"key":"16_CR45","doi-asserted-by":"crossref","unstructured":"Shamir, A.: IP = PSPACE. Journal of the ACM 39(4), 869\u2013877 (1992)","DOI":"10.1145\/146585.146609"},{"key":"16_CR46","doi-asserted-by":"crossref","unstructured":"Ta-Shma, A.: A note on PCP vs.MIP. Information Processing Letters 58, 135\u2013140 (1996)","DOI":"10.1016\/0020-0190(96)00043-9"},{"key":"16_CR47","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)"},{"key":"16_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/11523468_12","volume-title":"Automata, Languages and Programming","author":"H Wee","year":"2005","unstructured":"Wee, H.: On Round-Efficient Argument Systems. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 140\u2013152. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32009-5_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,25]],"date-time":"2022-01-25T19:08:11Z","timestamp":1643137691000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32009-5_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642320088","9783642320095"],"references-count":52,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32009-5_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}