{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:36:55Z","timestamp":1766281015143,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031158018"},{"type":"electronic","value":"9783031158025"}],"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.springernature.com\/gp\/researchers\/text-and-data-mining"},{"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.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-15802-5_18","type":"book-chapter","created":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T16:59:52Z","timestamp":1665507592000},"page":"504-532","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Succinct Interactive Oracle Proofs: Applications and\u00a0Limitations"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7388-3858","authenticated-orcid":false,"given":"Shafik","family":"Nassar","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5481-7276","authenticated-orcid":false,"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,12]]},"reference":[{"key":"18_CR1","unstructured":"Applebaum, B., Golombek, E.: On the randomness complexity of interactive proofs and statistical zero-knowledge proofs. In: Tessaro, S. (ed.) 2nd Conference on Information-Theoretic Cryptography, ITC 2021, 23\u201326 July 2021, Virtual Conference. LIPIcs, vol. 199, pp. 4:1\u20134:23. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"18_CR2","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, Part II. LNCS, vol. 9986, pp. 31\u201360. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53644-5_2"},{"key":"18_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1007\/978-3-319-96878-0_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"I Berman","year":"2018","unstructured":"Berman, I., Degwekar, A., Rothblum, R.D., Vasudevan, P.N.: From laconic zero-knowledge to public-key cryptography. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part III. LNCS, vol. 10993, pp. 674\u2013697. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96878-0_23"},{"key":"18_CR4","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":"18_CR5","doi-asserted-by":"crossref","unstructured":"Brakerski, Z.: Fundamentals of fully homomorphic encryption. In: Goldreich, O. (ed.) Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pp. 543\u2013563. ACM (2019)","DOI":"10.1145\/3335741.3335762"},{"key":"18_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1007\/978-3-662-46497-7_19","volume-title":"Theory of Cryptography","author":"R Canetti","year":"2015","unstructured":"Canetti, R., Lin, H., Tessaro, S., Vaikuntanathan, V.: Obfuscation of probabilistic circuits and applications. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 468\u2013497. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46497-7_19"},{"key":"18_CR7","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, Part II. LNCS, vol. 12551, pp. 47\u201376. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64378-2_3"},{"issue":"1","key":"18_CR8","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"18_CR9","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1007\/s00145-014-9184-y","volume":"28","author":"C Gentry","year":"2015","unstructured":"Gentry, C., Groth, J., Ishai, Y., Peikert, C., Sahai, A., Smith, A.D.: Using fully homomorphic hybrid encryption to minimize non-interative zero-knowledge proofs. J. Cryptol. 28(4), 820\u2013843 (2015)","journal-title":"J. Cryptol."},{"issue":"4","key":"18_CR10","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O Goldreich","year":"1986","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792\u2013807 (1986)","journal-title":"J. ACM"},{"issue":"4","key":"18_CR11","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)","journal-title":"Inf. Process. Lett."},{"key":"18_CR12","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"},{"key":"18_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/3-540-47721-7_11","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 86","author":"O Goldreich","year":"1987","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to prove all NP statements in zero-knowledge and a methodology of cryptographic protocol design (extended abstract). In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 171\u2013185. Springer, Heidelberg (1987). https:\/\/doi.org\/10.1007\/3-540-47721-7_11"},{"key":"18_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656","volume-title":"The Foundations of Cryptography - Volume 2: Basic Applications","author":"O Goldreich","year":"2004","unstructured":"Goldreich, O.: The Foundations of Cryptography - Volume 2: Basic Applications. Cambridge University Press, Cambridge (2004)"},{"key":"18_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106","volume-title":"Computational Complexity - A Conceptual Perspective","author":"Oded Goldreich","year":"2008","unstructured":"Goldreich, Oded: Computational Complexity - A Conceptual Perspective. Cambridge University Press, Cambridge (2008)"},{"issue":"1","key":"18_CR16","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s00037-016-0136-9","volume":"27","author":"T Gur","year":"2016","unstructured":"Gur, T., Rothblum, R.D.: Non-interactive proofs of proximity. Comput. Complex. 27(1), 99\u2013207 (2016). https:\/\/doi.org\/10.1007\/s00037-016-0136-9","journal-title":"Comput. Complex."},{"issue":"1","key":"18_CR17","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s00037-009-0282-4","volume":"19","author":"O Goldreich","year":"2010","unstructured":"Goldreich, O., Sheffet, O.: On the randomness complexity of property testing. Comput. Complex. 19(1), 99\u2013133 (2010)","journal-title":"Comput. Complex."},{"issue":"1\u20132","key":"18_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-002-0169-0","volume":"11","author":"O Goldreich","year":"2002","unstructured":"Goldreich, O., Vadhan, S.P., Wigderson, A.: On interactive proofs with a laconic prover. Comput. Complex. 11(1\u20132), 1\u201353 (2002)","journal-title":"Comput. Complex."},{"issue":"4","key":"18_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)","journal-title":"SIAM J. Comput."},{"issue":"301","key":"18_CR20","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"issue":"3","key":"18_CR21","doi-asserted-by":"publisher","first-page":"1121","DOI":"10.1137\/080725398","volume":"39","author":"Y Ishai","year":"2009","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge proofs from secure multiparty computation. SIAM J. Comput. 39(3), 1121\u20131152 (2009)","journal-title":"SIAM J. Comput."},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: Kosaraju, S.R., Fellows, M., Wigderson, A., Ellis, J.A. (eds.) Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 4\u20136 May 1992, Victoria, British Columbia, Canada, pp. 723\u2013732. ACM (1992)","DOI":"10.1145\/129712.129782"},{"key":"18_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/978-3-540-70583-3_44","volume-title":"Automata, Languages and Programming","author":"YT Kalai","year":"2008","unstructured":"Kalai, Y.T., Raz, R.: Interactive PCP. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 536\u2013547. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70583-3_44"},{"issue":"4","key":"18_CR24","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/S0097539795284959","volume":"30","author":"S Micali","year":"2000","unstructured":"Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253\u20131298 (2000)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"18_CR25","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF00196774","volume":"4","author":"M Naor","year":"1991","unstructured":"Naor, M.: Bit commitment using pseudorandomness. J. Cryptol. 4(2), 151\u2013158 (1991). https:\/\/doi.org\/10.1007\/BF00196774","journal-title":"J. Cryptol."},{"issue":"2","key":"18_CR26","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I Newman","year":"1991","unstructured":"Newman, I.: Private vs. common random bits in communication complexity. Inf. Process. Lett. 39(2), 67\u201371 (1991)","journal-title":"Inf. Process. Lett."},{"key":"18_CR27","unstructured":"Nassar, S., Rothblum, R.D.: Succinct interactive oracle proofs: applications and limitations. Cryptology ePrint Archive, Paper 2022\/281 (2022). https:\/\/eprint.iacr.org\/2022\/281"},{"key":"18_CR28","unstructured":"Ostrovsky, R., Wigderson, A.: One-way functions are essential for non-trivial zero-knowledge. In: Proceedings of the Second Israel Symposium on Theory of Computing Systems, ISTCS 1993, Natanya, Israel, 7\u20139 June 1993, pp. 3\u201317. IEEE Computer Society (1993)"},{"key":"18_CR29","doi-asserted-by":"crossref","unstructured":"Ron-Zewi, N., Rothblum, R.D.: Local proofs approaching the witness length [extended abstract]. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, 16\u201319 November 2020, pp. 846\u2013857. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00083"},{"key":"18_CR30","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":"18_CR31","unstructured":"How do we know that P != LINSPACE without knowing if one is a subset of the other? (2014). https:\/\/mathoverflow.net\/questions\/40770\/how-do-we-know-that-p-linspace-without-knowing-if-one-is-a-subset-of-the-othe. Accessed 2 Feb 2022"}],"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-15802-5_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:06:01Z","timestamp":1760133961000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-15802-5_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031158018","9783031158025"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-15802-5_18","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"}}]}}