{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,31]],"date-time":"2026-10-31T19:54:39Z","timestamp":1793476479712,"version":"4.5.0"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642383472","type":"print"},{"value":"9783642383489","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","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-38348-9_37","type":"book-chapter","created":{"date-parts":[[2013,5,8]],"date-time":"2013-05-08T20:46:38Z","timestamp":1368045998000},"page":"626-645","source":"Crossref","is-referenced-by-count":578,"title":["Quadratic Span Programs and Succinct NIZKs without PCPs"],"prefix":"10.1007","author":[{"given":"Rosario","family":"Gennaro","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Craig","family":"Gentry","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bryan","family":"Parno","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mariana","family":"Raykova","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"37_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-540-70936-7_7","volume-title":"Theory of Cryptography","author":"M. Abe","year":"2007","unstructured":"Abe, M., Fehr, S.: Perfect NIZK with adaptive soundness. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol.\u00a04392, pp. 118\u2013136. Springer, Heidelberg (2007)"},{"issue":"3","key":"37_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. J. ACM\u00a045(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"37_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. J. ACM\u00a045(1), 70\u2013122 (1998)","journal-title":"J. ACM"},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC, pp. 21\u201331 (1991)","DOI":"10.1145\/103418.103428"},{"key":"37_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/11693383_22","volume-title":"Selected Areas in Cryptography","author":"P.S.L.M. Barreto","year":"2006","unstructured":"Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol.\u00a03897, pp. 319\u2013331. Springer, Heidelberg (2006)"},{"key":"37_CR6","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":"37_CR7","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concrete-efficiency threshold of probabilistically-checkable proofs. In: STOC (to appear 2013)","DOI":"10.1145\/2488608.2488681"},{"key":"37_CR8","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: ITCS, pp. 326\u2013349 (2012)","DOI":"10.1145\/2090236.2090263"},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: STOC, pp. 103\u2013112 (1988)","DOI":"10.1145\/62212.62222"},{"issue":"6","key":"37_CR10","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1137\/0220068","volume":"20","author":"M. Blum","year":"1991","unstructured":"Blum, M., De Santis, A., Micali, S., Persiano, G.: Noninteractive zero-knowledge. SIAM Journal on Computing\u00a020(6), 1084\u20131118 (1991)","journal-title":"SIAM Journal on Computing"},{"key":"37_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/11426639_26","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"D. Boneh","year":"2005","unstructured":"Boneh, D., Boyen, X., Goh, E.-J.: Hierarchical identity based encryption with constant size ciphertext. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol.\u00a03494, pp. 440\u2013456. Springer, Heidelberg (2005)"},{"key":"37_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/3-540-44647-8_13","volume-title":"Advances in Cryptology - CRYPTO 2001","author":"D. Boneh","year":"2001","unstructured":"Boneh, D., Franklin, M.: Identity-based encryption from the weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol.\u00a02139, pp. 213\u2013229. Springer, Heidelberg (2001)"},{"key":"37_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/11535218_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"D. Boneh","year":"2005","unstructured":"Boneh, D., Gentry, C., Waters, B.: Collusion resistant broadcast encryption with short ciphertexts and private keys. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol.\u00a03621, pp. 258\u2013275. Springer, Heidelberg (2005)"},{"issue":"2","key":"37_CR14","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. J. Comput. Syst. Sci.\u00a037(2), 156\u2013189 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"37_CR15","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/1008731.1008734","volume":"51","author":"R. Canetti","year":"2004","unstructured":"Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM\u00a051(4), 557\u2013594 (2004)","journal-title":"J. ACM"},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: ITCS (2012)","DOI":"10.1145\/2090236.2090245"},{"key":"37_CR17","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":"37_CR18","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":"37_CR19","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. Damg\u00e5rd","year":"2012","unstructured":"Damg\u00e5rd, I., 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)"},{"issue":"2","key":"37_CR20","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM\u00a043(2), 268\u2013292 (1996)","journal-title":"J. ACM"},{"key":"37_CR21","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":"37_CR22","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":"37_CR23","doi-asserted-by":"crossref","unstructured":"Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: STOC, pp. 99\u2013108. ACM (2011)","DOI":"10.1145\/1993636.1993651"},{"key":"37_CR24","doi-asserted-by":"crossref","unstructured":"Gj\u00f8steen, K.: Subgroup membership problems and public key cryptosystems. PhD thesis, Norwegian University of Science and Technology (2004)","DOI":"10.1007\/978-3-540-30580-4_8"},{"key":"37_CR25","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: Interactive proofs for muggles. In: STOC, pp. 113\u2013122 (2008)","DOI":"10.1145\/1374376.1374396"},{"key":"37_CR26","unstructured":"Goldwasser, S., Lin, H., Rubinstein, A.: Delegation of computation without rejection problem from designated verifier CS-proofs. IACR Cryptology ePrint Archive, 2011: 456 (2011)"},{"key":"37_CR27","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":"3","key":"37_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2220357.2220358","volume":"59","author":"J. Groth","year":"2012","unstructured":"Groth, J., Ostrovsky, R., Sahai, A.: New techniques for noninteractive zero-knowledge. Journal of the ACM\u00a059(3), 11:1\u201311:35 (2012)","journal-title":"Journal of the ACM"},{"issue":"5","key":"37_CR29","doi-asserted-by":"publisher","first-page":"1193","DOI":"10.1137\/080725386","volume":"41","author":"J. Groth","year":"2012","unstructured":"Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. SIAM Journal on Computing\u00a041(5), 1193\u20131232 (2012)","journal-title":"SIAM Journal on Computing"},{"key":"37_CR30","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Efficient arguments without short PCPs. In: IEEE Conference on Computational Complexity (2007)","DOI":"10.1109\/CCC.2007.10"},{"key":"37_CR31","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: On span programs. In: Structure in Complexity Theory Conference, pp. 102\u2013111 (1993)","DOI":"10.1109\/SCT.1993.336536"},{"key":"37_CR32","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: STOC, pp. 723\u2013732 (1992)","DOI":"10.1145\/129712.129782"},{"key":"37_CR33","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":"37_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-28496-0_4","volume-title":"Selected Areas in Cryptography","author":"J. Loftus","year":"2012","unstructured":"Loftus, J., May, A., Smart, N.P., Vercauteren, F.: On CCA-secure somewhat homomorphic encryption. In: Miri, A., Vaudenay, S. (eds.) SAC 2011. LNCS, vol.\u00a07118, pp. 55\u201372. Springer, Heidelberg (2012)"},{"issue":"4","key":"37_CR35","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.J., Nisan, N.: Algebraic methods for interactive proof systems. J. ACM\u00a039(4), 859\u2013868 (1992)","journal-title":"J. ACM"},{"issue":"4","key":"37_CR36","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.\u00a030(4), 1253\u20131298 (2000); Extended abstract in FOCS (1994)","journal-title":"SIAM J. Comput."},{"key":"37_CR37","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":"37_CR38","doi-asserted-by":"crossref","unstructured":"Parno, B., Gentry, C., Howell, J., Raykova, M.: Pinocchio: Nearly practical verifiable computation. In: Proceedings of the IEEE Symposium on Security and Privacy (May 2013)","DOI":"10.1109\/SP.2013.47"},{"key":"37_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/978-3-642-28914-9_24","volume-title":"Theory of Cryptography","author":"B. Parno","year":"2012","unstructured":"Parno, B., Raykova, M., Vaikuntanathan, V.: How to delegate and verify in public: Verifiable computation from attribute-based encryption. In: Cramer, R. (ed.) TCC 2012. LNCS, vol.\u00a07194, pp. 422\u2013439. Springer, Heidelberg (2012)"},{"key":"37_CR40","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 USENIX Security (August 2012)"},{"issue":"4","key":"37_CR41","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 \u2013 EUROCRYPT 2013"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38348-9_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T05:17:44Z","timestamp":1745990264000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38348-9_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642383472","9783642383489"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38348-9_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}