{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T16:20:04Z","timestamp":1764606004469,"version":"3.46.0"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032122865","type":"print"},{"value":"9783032122872","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T00:00:00Z","timestamp":1764633600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T00:00:00Z","timestamp":1764633600000},"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-12287-2_14","type":"book-chapter","created":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T16:17:52Z","timestamp":1764605872000},"page":"400-416","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Relativized Succinct Arguments in\u00a0the\u00a0ROM do not Exist"],"prefix":"10.1007","author":[{"given":"Annalisa","family":"Barbara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Chiesa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-2779-7026","authenticated-orcid":false,"given":"Ziyi","family":"Guan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,12,2]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Wigderson, A.: Algebrization: a new barrier in complexity theory. ACM Trans. Comput. Theory 1(1), 2:1\u20132:54 (2009)","DOI":"10.1145\/1490270.1490272"},{"key":"14_CR2","unstructured":"Arora, S., Impagliazzo, R., Vazirani, U.: Relativizing versus nonrelativizing techniques: the role of local checkability (1992, unpublished manuscript)"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Aydinlio\u011flu, B., Bach, E.: Affine relativization: unifying the algebrization and relativization barriers. ACM Trans. Comput. Theory 10(1) (2018)","DOI":"10.1145\/3170704"},{"issue":"4","key":"14_CR4","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T Baker","year":"1975","unstructured":"Baker, T., Gill, J., Solovay, R.: Relativizations of the P =? NP question. SIAM J. Comput. 4(4), 431\u2013442 (1975)","journal-title":"SIAM J. Comput."},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Proceedings of the 14th Theory of Cryptography Conference, TCC 16-B, pp. 31\u201360 (2016)","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Scalable zero knowledge via cycles of elliptic curves. In: Proceedings of the 34th Annual International Cryptology Conference, CRYPTO 2014, pp. 276\u2013294 (2014). Extended version at http:\/\/eprint.iacr.org\/2014\/595","DOI":"10.1007\/978-3-662-44381-1_16"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKs and proof-carrying data. In: Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC 2013, pp. 111\u2013120 (2013)","DOI":"10.1145\/2488608.2488623"},{"issue":"1","key":"14_CR8","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/S0022-0000(05)80084-4","volume":"49","author":"R Chang","year":"1994","unstructured":"Chang, R., et al.: The random oracle hypothesis is false. J. Comput. Syst. Sci. 49(1), 24\u201339 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Chen, M., Chiesa, A., Gur, T., O\u2019Connor, J., Spooner, N.: Proof-carrying data from arithmetized random oracles. In: Proceedings of the 42nd Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT 2023, pp. 379\u2013404 (2023)","DOI":"10.1007\/978-3-031-30617-4_13"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Chen, M., Chiesa, A., Spooner, N.: On succinct non-interactive arguments in relativized worlds. In: Proceedings of the 41st Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT 2022, pp. 336\u2013366 (2022)","DOI":"10.1007\/978-3-031-07085-3_12"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Chiesa, A., Guan, Z., Samocha, S., Yogev, E.: Security bounds for proof-carrying data from straightline extractors. In: Proceedings of the 22nd Theory of Cryptography Conference, TCC 2024, pp. 464\u2013496 (2024)","DOI":"10.1007\/978-3-031-78017-2_16"},{"key":"14_CR12","unstructured":"Chiesa, A., Liu, S.: On the impossibility of probabilistic proofs in relativized worlds. In: Proceedings of the 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 (2020)"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Chiesa, A., Ojha, D., Spooner, N.: Fractal: post-quantum and transparent recursive proofs from holography. In: Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020, pp. 769\u2013793 (2020)","DOI":"10.1007\/978-3-030-45721-1_27"},{"key":"14_CR14","unstructured":"Chiesa, A., Tromer, E.: Proof-carrying data and hearsay arguments from signature cards. In: Proceedings of the 1st Symposium on Innovations in Computer Science, ITCS 2010, pp. 310\u2013331 (2010)"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Chiesa, A., Yogev, E.: Barriers for succinct arguments in the random oracle model. In: Proceedings of the 17th Theory of Cryptography Conference, TCC 2020, pp. 47\u201376 (2020)","DOI":"10.1007\/978-3-030-64378-2_3"},{"key":"14_CR16","unstructured":"Chiesa, A., Yogev, E.: Building Cryptographic Proofs from Hash Functions (2024). https:\/\/github.com\/hash-based-snargs-book"},{"key":"14_CR17","first-page":"1146","volume":"14","author":"M Dekhtyar","year":"1969","unstructured":"Dekhtyar, M.: On the impossibility of eliminating exhaustive search in computing a function relative to its graph. Dokl. Akad. Nauk SSSR 14, 1146\u20131148 (1969)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"14_CR18","first-page":"229","volume":"52","author":"L Fortnow","year":"1994","unstructured":"Fortnow, L.: The role of relativization in complexity theory. Bull. Eur. Assoc. Theor. Comput. Sci. 52, 229\u2013244 (1994)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Hall-Andersen, M., Nielsen, J.B.: On valiant\u2019s conjecture: impossibility of incrementally verifiable computation from random oracles. In: Proceedings of the 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023 (2023)","DOI":"10.1007\/978-3-031-30617-4_15"},{"issue":"3","key":"14_CR20","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0019-9958(86)80012-2","volume":"71","author":"H Heller","year":"1986","unstructured":"Heller, H.: On relativized exponential and probabilistic complexity classes. Inf. Control 71(3), 231\u2013243 (1986)","journal-title":"Inf. Control"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Kabanets, V., Kolokolova, A.: An axiomatic approach to algebrization. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 695\u2013704 (2009)","DOI":"10.1145\/1536414.1536509"},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Kalai, Y.T., Raz, R.: Probabilistically checkable arguments. In: Proceedings of the 29th Annual International Cryptology Conference, CRYPTO 2009, pp. 143\u2013159 (2009)","DOI":"10.1007\/978-3-642-03356-8_9"},{"issue":"17\u201318","key":"14_CR23","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1002\/malq.19860321702","volume":"32","author":"G Lischke","year":"1986","unstructured":"Lischke, G.: Oracle-constructions to prove all possible relationships between relativizations of P, NP, EL, NEL, EP and NEP. Math. Logic Q. 32(17\u201318), 257\u2013270 (1986)","journal-title":"Math. Logic Q."},{"key":"14_CR24","doi-asserted-by":"crossref","unstructured":"Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253\u20131298 (2000). Preliminary version appeared in FOCS\u00a0\u201994","DOI":"10.1137\/S0097539795284959"},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Paneth, O., Pass, R.: Incrementally verifiable computation via rate-1 batch arguments. In: Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2022, pp. 1045\u20131056 (2022)","DOI":"10.1109\/FOCS54457.2022.00102"},{"key":"14_CR26","doi-asserted-by":"crossref","unstructured":"Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time\/space efficiency. In: Proceedings of the 5th Theory of Cryptography Conference, TCC 2008, pp. 1\u201318 (2008)","DOI":"10.1007\/978-3-540-78524-8_1"}],"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-12287-2_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T16:17:57Z","timestamp":1764605877000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-12287-2_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,2]]},"ISBN":["9783032122865","9783032122872"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-12287-2_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,2]]},"assertion":[{"value":"2 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"}}]}}