{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T05:34:04Z","timestamp":1781242444706,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":63,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642365935","type":"print"},{"value":"9783642365942","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"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":[[2013]]},"DOI":"10.1007\/978-3-642-36594-2_18","type":"book-chapter","created":{"date-parts":[[2013,2,7]],"date-time":"2013-02-07T02:43:27Z","timestamp":1360205007000},"page":"315-333","source":"Crossref","is-referenced-by-count":189,"title":["Succinct Non-interactive Arguments via Linear Interactive Proofs"],"prefix":"10.1007","author":[{"given":"Nir","family":"Bitansky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessandro","family":"Chiesa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Omer","family":"Paneth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"18_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.\u00a01853, pp. 463\u2013474. Springer, Heidelberg (2000)"},{"key":"18_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/978-3-642-14165-2_14","volume-title":"Automata, Languages and Programming","author":"B. Applebaum","year":"2010","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: From Secrecy to Soundness: Efficient Verification via Secure Computation. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 152\u2013163. Springer, Heidelberg (2010)"},{"issue":"3","key":"18_CR3","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. Journal of the ACM\u00a045(3), 501\u2013555 (1998); Preliminary version in FOCS 1992","journal-title":"Journal of the ACM"},{"key":"18_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/978-3-642-32009-5_16","volume-title":"Proceedings of the 32nd Annual International Cryptology Conference (CRYPTO 2012)","author":"N. Bitansky","year":"2012","unstructured":"Bitansky, N., Chiesa, A.: Succinct arguments from multi-prover interactive proofs and their efficiency benefits. In: Safavi-Naini, R. (ed.) CRYPTO 2012. LNCS, vol.\u00a07417, pp. 255\u2013272. Springer, Heidelberg (2012)"},{"issue":"2","key":"18_CR5","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(88)90005-0","volume":"37","author":"G. Brassard","year":"1988","unstructured":"Brassard, G., Chaum, D., Cr\u00e9peau, C.: Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences\u00a037(2), 156\u2013189 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR6","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 (ITCS 2012), pp. 326\u2013349 (2012)","DOI":"10.1145\/2090236.2090263"},{"key":"18_CR7","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":"18_CR8","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Chiesa, A., Ishai, Y., Ostrovsky, R., Omer, P.: Succinct non-interactive arguments via linear interactive proofs. Cryptology ePrint Archive, Report 2012 (2012)","DOI":"10.1007\/978-3-642-36594-2_41"},{"key":"18_CR9","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"},{"issue":"5","key":"18_CR10","doi-asserted-by":"publisher","first-page":"1661","DOI":"10.1137\/070709244","volume":"38","author":"B. Barak","year":"2008","unstructured":"Barak, B., GoldreichUniversal, O.: arguments and their applications. SIAM Journal on Computing\u00a038(5), 1661\u20131694 (2008); Preliminary version appeared in CCC 2002","journal-title":"SIAM Journal on Computing"},{"key":"18_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-642-22792-9_7","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"S. Benabbas","year":"2011","unstructured":"Benabbas, S., Gennaro, R., Vahlis, Y.: Verifiable Delegation of Computation over Large Datasets. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.\u00a06841, pp. 111\u2013131. Springer, Heidelberg (2011)"},{"issue":"2","key":"18_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R.B. Boppana","year":"1987","unstructured":"Boppana, R.B., H\u00e5stad, J., Zachos, S.: Does co-NP have short interactive proofs? Information Processing Letters\u00a025(2), 127\u2013132 (1987)","journal-title":"Information Processing Letters"},{"key":"18_CR13","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.\u00a03152, pp. 273\u2013289. Springer, Heidelberg (2004)"},{"key":"18_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":"#cr-split#-18_CR15.1","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Harsha, P., Lachish, O., Matsliah, A.: Sound 3-Query PCPPs are Long. ACM Transactions on Computation Theory 1(2), 7:1-7:49 (2009)","DOI":"10.1145\/1595391.1595394"},{"key":"#cr-split#-18_CR15.2","unstructured":"Preliminary version appeared in: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 686-697. Springer, Heidelberg (2008)"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Boneh, D., Segev, G., Waters, B.: Targeted malleability: Homomorphic encryption for restricted computations. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS 1912), pp. 350\u2013366 (2012)","DOI":"10.1145\/2090236.2090264"},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Viola, E.: Pseudorandom bits for polynomials. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), pp. 41\u201351 (2007)","DOI":"10.1109\/FOCS.2007.42"},{"key":"18_CR18","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.\u00a06223, pp. 483\u2013501. Springer, Heidelberg (2010)"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS 2012), pp. 90\u2013112 (2012)","DOI":"10.1145\/2090236.2090245"},{"key":"18_CR20","unstructured":"Canetti, R., Riva, B., Rothblum, G.N.: Two 1-round protocols for delegation of computation. Cryptology ePrint Archive, Report 2011\/518 (2011)"},{"issue":"1","key":"18_CR21","doi-asserted-by":"publisher","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. Proceedings of the VLDB Endowment\u00a05(1), 25\u201336 (2011)","journal-title":"Proceedings of the VLDB Endowment"},{"key":"18_CR22","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 - CRYPTO \u201991","author":"I.B. Damg\u00e5rd","year":"1992","unstructured":"Damg\u00e5rd, I.B.: Towards Practical Public Key Systems Secure against Chosen Ciphertext Attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol.\u00a0576, pp. 445\u2013456. Springer, Heidelberg (1992)"},{"key":"18_CR23","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.\u00a05028, pp. 175\u2013185. Springer, Heidelberg (2008)"},{"key":"18_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-642-28914-9_4","volume-title":"Theory of Cryptography","author":"I.. B. Damg\u00e5rd","year":"2012","unstructured":"Damg\u00e5rd, I. B., Faust, S., Hazay, C.: Secure Two-Party Computation with Low Communication. In: Cramer, R. (ed.) TCC 2012. LNCS, vol.\u00a07194, pp. 54\u201374. Springer, Heidelberg (2012)"},{"key":"18_CR25","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 - CRYPTO \u201992","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.\u00a0740, pp. 215\u2013227. Springer, Heidelberg (1993)"},{"issue":"1","key":"18_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-009-0258-4","volume":"18","author":"Z. Dvir","year":"2009","unstructured":"Dvir, Z., Gabizon, A., Wigderson, A.: Extractors and rank extractors for polynomial sources. Computational Complexity\u00a018(1), 1\u201358 (2009)","journal-title":"Computational Complexity"},{"key":"18_CR27","unstructured":"Dwork, C., Langberg, M., Naor, M., Nissim, K., Reingold, O.: Succinct NP proofs and spooky interactions (December 2004), www.openu.ac.il\/home\/mikel\/papers\/spooky.ps"},{"issue":"4","key":"18_CR28","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","volume":"31","author":"T. Gamal El","year":"1985","unstructured":"El Gamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory\u00a031(4), 469\u2013472 (1985)","journal-title":"IEEE Transactions on Information Theory"},{"key":"18_CR29","doi-asserted-by":"crossref","unstructured":"Fiore, D., Gennaro, R.: Publicly verifiable delegation of large polynomials and matrix computations, with applications. Cryptology ePrint Archive, Report 2012\/281 (2012)","DOI":"10.1145\/2382196.2382250"},{"key":"18_CR30","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":"18_CR31","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.\u00a06223, pp. 465\u2013482. Springer, Heidelberg (2010)"},{"key":"18_CR32","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"},{"issue":"4","key":"18_CR33","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0020-0190(98)00116-1","volume":"67","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., H\u00e5stad, J.: On the complexity of interactive proofs with bounded communication. Information Processing Letters\u00a067(4), 205\u2013214 (1998)","journal-title":"Information Processing Letters"},{"key":"18_CR34","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 (STOC 2008), pp. 113\u2013122 (2008)","DOI":"10.1145\/1374376.1374396"},{"key":"18_CR35","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)"},{"issue":"1","key":"18_CR36","doi-asserted-by":"publisher","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 Journal on Computing\u00a018(1), 186\u2013208 (1989); Preliminary version appeared in STOC 1985","journal-title":"SIAM Journal on Computing"},{"key":"18_CR37","doi-asserted-by":"crossref","unstructured":"Gabizon, A., Raz, R.: Deterministic extractors for affine sources over large fields. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 407\u2013418 (2005)","DOI":"10.1109\/SFCS.2005.31"},{"key":"18_CR38","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.\u00a06477, pp. 321\u2013340. Springer, Heidelberg (2010)"},{"issue":"1\/2","key":"18_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-002-0169-0","volume":"11","author":"O. Goldreich","year":"2002","unstructured":"Goldreich, O., Vadhan, S., Wigderson, A.: On interactive proofs with a laconic prover. Computational Complexity\u00a011(1\/2), 1\u201353 (2002)","journal-title":"Computational Complexity"},{"key":"18_CR40","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"},{"issue":"1","key":"18_CR41","doi-asserted-by":"publisher","first-page":"119","DOI":"10.4086\/toc.2005.v001a007","volume":"1","author":"J. H\u00e5stad","year":"2005","unstructured":"H\u00e5stad, J., Khot, S.: Query efficient PCPs with perfect completeness. Theory of Computing\u00a01(1), 119\u2013148 (2005)","journal-title":"Theory of Computing"},{"key":"18_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1007\/BFb0055744","volume-title":"Advances in Cryptology - CRYPTO \u201998","author":"S. Hada","year":"1998","unstructured":"Hada, S., Tanaka, T.: On the Existence of 3-Round Zero-Knowledge Protocols. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol.\u00a01462, pp. 408\u2013423. Springer, Heidelberg (1998)"},{"key":"18_CR43","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":"18_CR44","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":"18_CR45","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":"18_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/978-3-642-03356-8_9","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"Y.T. Kalai","year":"2009","unstructured":"Kalai, Y.T., Raz, R.: Probabilistically Checkable Arguments. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 143\u2013159. Springer, Heidelberg (2009)"},{"key":"18_CR47","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.\u00a07194, pp. 169\u2013189. Springer, Heidelberg (2012)"},{"key":"18_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-13190-5_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"V. Lyubashevsky","year":"2010","unstructured":"Lyubashevsky, V., Peikert, C., Regev, O.: On Ideal Lattices and Learning with Errors over Rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 1\u201323. Springer, Heidelberg (2010)"},{"key":"18_CR49","doi-asserted-by":"crossref","unstructured":"Meir, O.: Combinatorial PCPs with short proofs. In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity (CCC 2012) (2012)","DOI":"10.1109\/CCC.2012.14"},{"issue":"4","key":"18_CR50","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/S0097539795284959","volume":"30","author":"S. Micali","year":"2000","unstructured":"Micali, S.: Computationally sound proofs. SIAM Journal on Computing\u00a030(4), 1253\u20131298 (2000); Preliminary version appeared in FOCS 1994","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"18_CR51","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. Journal of Mathematical Cryptology\u00a02(4), 343\u2013363 (2008)","journal-title":"Journal of Mathematical Cryptology"},{"key":"18_CR52","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 - CRYPTO 2003","author":"M. Naor","year":"2003","unstructured":"Naor, M.: On Cryptographic Assumptions and Challenges. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol.\u00a02729, pp. 96\u2013109. Springer, Heidelberg (2003)"},{"key":"18_CR53","doi-asserted-by":"crossref","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC 1990), pp. 213\u2013223 (1990)","DOI":"10.1145\/100216.100244"},{"key":"18_CR54","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/3-540-48910-X_16","volume-title":"Advances in Cryptology - EUROCRYPT \u201999","author":"P. Paillier","year":"1999","unstructured":"Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.\u00a01592, pp. 223\u2013238. Springer, Heidelberg (1999)"},{"key":"18_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-642-34961-4_28","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2012","author":"C. Petit","year":"2012","unstructured":"Petit, C., Quisquater, J.-J.: On Polynomial Systems Arising from a Weil Descent. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol.\u00a07658, pp. 451\u2013466. Springer, Heidelberg (2012)"},{"key":"18_CR56","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. Cryptology ePrint Archive, Report 2012\/622 (2012)","DOI":"10.1145\/2465351.2465359"},{"key":"18_CR57","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 (HotOS 2013), p. 29 (2011)"},{"issue":"4","key":"18_CR58","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"Shamir, A.: IP = PSPACE. Journal of the ACM\u00a039(4), 869\u2013877 (1992)","journal-title":"Journal of the ACM"},{"key":"18_CR59","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":"18_CR60","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 (Security 2012) (2012)"},{"key":"18_CR61","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/3-540-08353-7_135","volume-title":"Mathematical Foundations of Computer Science 1977","author":"L.G. Valiant","year":"1977","unstructured":"Valiant, L.G.: Graph-Theoretic Arguments in Low-Level Complexity. In: Gruska, J. (ed.) MFCS 1977. LNCS, vol.\u00a053, pp. 162\u2013176. Springer, Heidelberg (1977)"},{"key":"18_CR62","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.\u00a03580, pp. 140\u2013152. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36594-2_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T20:11:24Z","timestamp":1745957484000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36594-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642365935","9783642365942"],"references-count":63,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36594-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}