{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T22:09:43Z","timestamp":1764886183763,"version":"3.46.0"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032122896","type":"print"},{"value":"9783032122902","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T00:00:00Z","timestamp":1764892800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T00:00:00Z","timestamp":1764892800000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-12290-2_2","type":"book-chapter","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T22:06:53Z","timestamp":1764886013000},"page":"37-70","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Time-Space Trade-Offs for\u00a0Sumcheck"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5563-0630","authenticated-orcid":false,"given":"Anubhav","family":"Baweja","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3029-2353","authenticated-orcid":false,"given":"Alessandro","family":"Chiesa","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0008-0118-9526","authenticated-orcid":false,"given":"Elisabetta","family":"Fedele","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3702-1780","authenticated-orcid":false,"given":"Giacomo","family":"Fenzi","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0000-6600-9719","authenticated-orcid":false,"given":"Pratyush","family":"Mishra","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0009-8598-3643","authenticated-orcid":false,"given":"Tushar","family":"Mopuri","sequence":"additional","affiliation":[]},{"given":"Andrew","family":"Zitek-Estrada","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"2_CR1","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/978-3-031-68403-6_12","volume-title":"CRYPTO 2024","author":"G Arnon","year":"2024","unstructured":"Arnon, G., Chiesa, A., Fenzi, G., Yogev, E.: STIR: Reed-Solomon proximity testing with fewer queries. In: Reyzin, L., Stebila, D. (eds.) CRYPTO 2024. LNCS, vol. 14929, pp. 380\u2013413. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-68403-6_12"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Athamnah, N., Ron-Zewi, N., Rothblum, R.: Linear Prover IOPs in Log Star Rounds (2025). ECCC TR25-090","DOI":"10.1007\/978-3-032-12287-2_12"},{"key":"2_CR3","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 1991, pp. 21\u201332 (1991)","DOI":"10.1145\/103418.103428"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex. 1, 3\u201340 (1991)","journal-title":"Comput. Complex."},{"key":"2_CR5","unstructured":"Baweja, A., Mishra, P., Mopuri, T., Newatia, K., Wang, S.: Scribe: low-memory SNARKs via read-write streaming. Cryptology ePrint Archive Report 2024\/1970 (2024). https:\/\/eprint.iacr.org\/2024\/1970"},{"key":"2_CR6","unstructured":"Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast Reed-Solomon interactive oracle proofs of proximity. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, pp. 14:1\u201314:17 (2018)"},{"key":"2_CR7","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":"2_CR8","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":"2_CR9","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":"2_CR10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/978-3-031-07085-3_15","volume-title":"EUROCRYPT 2022","author":"J Bootle","year":"2022","unstructured":"Bootle, J., Chiesa, A., Hu, Y., Orr\u00fa, M.: Gemini: elastic SNARKs for diverse environments. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13276, pp. 427\u2013457. Springer, Cham (2022)"},{"key":"2_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":"2_CR12","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-031-30617-4_17","volume-title":"EUROCRYPT 2023","author":"B Chen","year":"2023","unstructured":"Chen, B., B\u00fcnz, B., Boneh, D., Zhang, Z.: HyperPlonk: plonk with linear-time prover and high-degree custom gates. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14005, pp. 499\u2013530. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30617-4_17"},{"key":"2_CR13","unstructured":"Chiesa, A., Fedele, E., Fenzi, G., Zitek-Estrada, A.: A time-space tradeoff for the sumcheck prover. Cryptology ePrint Archive Paper 2024\/524 (2024). https:\/\/eprint.iacr.org\/2024\/524"},{"key":"2_CR14","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":"2_CR15","doi-asserted-by":"crossref","unstructured":"Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: Proceedings of the 4th Symposium on Innovations in Theoretical Computer Science, ITCS 2012, pp. 90\u2013112 (2012)","DOI":"10.1145\/2090236.2090245"},{"issue":"1","key":"2_CR16","doi-asserted-by":"publisher","first-page":"25","DOI":"10.14778\/2047485.2047488","volume":"5","author":"G Cormode","year":"2011","unstructured":"Cormode, G., Thaler, J., Yi, K.: Verifying computations with streaming interactive proofs. Proc. VLDB Endow. 5(1), 25\u201336 (2011)","journal-title":"Proc. VLDB Endow."},{"key":"2_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1007\/978-3-642-14623-7_35","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"A De","year":"2010","unstructured":"De, A., Trevisan, L., Tulsiani, M.: Time space tradeoffs for attacks against one-way functions and PRGs. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 649\u2013665. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14623-7_35"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. J. ACM 62(4), 27:1\u201327:64 (2015)","DOI":"10.1145\/2699436"},{"issue":"1","key":"2_CR19","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00037-009-0263-7","volume":"18","author":"A Juma","year":"2009","unstructured":"Juma, A., Kabanets, V., Rackoff, C., Shpilka, A.: The black-box query complexity of polynomial summation. Comput. Complex. 18(1), 59\u201379 (2009)","journal-title":"Comput. Complex."},{"key":"2_CR20","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"},{"issue":"1","key":"2_CR21","doi-asserted-by":"publisher","first-page":"15","DOI":"10.62056\/abksdk5vt","volume":"2","author":"C Levrat","year":"2025","unstructured":"Levrat, C., Medevielle, T., Nardi, J.: A divide-and-conquer sumcheck protocol. IACR Commun. Cryptol. 2(1), 15 (2025)","journal-title":"IACR Commun. Cryptol."},{"issue":"4","key":"2_CR22","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)","journal-title":"J. ACM"},{"key":"2_CR23","unstructured":"Nair, V., Thaler, J., Zhu, M.: Proving CPU executions in small space. Cryptology ePrint Archive, Paper 2025\/611 (2025). https:\/\/eprint.iacr.org\/2025\/611"},{"key":"2_CR24","unstructured":"Pappas, C., Papadopoulos, D.: Hobbit: space-efficient zkSNARK with optimal prover time. Cryptology ePrint Archive, Paper 2025\/1214 (2025). https:\/\/eprint.iacr.org\/2025\/1214"},{"key":"2_CR25","doi-asserted-by":"crossref","unstructured":"Pappas, C., Papadopoulos, D.: Sparrow: space-efficient zkSNARK for data-parallel circuits and applications to zero-knowledge decision trees. In: Proceedings of the ACM Conference on Computer and Communications Security, CCS 2024, pp. 3110\u20133124 (2024)","DOI":"10.1145\/3658644.3690318"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"Raz, R.: On the complexity of matrix product. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, STOC 2002, pp. 144\u2013151 (2002)","DOI":"10.1145\/509907.509932"},{"key":"2_CR27","unstructured":"Rothblum, R.: A Note on Efficient Computation of the Multilinear Extension (2024). https:\/\/eprint.iacr.org\/2024\/1103"},{"key":"2_CR28","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":"2_CR29","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-031-58751-1_7","volume-title":"EUROCRYPT 2024","author":"S Setty","year":"2024","unstructured":"Setty, S., Thaler, J., Wahby, R.: Unlocking the lookup singularity with lasso. In: Joye, M., Leander, G. (eds.) EUROCRYPT 2024. LNCS, vol. 14656, pp. 180\u2013209. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-58751-1_7"},{"issue":"4","key":"2_CR30","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\u201377 (1992)","journal-title":"J. ACM"},{"issue":"3\u20134","key":"2_CR31","first-page":"207","volume":"5","author":"A Shpilka","year":"2010","unstructured":"Shpilka, A., Yehudayoff, A.: Arithmetic circuits: a survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5(3\u20134), 207\u2013388 (2010)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"2_CR32","unstructured":"Singh, N., Patranabis, S.: SubLogarithmic linear time SNARKs from compressed sum-check. Cryptology ePrint Archive, Paper 2025\/908 (2025). https:\/\/eprint.iacr.org\/2025\/908"},{"key":"2_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-642-40084-1_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"J Thaler","year":"2013","unstructured":"Thaler, J.: Time-optimal interactive proofs for circuit evaluation. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 71\u201389. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40084-1_5"},{"key":"2_CR34","doi-asserted-by":"crossref","unstructured":"Vu, V., Setty, S., Blumberg, A.J., Walfish, M.: A hybrid architecture for interactive verifiable computation. In: Proceedings of the 34th IEEE Symposium on Security and Privacy, S &P 2013, pp. 223\u2013237 (2013)","DOI":"10.1109\/SP.2013.48"},{"key":"2_CR35","unstructured":"Zhang, S., Cai, D., Li, Y., Kan, H., Zhang, L.: Epistle: elastic succinct arguments for plonk constraint system. IACR ePrint Report 2024\/872 (2024). https:\/\/eprint.iacr.org\/2024\/872"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-12290-2_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T22:06:56Z","timestamp":1764886016000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-12290-2_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,5]]},"ISBN":["9783032122896","9783032122902"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-12290-2_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,5]]},"assertion":[{"value":"5 December 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Aarhus","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Denmark","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 December 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 December 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}