{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T00:38:39Z","timestamp":1777250319980,"version":"3.51.4"},"publisher-location":"Cham","reference-count":74,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031587368","type":"print"},{"value":"9783031587375","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-58737-5_5","type":"book-chapter","created":{"date-parts":[[2024,4,27]],"date-time":"2024-04-27T07:01:52Z","timestamp":1714201312000},"page":"112-141","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Public-Coin, Complexity-Preserving, Succinct Arguments of\u00a0Knowledge for\u00a0NP from\u00a0Collision-Resistance"],"prefix":"10.1007","author":[{"given":"Cody","family":"Freitag","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Omer","family":"Paneth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,28]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: CCS, pp. 2087\u20132104. ACM (2017)","DOI":"10.1145\/3133956.3134104"},{"key":"5_CR2","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, pp. 21\u201331 (1991)","DOI":"10.1145\/103418.103428"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Badrinarayanan, S., Kalai, Y.T., Khurana, D., Sahai, A., Wichs, D.: Succinct delegation for low-space non-deterministic computation. In: STOC, pp. 709\u2013721. ACM (2018)","DOI":"10.1145\/3188745.3188924"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/978-3-031-22318-1_15","volume-title":"Theory of Cryptography","author":"L Bangalore","year":"2022","unstructured":"Bangalore, L., Bhadauria, R., Hazay, C., Venkitasubramaniam, M.: On black-box constructions of time and space efficient sublinear arguments from symmetric-key primitives. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC 2022. LNCS, vol. 13747, pp. 417\u2013446. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-22318-1_15"},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"Barak, B.: How to go beyond the black-box simulation barrier. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS, pp. 106\u2013115 (2001)","DOI":"10.1109\/SFCS.2001.959885"},{"issue":"5","key":"5_CR6","doi-asserted-by":"publisher","first-page":"1661","DOI":"10.1137\/070709244","volume":"38","author":"B Barak","year":"2008","unstructured":"Barak, B., Goldreich, O.: Universal arguments and their applications. SIAM J. Comput. 38(5), 1661\u20131694 (2008)","journal-title":"SIAM J. Comput."},{"key":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/3-540-48071-4_28","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 92","author":"M Bellare","year":"1993","unstructured":"Bellare, M., Goldreich, O.: On defining proofs of knowledge. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 390\u2013420. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-48071-4_28"},{"key":"5_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/0-387-34799-2_4","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 88","author":"M Ben-Or","year":"1990","unstructured":"Ben-Or, M., et al.: Everything provable is provable in zero-knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 37\u201356. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34799-2_4"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: how to remove intractability assumptions. In: STOC, pp. 113\u2013131. ACM (1988)","DOI":"10.1145\/62212.62223"},{"key":"5_CR10","doi-asserted-by":"publisher","unstructured":"Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast Reed-Solomon interactive oracle proofs of proximity. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, 9\u201313 July 2018. LIPIcs, vol.\u00a0107, pp. 14:1\u201314:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.14","DOI":"10.4230\/LIPIcs.ICALP.2018.14"},{"key":"5_CR11","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":"5_CR12","unstructured":"Ben-Sasson, E., Chiesa, A., Gabizon, A., Riabzev, M., Spooner, N.: Interactive oracle proofs with constant rate and query complexity. In: ICALP. LIPIcs, vol.\u00a080, pp. 40:1\u201340:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"key":"5_CR13","doi-asserted-by":"publisher","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concrete efficiency of probabilistically-checkable proofs. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) Symposium on Theory of Computing Conference, STOC 2013, Palo Alto, CA, USA, 1\u20134 June 2013, pp. 585\u2013594. ACM (2013). https:\/\/doi.org\/10.1145\/2488608.2488681","DOI":"10.1145\/2488608.2488681"},{"key":"5_CR14","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":"5_CR15","doi-asserted-by":"publisher","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Short PCPs verifiable in polylogarithmic time. In: 20th Annual IEEE Conference on Computational Complexity (CCC 2005), San Jose, CA, USA, 11\u201315 June 2005, pp. 120\u2013134. IEEE Computer Society (2005). https:\/\/doi.org\/10.1109\/CCC.2005.27","DOI":"10.1109\/CCC.2005.27"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Kaplan, Y., Kopparty, S., Meir, O., Stichtenoth, H.: Constant rate PCPs for circuit-sat with sublinear query complexity. J. ACM 63(4), 32:1\u201332:57 (2016)","DOI":"10.1145\/2901294"},{"issue":"2","key":"5_CR17","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/050646445","volume":"38","author":"E Ben-Sasson","year":"2008","unstructured":"Ben-Sasson, E., Sudan, M.: Short PCPs with polylog query complexity. SIAM J. Comput. 38(2), 551\u2013607 (2008)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"5_CR18","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1007\/s00145-016-9241-9","volume":"30","author":"N Bitansky","year":"2017","unstructured":"Bitansky, N., et al.: The hunting of the SNARK. J. Cryptol. 30(4), 989\u20131066 (2017)","journal-title":"J. Cryptol."},{"key":"5_CR19","doi-asserted-by":"publisher","unstructured":"Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKS and proof-carrying data. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) Symposium on Theory of Computing Conference, STOC 2013, Palo Alto, CA, USA, 1\u20134 June 2013, pp. 111\u2013120. ACM (2013). https:\/\/doi.org\/10.1145\/2488608.2488623","DOI":"10.1145\/2488608.2488623"},{"issue":"5","key":"5_CR20","doi-asserted-by":"publisher","first-page":"1910","DOI":"10.1137\/140975048","volume":"45","author":"N Bitansky","year":"2016","unstructured":"Bitansky, N., Canetti, R., Paneth, O., Rosen, A.: On the existence of extractable one-way functions. SIAM J. Comput. 45(5), 1910\u20131952 (2016)","journal-title":"SIAM J. Comput."},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/978-3-642-32009-5_16","volume-title":"Advances in Cryptology \u2013 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., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 255\u2013272. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32009-5_16"},{"key":"5_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-36594-2_18","volume-title":"Theory of Cryptography","author":"N Bitansky","year":"2013","unstructured":"Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., Ostrovsky, R.: Succinct non-interactive arguments via linear interactive proofs. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 315\u2013333. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36594-2_18"},{"key":"5_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/978-3-030-64378-2_7","volume-title":"Theory of Cryptography","author":"AR Block","year":"2020","unstructured":"Block, A.R., Holmgren, J., Rosen, A., Rothblum, R.D., Soni, P.: Public-coin zero-knowledge arguments with (almost) minimal time and space overheads. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12551, pp. 168\u2013197. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64378-2_7"},{"key":"5_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/978-3-030-84259-8_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"AR Block","year":"2021","unstructured":"Block, A.R., Holmgren, J., Rosen, A., Rothblum, R.D., Soni, P.: Time- and space-efficient arguments from groups of unknown order. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 123\u2013152. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84259-8_5"},{"key":"5_CR25","unstructured":"Blumberg, A.J., Thaler, J., Vu, V., Walfish, M.: Verifiable computation using multiple provers. IACR Cryptology ePrint Archive, p.\u00a0846 (2014)"},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-030-26954-8_3","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"D Boneh","year":"2019","unstructured":"Boneh, D., Boyle, E., Corrigan-Gibbs, H., Gilboa, N., Ishai, Y.: Zero-knowledge proofs on secret-shared data via fully linear PCPs. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 67\u201397. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26954-8_3"},{"key":"5_CR27","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":"5_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/978-3-662-48800-3_10","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2015","author":"E Boyle","year":"2015","unstructured":"Boyle, E., Pass, R.: Limits of extractability assumptions with distributional auxiliary input. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 236\u2013261. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48800-3_10"},{"key":"5_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/978-3-031-38545-2_9","volume-title":"Advances in Cryptology","author":"Z Brakerski","year":"2023","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.) CRYPTO 2023. LNCS, vol. 14082, pp. 252\u2013283. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-38545-2_9"},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Holmgren, J., Kalai, Y.T.: Non-interactive delegation and batch NP verification from standard computational assumptions. In: STOC, pp. 474\u2013482. ACM (2017)","DOI":"10.1145\/3055399.3055497"},{"key":"5_CR31","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: IEEE Symposium on Security and Privacy, pp. 315\u2013334. IEEE Computer Society (2018)","DOI":"10.1109\/SP.2018.00020"},{"key":"5_CR32","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":"5_CR33","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":"5_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/978-3-031-38551-3_20","volume-title":"Advances in Cryptology","author":"AR Choudhuri","year":"2023","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.) CRYPTO 2023. LNCS, vol. 14084, pp. 635\u2013668. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-38551-3_20"},{"key":"5_CR35","unstructured":"Choudhuri, A.R., Jain, A., Jin, Z.: SNARGs for P from LWE. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 68\u201379 (2021)"},{"key":"5_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/0-387-34805-0_39","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 89 Proceedings","author":"IB Damg\u00e5rd","year":"1990","unstructured":"Damg\u00e5rd, I.B.: A design principle for hash functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416\u2013427. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34805-0_39"},{"key":"5_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/3-540-36178-2_8","volume-title":"Advances in Cryptology \u2014 ASIACRYPT 2002","author":"I Damg\u00e5rd","year":"2002","unstructured":"Damg\u00e5rd, I., Fujisaki, E.: A statistically-hiding integer commitment scheme based on groups with hidden order. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 125\u2013142. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-36178-2_8"},{"key":"5_CR38","doi-asserted-by":"crossref","unstructured":"Devadas, L., Goyal, R., Kalai, Y., Vaikuntanathan, V.: Rate-1 non-interactive arguments for batch-NP and applications. In: FOCS, pp. 1057\u20131068. IEEE (2022)","DOI":"10.1109\/FOCS54457.2022.00103"},{"issue":"3","key":"5_CR39","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I Dinur","year":"2007","unstructured":"Dinur, I.: The PCP theorem by gap amplification. J. ACM 54(3), 12 (2007)","journal-title":"J. ACM"},{"key":"5_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1007\/978-3-030-45721-1_25","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"N Ephraim","year":"2020","unstructured":"Ephraim, N., Freitag, C., Komargodski, I., Pass, R.: SPARKs: succinct parallelizable arguments of knowledge. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 707\u2013737. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45721-1_25"},{"issue":"2","key":"5_CR41","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 43(2), 268\u2013292 (1996)","journal-title":"J. ACM"},{"key":"5_CR42","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":"5_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/978-3-031-22365-5_22","volume-title":"Theory of Cryptography","author":"C Freitag","year":"2022","unstructured":"Freitag, C., Pass, R., Sirkin, N.: Parallelizable delegation from LWE. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC 2022. LNCS, vol. 13748, pp. 623\u2013652. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-22365-5_22"},{"key":"5_CR44","unstructured":"Gabizon, A., Williamson, Z.J., Ciobotaru, O.: PLONK: permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge. IACR Cryptology ePrint Archive, p.\u00a0953 (2019)"},{"key":"5_CR45","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":"5_CR46","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":"5_CR47","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Krawczyk, H.: On the composition of zero-knowledge proof systems. In: International Colloquium on Automata, Languages, and Programming, ICALP, pp. 268\u2013282 (1990)","DOI":"10.1007\/BFb0032038"},{"key":"5_CR48","doi-asserted-by":"crossref","unstructured":"Holmgren, J., Rothblum, R.: Delegating computations with (almost) minimal time and space overhead. In: FOCS, pp. 124\u2013135. IEEE Computer Society (2018)","DOI":"10.1109\/FOCS.2018.00021"},{"key":"5_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/978-3-031-07085-3_18","volume-title":"Advances in Cryptology","author":"J Hulett","year":"2022","unstructured":"Hulett, J., Jawale, R., Khurana, D., Srinivasan, A.: SNARGs for P from Sub-exponential DDH and QR. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13276, pp. 520\u2013549. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-07085-3_18"},{"key":"5_CR50","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R.: A personal view of average-case complexity. In: Proceedings of the Tenth Annual Structure in Complexity Theory Conference, pp. 134\u2013147. IEEE Computer Society (1995)","DOI":"10.1109\/SCT.1995.514853"},{"key":"5_CR51","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Efficient arguments without short PCPs. In: CCC, pp. 278\u2013291. IEEE Computer Society (2007)","DOI":"10.1109\/CCC.2007.10"},{"key":"5_CR52","doi-asserted-by":"crossref","unstructured":"Jawale, R., Kalai, Y.T., Khurana, D., Zhang, R.Y.: SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. In: STOC 2021: 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 708\u2013721 (2021)","DOI":"10.1145\/3406325.3451055"},{"key":"5_CR53","doi-asserted-by":"crossref","unstructured":"Kalai, Y., Lombardi, A., Vaikuntanathan, V., Wichs, D.: Boosting batch arguments and RAM delegation. In: STOC, pp. 1545\u20131552. ACM (2023)","DOI":"10.1145\/3564246.3585200"},{"key":"5_CR54","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-662-53644-5_4","volume-title":"Theory of Cryptography","author":"Y Kalai","year":"2016","unstructured":"Kalai, Y., Paneth, O.: Delegating RAM computations. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 91\u2013118. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53644-5_4"},{"key":"5_CR55","doi-asserted-by":"crossref","unstructured":"Kalai, Y.T., Paneth, O., Yang, L.: How to delegate computations publicly. In: STOC, pp. 1115\u20131124. ACM (2019)","DOI":"10.1145\/3313276.3316411"},{"key":"5_CR56","doi-asserted-by":"crossref","unstructured":"Kalai, Y.T., Raz, R., Rothblum, R.D.: How to delegate computations: the power of no-signaling proofs. In: STOC, pp. 485\u2013494. ACM (2014)","DOI":"10.1145\/2591796.2591809"},{"key":"5_CR57","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). https:\/\/doi.org\/10.1007\/978-3-642-17373-8_11"},{"key":"5_CR58","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC, pp. 723\u2013732 (1992)","DOI":"10.1145\/129712.129782"},{"issue":"3","key":"5_CR59","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. Cryptol. 16(3), 143\u2013184 (2003)","journal-title":"J. Cryptol."},{"key":"5_CR60","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. In: CCS, pp. 2111\u20132128. ACM (2019)","DOI":"10.1145\/3319535.3339817"},{"key":"5_CR61","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/3-540-48184-2_32","volume-title":"Advances in Cryptology \u2014 CRYPTO \u201987","author":"RC Merkle","year":"1988","unstructured":"Merkle, R.C.: A digital signature based on a conventional encryption function. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 369\u2013378. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/3-540-48184-2_32"},{"key":"5_CR62","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/0-387-34805-0_21","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 89 Proceedings","author":"RC Merkle","year":"1990","unstructured":"Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218\u2013238. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34805-0_21"},{"key":"5_CR63","doi-asserted-by":"crossref","unstructured":"Micali, S.: CS proofs (extended abstracts). In: 35th Annual Symposium on Foundations of Computer Science, FOCS, pp. 436\u2013453 (1994)","DOI":"10.1109\/SFCS.1994.365746"},{"key":"5_CR64","doi-asserted-by":"crossref","unstructured":"Micali, S., Pass, R.: Local zero knowledge. In: STOC, pp. 306\u2013315. ACM (2006)","DOI":"10.1145\/1132516.1132561"},{"issue":"3\u20134","key":"5_CR65","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s10472-009-9169-y","volume":"56","author":"T Mie","year":"2009","unstructured":"Mie, T.: Short PCPPs verifiable in polylogarithmic time with O(1) queries. Ann. Math. Artif. Intell. 56(3\u20134), 313\u2013338 (2009)","journal-title":"Ann. Math. Artif. Intell."},{"key":"5_CR66","doi-asserted-by":"crossref","unstructured":"Paneth, O., Pass, R.: Incrementally verifiable computation via rate-1 batch arguments. In: FOCS, pp. 1045\u20131056. IEEE (2022)","DOI":"10.1109\/FOCS54457.2022.00102"},{"key":"5_CR67","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-319-70503-3_9","volume-title":"Theory of Cryptography","author":"O Paneth","year":"2017","unstructured":"Paneth, O., Rothblum, G.N.: On zero-testable homomorphic encryption and publicly verifiable non-interactive arguments. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 283\u2013315. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70503-3_9"},{"key":"5_CR68","doi-asserted-by":"crossref","unstructured":"Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. SIAM J. Comput. 50(3) (2021)","DOI":"10.1137\/16M1096773"},{"key":"5_CR69","doi-asserted-by":"crossref","unstructured":"Ron-Zewi, N., Rothblum, R.D.: Local proofs approaching the witness length [extended abstract]. In: FOCS, pp. 846\u2013857. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00083"},{"key":"5_CR70","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1007\/978-3-030-56877-1_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2020","author":"S Setty","year":"2020","unstructured":"Setty, S.: Spartan: efficient and general-purpose zkSNARKs without trusted setup. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 704\u2013737. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-56877-1_25"},{"key":"5_CR71","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/BFb0054137","volume-title":"Advances in Cryptology \u2014 EUROCRYPT\u201998","author":"DR Simon","year":"1998","unstructured":"Simon, D.R.: Finding collisions on a one-way street: can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334\u2013345. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0054137"},{"key":"5_CR72","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/978-3-030-97121-2_19","volume-title":"Public-Key Cryptography","author":"A Szepieniec","year":"2022","unstructured":"Szepieniec, A., Zhang, Y.: Polynomial IOPs for linear algebra relations. In: Hanaoka, G., Shikata, J., Watanabe, Y. (eds.) PKC 2022. LNCS, vol. 13177, pp. 523\u2013552. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-97121-2_19"},{"key":"5_CR73","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-78524-8_1","volume-title":"Theory of Cryptography","author":"P Valiant","year":"2008","unstructured":"Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time\/space efficiency. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 1\u201318. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78524-8_1"},{"key":"5_CR74","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/978-3-031-15979-4_15","volume-title":"Advances in Cryptology","author":"B Waters","year":"2022","unstructured":"Waters, B., Wu, D.J.: Batch arguments for np and more from standard bilinear group assumptions. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13508, pp. 433\u2013463. Springer, Cham (2022). https:\/\/doi.org\/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-58737-5_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T00:04:23Z","timestamp":1777248263000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-58737-5_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031587368","9783031587375"],"references-count":74,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-58737-5_5","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":"28 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"}]}}