{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:40:12Z","timestamp":1760136012248,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":58,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031159817"},{"type":"electronic","value":"9783031159824"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-15982-4_4","type":"book-chapter","created":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T04:40:54Z","timestamp":1665463254000},"page":"97-127","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Lower Bound on\u00a0SNARGs in\u00a0the\u00a0Random Oracle Model"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3167-3294","authenticated-orcid":false,"given":"Iftach","family":"Haitner","sequence":"first","affiliation":[]},{"given":"Daniel","family":"Nukrai","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8599-2472","authenticated-orcid":false,"given":"Eylon","family":"Yogev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,12]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: CCS 2017 (2017)","DOI":"10.1145\/3133956.3134104"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"B\u00fcnz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: S &P 2018 (2018)","DOI":"10.1109\/SP.2018.00020"},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1007\/978-3-319-96881-0_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"C Baum","year":"2018","unstructured":"Baum, C., Bootle, J., Cerulli, A., del Pino, R., Groth, J., Lyubashevsky, V.: Sub-linear lattice-based zero-knowledge arguments for arithmetic circuits. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 669\u2013699. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96881-0_23"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1007\/978-3-030-26954-8_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"E Ben-Sasson","year":"2019","unstructured":"Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable zero knowledge with no trusted setup. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 701\u2013732. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26954-8_23"},{"key":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-662-49896-5_12","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"J Bootle","year":"2016","unstructured":"Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C.: Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 327\u2013357. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49896-5_12"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., et al.: Zerocash: decentralized anonymous payments from bitcoin. In: SP 2014 (2014)","DOI":"10.1109\/SP.2014.36"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Chiesa, A., Ishai, Y., Ostrovsky, R., Paneth, O.: Succinct non-interactive arguments via linear interactive proofs. In: TCC 2013 (2013)","DOI":"10.1007\/978-3-642-36594-2_18"},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-3-030-17653-2_4","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"E Ben-Sasson","year":"2019","unstructured":"Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., Ward, N.P.: Aurora: transparent succinct arguments for R1CS. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 103\u2013128. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17653-2_4"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-662-53644-5_2","volume-title":"Theory of Cryptography","author":"E Ben-Sasson","year":"2016","unstructured":"Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 31\u201360. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53644-5_2"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1007\/978-3-030-84242-0_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"J Bootle","year":"2021","unstructured":"Bootle, J., Chiesa, A., Sotiraki, K.: Sumcheck arguments and their applications. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12825, pp. 742\u2013773. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84242-0_26"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/978-3-030-45721-1_24","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"B B\u00fcnz","year":"2020","unstructured":"B\u00fcnz, B., Fisch, B., Szepieniec, A.: Transparent SNARKs from DARK compilers. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 677\u2013706. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45721-1_24"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistically checkable proofs and applications to approximations. In: STOC 1993 (1993)","DOI":"10.1145\/167088.167174"},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-319-56617-7_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"D Boneh","year":"2017","unstructured":"Boneh, D., Ishai, Y., Sahai, A., Wu, D.J.: Lattice-based SNARGs and their application to more efficient obfuscation. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 247\u2013277. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56617-7_9"},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-319-78372-7_8","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"D Boneh","year":"2018","unstructured":"Boneh, D., Ishai, Y., Sahai, A., Wu, D.J.: Quasi-optimal SNARGs via linear multi-prover interactive proofs. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 222\u2013255. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78372-7_8"},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/978-3-030-56880-1_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2020","author":"J Bootle","year":"2020","unstructured":"Bootle, J., Lyubashevsky, V., Nguyen, N.K., Seiler, G.: A non-PCP approach to succinct quantum-safe zero-knowledge. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 441\u2013469. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-56880-1_16"},{"issue":"3","key":"4_CR16","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1007\/s00145-016-9233-9","volume":"30","author":"B Barak","year":"2017","unstructured":"Barak, B., Mahmoody-Ghidary, M.: Merkle\u2019s key agreement protocol is optimal: an O(n$$^{2}$$) attack on any key agreement from random oracles. J. Cryptol. 30(3), 699\u2013734 (2017)","journal-title":"J. Cryptol."},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Barak, B., Mahmoody-Ghidary, M.: Lower bounds on signatures from symmetric primitives (2007)","DOI":"10.1109\/FOCS.2007.4389536"},{"key":"4_CR18","unstructured":"Canetti, R., Chen, Y., Holmgren, J., Lombardi, A., Rothblum, G.N., Rothblum, R.D.: Fiat\u2013Shamir from simpler assumptions. Cryptology ePrint Archive, Report 2018\/1004"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-319-78381-9_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"S Coretti","year":"2018","unstructured":"Coretti, S., Dodis, Y., Guo, S., Steinberger, J.: Random oracles and non-uniformity. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 227\u2013258. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78381-9_9"},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-36362-7_5","volume-title":"Public-Key Cryptography \u2013 PKC 2013","author":"D Catalano","year":"2013","unstructured":"Catalano, D., Fiore, D.: Vector commitments and their applications. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 55\u201372. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36362-7_5"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1007\/978-3-030-45721-1_26","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"A Chiesa","year":"2020","unstructured":"Chiesa, A., Hu, Y., Maller, M., Mishra, P., Vesely, N., Ward, N.: Marlin: preprocessing zkSNARKs with universal and updatable SRS. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 738\u2013768. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45721-1_26"},{"key":"4_CR22","unstructured":"Chiesa, A., Ma, F., Spooner, N., Zhandry, M.: Post-quantum succinct arguments. In: IACR Cryptol. ePrint Arch (2021)"},{"key":"4_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1007\/978-3-030-45721-1_27","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"A Chiesa","year":"2020","unstructured":"Chiesa, A., Ojha, D., Spooner, N.: Fractal: post-quantum and transparent recursive proofs from holography. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 769\u2013793. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45721-1_27"},{"key":"4_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-030-64378-2_3","volume-title":"Theory of Cryptography","author":"A Chiesa","year":"2020","unstructured":"Chiesa, A., Yogev, E.: Barriers for succinct arguments in the random oracle model. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12551, pp. 47\u201376. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64378-2_3"},{"key":"4_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1007\/978-3-030-84242-0_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"A Chiesa","year":"2021","unstructured":"Chiesa, A., Yogev, E.: Subquadratic SNARGs in the random oracle model. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12825, pp. 711\u2013741. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84242-0_25"},{"key":"4_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/978-3-030-90459-3_14","volume-title":"Theory of Cryptography","author":"A Chiesa","year":"2021","unstructured":"Chiesa, A., Yogev, E.: Tight security bounds for Micali\u2019s SNARGs. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13042, pp. 401\u2013434. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-90459-3_14"},{"key":"4_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/978-3-319-56614-6_16","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"Y Dodis","year":"2017","unstructured":"Dodis, Y., Guo, S., Katz, J.: Fixing cracks in the concrete: random oracles with auxiliary input, revisited. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 473\u2013495. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56614-6_16"},{"key":"4_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/978-3-642-14165-2_37","volume-title":"Automata, Languages and Programming","author":"H Dell","year":"2010","unstructured":"Dell, H., Husfeldt, T., Wahl\u00e9n, M.: Exponential time complexity of the permanent and the Tutte polynomial. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 426\u2013437. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14165-2_37"},{"key":"4_CR29","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/s00037-001-8195-x","volume":"10","author":"J Edmonds","year":"2001","unstructured":"Edmonds, J., Impagliazzo, R., Rudich, S., Sgall, J.: Communication complexity towards lower bounds on circuit depth. Comput. Complex. 10, 210\u2013246 (2001)","journal-title":"Comput. Complex."},{"key":"4_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 \u2014 CRYPTO\u2019 86","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). https:\/\/doi.org\/10.1007\/3-540-47721-7_12"},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. In: SICOMP (2005)","DOI":"10.1137\/S0097539704443276"},{"key":"4_CR32","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). https:\/\/doi.org\/10.1007\/978-3-642-38348-9_37"},{"key":"4_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-030-90459-3_7","volume-title":"Theory of Cryptography","author":"S Guo","year":"2021","unstructured":"Guo, S., Li, Q., Liu, Q., Zhang, J.: Unifying presampling via concentration bounds. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13042, pp. 177\u2013208. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-90459-3_7"},{"key":"4_CR34","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Minelli, M., Nitulescu, A., Orr\u00f9, M.: Lattice-based zk-SNARKs from square span programs. In: CCS 2018 (2018)","DOI":"10.1145\/3243734.3243845"},{"key":"4_CR35","unstructured":"Ganesh, C., Nitulescu, A., Soria-Vazquez, E.: Rinocchio: SNARKs for ring arithmetic. In: IACR Cryptol. ePrint Arch (2021)"},{"key":"4_CR36","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). https:\/\/doi.org\/10.1007\/978-3-642-17373-8_19"},{"key":"4_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-662-49896-5_11","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"J Groth","year":"2016","unstructured":"Groth, J.: On the size of pairing-based non-interactive arguments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 305\u2013326. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49896-5_11"},{"key":"4_CR38","doi-asserted-by":"crossref","unstructured":"Grinberg, A., Shaltiel, R., Viola, E.: Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs (2018)","DOI":"10.1109\/FOCS.2018.00094"},{"key":"4_CR39","doi-asserted-by":"crossref","unstructured":"Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: STOC 2011 (2011)","DOI":"10.1145\/1993636.1993651"},{"key":"4_CR40","unstructured":"Haitner, I., Mazor, N., Oshman, R., Reingold, O., . Yehudayoff, A: On the communication complexity of key-agreement protocols (2018)"},{"key":"4_CR41","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations (1989)","DOI":"10.1145\/73007.73012"},{"key":"4_CR42","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Su, H., Wu, D.J.: Shorter and faster post-quantum designated-verifier zkSNARKs from lattices (2021)","DOI":"10.1145\/3460120.3484572"},{"key":"4_CR43","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: STOC 1992 (1992)","DOI":"10.1145\/129712.129782"},{"key":"4_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1007\/978-3-030-26948-7_19","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"RWF Lai","year":"2019","unstructured":"Lai, R.W.F., Malavolta, G.: Subvector commitments with application to succinct arguments. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 530\u2013560. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26948-7_19"},{"key":"4_CR45","unstructured":"Lee, J., Setty, S.T.V., Thaler, J., Wahby, R.S.: Linear-time zero-knowledge SNARKs for R1CS. In: IACR Cryptol. ePrint Arch (2021)"},{"key":"4_CR46","doi-asserted-by":"crossref","unstructured":"Maller, M., Bowe, S., Kohlweiss, M., Meiklejohn, S.: Sonic: zero-knowledge SNARKs from linear-size universal and updatable structured reference strings (2019)","DOI":"10.1145\/3319535.3339817"},{"key":"4_CR47","doi-asserted-by":"crossref","unstructured":"Merkle, R.C.: Secure communications over insecure channels. Commun. ACM 21(4), 294\u2013299 (1978)","DOI":"10.1145\/359460.359473"},{"key":"4_CR48","doi-asserted-by":"crossref","unstructured":"Micali, S.: Computationally sound proofs. SIAM J. Comput. (2000); Preliminary version appeared in FOCS 1994","DOI":"10.1137\/S0097539795284959"},{"key":"4_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-030-30530-7_11","volume-title":"Progress in Cryptology \u2013 LATINCRYPT 2019","author":"A Nitulescu","year":"2019","unstructured":"Nitulescu, A.: Lattice-based zero-knowledge SNARGs for arithmetic circuits. In: Schwabe, P., Th\u00e9riault, N. (eds.) LATINCRYPT 2019. LNCS, vol. 11774, pp. 217\u2013236. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-30530-7_11"},{"key":"4_CR50","doi-asserted-by":"crossref","unstructured":"Parno, B., Gentry, C., Howell, J., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: Oakland 2013 (2013)","DOI":"10.1109\/SP.2013.47"},{"issue":"3","key":"4_CR51","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 769\u2013803 (1998)","journal-title":"SIAM J. Comput."},{"key":"4_CR52","doi-asserted-by":"crossref","unstructured":"Setty, S.: Spartan: efficient and general-purpose zkSNARKs without trusted setup. Cryptology ePrint Archive, Report 2019\/550","DOI":"10.1007\/978-3-030-56877-1_25"},{"key":"4_CR53","unstructured":"libstark. libstark: a C++ library for zkSTARK systems (2018). https:\/\/github.com\/elibensasson\/libSTARK"},{"key":"4_CR54","doi-asserted-by":"publisher","first-page":"3122","DOI":"10.1137\/080735096","volume":"39","author":"R Shaltiel","year":"2010","unstructured":"Shaltiel, R., Viola, E.: Hardness amplification proofs require majority. SIAM J. Comput. 39, 3122\u20133154 (2010)","journal-title":"SIAM J. Comput."},{"key":"4_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-74143-5_12","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"D Unruh","year":"2007","unstructured":"Unruh, D.: Random oracles and auxiliary input. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 205\u2013223. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74143-5_12"},{"key":"4_CR56","doi-asserted-by":"crossref","unstructured":"Wahby, R.S., Tzialla, I., Shelat, A., Thaler, J., Walfish, M.: Doublyefficient zkSNARKs without trusted setup (2018)","DOI":"10.1109\/SP.2018.00060"},{"key":"4_CR57","unstructured":"Electric Coin Company: Zcash Cryptocurrency. https:\/\/z.cash\/"},{"key":"4_CR58","unstructured":"Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: A zero-knowledge version of vSQL. Cryptology ePrint Archive, Report 2017\/1146"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2022"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-15982-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:05:52Z","timestamp":1760133952000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-15982-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031159817","9783031159824"],"references-count":58,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-15982-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"12 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"42","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}