{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T11:46:12Z","timestamp":1777376772859,"version":"3.51.4"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031587504","type":"print"},{"value":"9783031587511","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-58751-1_9","type":"book-chapter","created":{"date-parts":[[2024,4,28]],"date-time":"2024-04-28T03:01:57Z","timestamp":1714273317000},"page":"241-270","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Strong Batching for\u00a0Non-interactive Statistical Zero-Knowledge"],"prefix":"10.1007","author":[{"given":"Changrui","family":"Mu","sequence":"first","affiliation":[]},{"given":"Shafik","family":"Nassar","sequence":"additional","affiliation":[]},{"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[]},{"given":"Prashant Nalini","family":"Vasudevan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"key":"9_CR1","unstructured":"Bitansky, N., Kamath, C., Paneth, O., Rothblum, R., Vasudevan, P.N.: Batch proofs are statistically hiding. Electron. Colloquium Comput. Complex. TR23-077 (2023)"},{"key":"9_CR2","doi-asserted-by":"publisher","unstructured":"Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pp. 103\u2013112. ACM (1988). https:\/\/doi.org\/10.1145\/62212.62222","DOI":"10.1145\/62212.62222"},{"key":"9_CR3","doi-asserted-by":"publisher","unstructured":"Blum, M., Santis, A., Micali, S., Persiano, G.: Noninteractive zero-knowledge. SIAM J. Comput. 20(6), 1084\u20131118 (1991). https:\/\/doi.org\/10.1137\/0220068","DOI":"10.1137\/0220068"},{"key":"9_CR4","doi-asserted-by":"publisher","unstructured":"Brakerski, Z., Brodsky, M.F., Kalai, Y.T., Lombardi, A., Paneth, O.: SNARGs for monotone policy batch NP. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference. LNCS, vol. 14082, pp. 252\u2013283. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-38545-2_9","DOI":"10.1007\/978-3-031-38545-2_9"},{"key":"9_CR5","doi-asserted-by":"publisher","unstructured":"Brakerski, Z., Holmgren, J., Kalai, Y.T.: Non-interactive delegation and batch NP verification from standard computational assumptions. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 474\u2013482. ACM (2017). https:\/\/doi.org\/10.1145\/3055399.3055497","DOI":"10.1145\/3055399.3055497"},{"key":"9_CR6","doi-asserted-by":"publisher","unstructured":"Choudhuri, A.R., Garg, S., Jain, A., Jin, Z., Zhang, J.: Correlation intractability and SNARGs from sub-exponential DDH. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference. LNCS, vol. 14084, pp. 635\u2013668. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-38551-3_20","DOI":"10.1007\/978-3-031-38551-3_20"},{"key":"9_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-030-84259-8_14","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"AR Choudhuri","year":"2021","unstructured":"Choudhuri, A.R., Jain, A., Jin, Z.: Non-interactive batch arguments for NP from standard assumptions. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 394\u2013423. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84259-8_14"},{"key":"9_CR8","doi-asserted-by":"publisher","unstructured":"Choudhuri, A.R., Jain, A., Jin, Z.: SNARGs for P from LWE. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pp. 68\u201379. IEEE (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00016","DOI":"10.1109\/FOCS52979.2021.00016"},{"key":"9_CR9","doi-asserted-by":"publisher","unstructured":"Devadas, L., Goyal, R., Kalai, Y., Vaikuntanathan, V.: Rate-1 non-interactive arguments for batch-NP and applications. In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pp. 1057\u20131068. IEEE (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00103","DOI":"10.1109\/FOCS54457.2022.00103"},{"key":"9_CR10","unstructured":"Dvir, Z., Gutfreund, D., Rothblum, G.N., Vadhan, S.P.: On approximating the entropy of polynomial mappings. In: Innovations in Computer Science - ICS 2011, pp. 460\u2013475. Tsinghua University Press (2011)"},{"key":"9_CR11","doi-asserted-by":"publisher","unstructured":"Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC 1990, pp. 416\u2013426. Association for Computing Machinery, New York, NY, USA (1990). https:\/\/doi.org\/10.1145\/100216.100272","DOI":"10.1145\/100216.100272"},{"key":"9_CR12","doi-asserted-by":"publisher","unstructured":"Goel, A., Hall-Andersen, M., Kaptchuk, G., Spooner, N.: Speed-stacking: fast sublinear zero-knowledge proofs for disjunctions. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques. LNCS, vol. 14005, pp. 347\u2013378. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30617-4_12","DOI":"10.1007\/978-3-031-30617-4_12"},{"issue":"4","key":"9_CR13","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). https:\/\/doi.org\/10.1016\/S0020-0190(98)00116-1","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9_CR14","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1137\/S0097539791220688","volume":"25","author":"O Goldreich","year":"1996","unstructured":"Goldreich, O., Krawczyk, H.: On the composition of zero-knowledge proof systems. SIAM J. Comput. 25(1), 169\u2013192 (1996). https:\/\/doi.org\/10.1137\/S0097539791220688","journal-title":"SIAM J. Comput."},{"key":"9_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/3-540-48405-1_30","volume-title":"Advances in Cryptology \u2014 CRYPTO 1999","author":"O Goldreich","year":"1999","unstructured":"Goldreich, O., Sahai, A., Vadhan, S.: Can statistical zero knowledge be made non-interactive? or On the relationship of SZK and NISZK. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 467\u2013484. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48405-1_30"},{"key":"9_CR16","doi-asserted-by":"publisher","unstructured":"Goldreich, O., Sahai, A., Vadhan, S.P.: Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In: Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, pp. 399\u2013408. ACM (1998). https:\/\/doi.org\/10.1145\/276698.276852","DOI":"10.1145\/276698.276852"},{"key":"9_CR17","doi-asserted-by":"publisher","unstructured":"Goldreich, O., Vadhan, S., Wigderson, A.: On interactive proofs with a Laconic prover. Comput. Complex. 11(1\/2), 1\u201353 (2002). https:\/\/doi.org\/10.1007\/s00037-002-0169-0","DOI":"10.1007\/s00037-002-0169-0"},{"issue":"1","key":"9_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 proof systems. SIAM J. Comput. 18(1), 186\u2013208 (1989). https:\/\/doi.org\/10.1137\/0218012","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9_CR19","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364\u20131396 (1999). https:\/\/doi.org\/10.1137\/S0097539793244708","journal-title":"SIAM J. Comput."},{"key":"9_CR20","doi-asserted-by":"publisher","unstructured":"Kalai, Y., Lombardi, A., Vaikuntanathan, V., Wichs, D.: Boosting batch arguments and RAM delegation. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pp. 1545\u20131552. ACM (2023). https:\/\/doi.org\/10.1145\/3564246.3585200","DOI":"10.1145\/3564246.3585200"},{"key":"9_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/978-3-030-90459-3_12","volume-title":"Theory of Cryptography","author":"YT Kalai","year":"2021","unstructured":"Kalai, Y.T., Vaikuntanathan, V., Zhang, R.Y.: Somewhere statistical soundness, post-quantum security, and SNARGs. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13042, pp. 330\u2013368. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-90459-3_12"},{"key":"9_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-030-64378-2_6","volume-title":"Theory of Cryptography","author":"I Kaslasi","year":"2020","unstructured":"Kaslasi, I., Rothblum, G.N., Rothblum, R.D., Sealfon, A., Vasudevan, P.N.: Batch verification for statistical zero knowledge proofs. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12551, pp. 139\u2013167. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64378-2_6"},{"key":"9_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-030-77883-5_8","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2021","author":"I Kaslasi","year":"2021","unstructured":"Kaslasi, I., Rothblum, R.D., Vasudevanr, P.N.: Public-coin statistical zero-knowledge batch verification against malicious verifiers. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12698, pp. 219\u2013246. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-77883-5_8"},{"issue":"4","key":"9_CR24","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 39(4), 859\u2013868 (1992). https:\/\/doi.org\/10.1145\/146585.146605","journal-title":"J. ACM"},{"key":"9_CR25","doi-asserted-by":"crossref","unstructured":"Mu, C., Nassar, S., Rothblum, R.D., Vasudevan, P.N.: Strong batching for non-interactive statistical zero-knowledge. IACR Cryptol. ePrint Arch. (2024). https:\/\/eprint.iacr.org\/2024\/229","DOI":"10.1007\/978-3-031-58751-1_9"},{"key":"9_CR26","doi-asserted-by":"crossref","unstructured":"Nassar, S., Waters, B., Wu, D.J.: Monotone policy BARGs from BARGs and additively homomorphic encryption. IACR Cryptol. ePrint Arch. (2023). https:\/\/eprint.iacr.org\/2023\/1967","DOI":"10.1007\/978-3-031-78017-2_14"},{"key":"9_CR27","doi-asserted-by":"publisher","unstructured":"Nguyen, M., Vadhan, S.P.: Zero knowledge with efficient provers. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 287\u2013295. ACM (2006). https:\/\/doi.org\/10.1145\/1132516.1132559","DOI":"10.1145\/1132516.1132559"},{"issue":"4","key":"9_CR28","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"N Nisan","year":"1992","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica 12(4), 449\u2013461 (1992). https:\/\/doi.org\/10.1007\/BF01305237","journal-title":"Combinatorica"},{"key":"9_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/978-3-540-78524-8_27","volume-title":"Theory of Cryptography","author":"SJ Ong","year":"2008","unstructured":"Ong, S.J., Vadhan, S.: An equivalence between zero knowledge and commitments. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 482\u2013500. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78524-8_27"},{"key":"9_CR30","doi-asserted-by":"publisher","unstructured":"Paneth, O., Pass, R.: Incrementally verifiable computation via rate-1 batch arguments. In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pp. 1045\u20131056. IEEE (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00102","DOI":"10.1109\/FOCS54457.2022.00102"},{"key":"9_CR31","doi-asserted-by":"publisher","unstructured":"Reingold, O., Rothblum, G.N., Rothblum, R.D.: Efficient batch verification for UP. In: 33rd Computational Complexity Conference, CCC 2018. LIPIcs, vol.\u00a0102, pp. 22:1\u201322:23. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2018.22","DOI":"10.4230\/LIPIcs.CCC.2018.22"},{"key":"9_CR32","doi-asserted-by":"publisher","unstructured":"Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. SIAM J. Comput. 50(3) (2021). https:\/\/doi.org\/10.1137\/16M1096773","DOI":"10.1137\/16M1096773"},{"key":"9_CR33","doi-asserted-by":"publisher","unstructured":"Renner, R., Wolf, S.: Smooth Renyi entropy and applications. In: International Symposium on Information Theory, ISIT 2004, Proceedings, pp. 233\u2013 (2004). https:\/\/doi.org\/10.1109\/ISIT.2004.1365269","DOI":"10.1109\/ISIT.2004.1365269"},{"key":"9_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-030-64378-2_5","volume-title":"Theory of Cryptography","author":"GN Rothblum","year":"2020","unstructured":"Rothblum, G.N., Rothblum, R.D.: Batch verification and proofs of proximity with polylog overhead. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12551, pp. 108\u2013138. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64378-2_5"},{"key":"9_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1007\/BFb0055102","volume-title":"Automata, Languages and Programming","author":"A De Santis","year":"1998","unstructured":"De Santis, A., Di Crescenzo, G., Persiano, G., Yung, M.: Image density is complete for non-interactive-SZK. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 784\u2013795. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0055102"},{"issue":"4","key":"9_CR36","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 39(4), 869\u2013877 (1992). https:\/\/doi.org\/10.1145\/146585.146609","journal-title":"J. ACM"},{"key":"9_CR37","doi-asserted-by":"publisher","unstructured":"Vadhan, S.P.: Pseudorandomness. Found. Trends\u00ae Theor. Comput. Sci. 7(1\u20133), 1\u2013336 (2012). https:\/\/doi.org\/10.1561\/0400000010","DOI":"10.1561\/0400000010"},{"key":"9_CR38","unstructured":"Vadhan, S.P.: A study of statistical zero-knowledge proofs. Ph.D. thesis, Massachusetts Institute of Technology (1999)"},{"key":"9_CR39","doi-asserted-by":"publisher","unstructured":"Waters, B., Wu, D.J.: Batch arguments for NP and more from standard bilinear group assumptions. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference. LNCS, vol. 13508, pp. 433\u2013463. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-15979-4_15","DOI":"10.1007\/978-3-031-15979-4_15"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2024"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-58751-1_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T00:05:01Z","timestamp":1777334701000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-58751-1_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031587504","9783031587511"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-58751-1_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"29 April 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"EUROCRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Zurich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Switzerland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 May 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 May 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"43","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eurocrypt2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt.iacr.org\/2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}