{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T10:14:39Z","timestamp":1772878479323,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662498958","type":"print"},{"value":"9783662498965","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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-49896-5_12","type":"book-chapter","created":{"date-parts":[[2016,4,27]],"date-time":"2016-04-27T04:45:32Z","timestamp":1461732332000},"page":"327-357","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":255,"title":["Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting"],"prefix":"10.1007","author":[{"given":"Jonathan","family":"Bootle","sequence":"first","affiliation":[]},{"given":"Andrea","family":"Cerulli","sequence":"additional","affiliation":[]},{"given":"Pyrros","family":"Chaidos","sequence":"additional","affiliation":[]},{"given":"Jens","family":"Groth","sequence":"additional","affiliation":[]},{"given":"Christophe","family":"Petit","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,4,28]]},"reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/978-3-642-29011-4_17","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"S Bayer","year":"2012","unstructured":"Bayer, S., Groth, J.: Efficient zero-knowledge argument for correctness of a shuffle. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 263\u2013280. Springer, Heidelberg (2012)"},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1007\/978-3-642-38348-9_38","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"S Bayer","year":"2013","unstructured":"Bayer, S., Groth, J.: Zero-knowledge argument for polynomial evaluation with application to blacklists. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 646\u2013663. Springer, Heidelberg (2013)"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security \u2013 CCS 1993, pp. 62\u201373 (1993)","DOI":"10.1145\/168588.168596"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-40084-1_6","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"E Ben-Sasson","year":"2013","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: verifying program executions succinctly and in zero knowledge. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 90\u2013108. Springer, Heidelberg (2013)"},{"key":"12_CR5","unstructured":"Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Succinct non-interactive zero knowledge for a von Neumann architecture. In: USENIX Security Symposium 2014, pp. 781\u2013796 (2014)"},{"key":"12_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: Innovations in Theoretical Computer Science \u2013 ITCS 2012, pp. 326\u2013349 (2012)","DOI":"10.1145\/2090236.2090263"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKS and proof-carrying data. In: Symposium on Theory of Computing Conference \u2013 TCC 2013, pp. 111\u2013120 (2013)","DOI":"10.1145\/2488608.2488623"},{"issue":"2","key":"12_CR8","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. 37(2), 156\u2013189 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"12_CR9","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0097-3165(89)90020-4","volume":"50","author":"DG Cantor","year":"1989","unstructured":"Cantor, D.G.: On arithmetical algorithms over finite fields. J. Comb. Theor. Ser. A 50(2), 285\u2013300 (1989)","journal-title":"J. Comb. Theor. Ser. A"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/BFb0055745","volume-title":"Advances in Cryptology - CRYPTO \u201998","author":"R Cramer","year":"1998","unstructured":"Cramer, R., Damg\u00e5rd, I.B.: Zero-knowledge proofs for finite field arithmetic or: can zero-knowledge be for free? In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 424\u2013441. Springer, Heidelberg (1998)"},{"key":"12_CR11","unstructured":"Danezis, G.: Petlib: a Python library that implements a number of privacy enhancing technologies (PETs) (2015). \n                    https:\/\/github.com\/gdanezis\/petlib"},{"issue":"2","key":"12_CR12","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/s00145-005-0307-3","volume":"19","author":"JA Garay","year":"2006","unstructured":"Garay, J.A., MacKenzie, P., Yang, K.: Strengthening zero-knowledge protocols using signatures. J. Cryptology 19(2), 169\u2013209 (2006)","journal-title":"J. Cryptology"},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1007\/978-3-642-38348-9_37","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"R Gennaro","year":"2013","unstructured":"Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626\u2013645. Springer, Heidelberg (2013)"},{"issue":"4","key":"12_CR14","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1007\/s00145-014-9184-y","volume":"28","author":"C Gentry","year":"2015","unstructured":"Gentry, C., Groth, J., Ishai, Y., Peikert, C., Sahai, A., Smith, A.: Using fully homomorphic hybrid encryption to minimize non-interative zero-knowledge proofs. J. Cryptology 28(4), 820\u2013843 (2015)","journal-title":"J. Cryptology"},{"issue":"4","key":"12_CR15","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. Inf. Process. Lett. 67(4), 205\u2013214 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"12_CR16","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O Goldreich","year":"1991","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691\u2013729 (1991)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"12_CR17","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.P., Wigderson, A.: On interactive proofs with a laconic prover. Comput. Complex. 11(1\u20132), 1\u201353 (2002)","journal-title":"Comput. Complex."},{"issue":"1","key":"12_CR18","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 proofs. SIAM J. Comput. 18(1), 186\u2013208 (1989)","journal-title":"SIAM J. Comput."},{"key":"12_CR19","unstructured":"Groth, J.: Honest verifier zero-knowledge arguments applied. Ph.D. thesis, University of Aarhus (2004)"},{"key":"12_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/978-3-642-25385-0_23","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2011","author":"J Groth","year":"2011","unstructured":"Groth, J.: Efficient zero-knowledge arguments from two-tiered homomorphic commitments. In: Wang, X., Lee, D.H. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 431\u2013448. Springer, Heidelberg (2011)"},{"key":"12_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-642-03356-8_12","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"J Groth","year":"2009","unstructured":"Groth, J.: Linear algebra with sub-linear zero-knowledge arguments. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 192\u2013208. Springer, Heidelberg (2009)"},{"key":"12_CR22","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. 6477, pp. 321\u2013340. Springer, Heidelberg (2010)"},{"key":"12_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/978-3-540-78967-3_22","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"J Groth","year":"2008","unstructured":"Groth, J., Ishai, Y.: Sub-linear zero-knowledge argument for correctness of a shuffle. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 379\u2013396. Springer, Heidelberg (2008)"},{"key":"12_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/978-3-662-46803-6_9","volume-title":"Advances in Cryptology - EUROCRYPT 2015","author":"J Groth","year":"2015","unstructured":"Groth, J., Kohlweiss, M.: One-out-of-many proofs: or how to leak a secret and spend a coin. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 253\u2013280. Springer, Heidelberg (2015)"},{"key":"12_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/3-540-45961-8_11","volume-title":"Advances in Cryptology - EUROCRYPT \u201988","author":"LC Guillou","year":"1988","unstructured":"Guillou, L.C., Quisquater, J.-J.: A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. In: G\u00fcnther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 123\u2013128. Springer, Heidelberg (1988)"},{"key":"12_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-17373-8_11","volume-title":"Advances in Cryptology - ASIACRYPT 2010","author":"A Kate","year":"2010","unstructured":"Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 177\u2013194. Springer, Heidelberg (2010)"},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Symposium on Theory of Computing Conference \u2013 TCC 1992, pp. 723\u2013732 (1992)","DOI":"10.1145\/129712.129782"},{"key":"12_CR28","unstructured":"Lim, C.H.: Efficient multi-exponentiation and application to batch verification of digital signatures, manuscript (2000). \n                    http:\/\/dasan.sejong.ac.kr\/ chlim\/pub\/multi_exp.ps"},{"issue":"3","key":"12_CR29","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s00145-002-0143-7","volume":"16","author":"Y Lindell","year":"2003","unstructured":"Lindell, Y.: Parallel coin-tossing and constant-round secure two-party computation. J. Cryptology 16(3), 143\u2013184 (2003)","journal-title":"J. Cryptology"},{"key":"12_CR30","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. 7194, pp. 169\u2013189. Springer, Heidelberg (2012)"},{"key":"12_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/3-540-45537-X_13","volume-title":"Selected Areas in Cryptography","author":"B M\u00f6ller","year":"2001","unstructured":"M\u00f6ller, B.: Algorithms for multi-exponentiation. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, pp. 165\u2013180. Springer, Heidelberg (2001)"},{"key":"12_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-540-85855-3_4","volume-title":"Security and Cryptography for Networks","author":"B M\u00f6ller","year":"2008","unstructured":"M\u00f6ller, B., Rupp, A.: Faster multi-exponentiation through caching: accelerating (EC) DSA signature verification. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 39\u201356. Springer, Heidelberg (2008)"},{"key":"12_CR33","unstructured":"Oliphant, T.E.: A guide to NumPy, vol. 1. Trelgol Publishing, USA (2006)"},{"key":"12_CR34","doi-asserted-by":"crossref","unstructured":"Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: IEEE Symposium on Security and Privacy, pp. 238\u2013252 (2013)","DOI":"10.1109\/SP.2013.47"},{"issue":"3","key":"12_CR35","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00196725","volume":"4","author":"CP Schnorr","year":"1991","unstructured":"Schnorr, C.P.: Efficient signature generation by smart cards. J. Cryptology 4(3), 161\u2013174 (1991)","journal-title":"J. Cryptology"},{"key":"12_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-642-19379-8_24","volume-title":"Public Key Cryptography \u2013 PKC 2011","author":"JH Seo","year":"2011","unstructured":"Seo, J.H.: Round-efficient sub-linear zero-knowledge arguments for linear algebra. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 387\u2013402. Springer, Heidelberg (2011)"},{"key":"12_CR37","unstructured":"Shoup, V.: NTL: a library for doing number theory (2001). \n                    http:\/\/www.shoup.net\/ntl\/"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2016"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49896-5_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,28]],"date-time":"2020-04-28T00:04:07Z","timestamp":1588032247000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49896-5_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662498958","9783662498965"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49896-5_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"28 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}