{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:13:59Z","timestamp":1750306439733,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,8,31]],"date-time":"2015-08-31T00:00:00Z","timestamp":1440979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1041\/08"],"award-info":[{"award-number":["1041\/08"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001658","name":"Minerva Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001658","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2015,9,11]]},"abstract":"<jats:p>\n            An input-oblivious proof system is a proof system in which the proof does not depend on the claim being proved. Input-oblivious versions of\n            <jats:italic>NP<\/jats:italic>\n            and\n            <jats:italic>MA<\/jats:italic>\n            were introduced in passing by Fortnow, Santhanam, and Williams, who also showed that those classes are related to questions on circuit complexity.\n          <\/jats:p>\n          <jats:p>\n            In this article, we wish to highlight the notion of input-oblivious proof systems and initiate a more systematic study of them. We begin by describing in detail the results of Fortnow et al. and discussing their connection to circuit complexity. We then extend the study to input-oblivious versions of\n            <jats:italic>IP<\/jats:italic>\n            , and\n            <jats:italic>PCP<\/jats:italic>\n            , and\n            <jats:italic>ZK<\/jats:italic>\n            and present few preliminary results regarding those versions.\n          <\/jats:p>","DOI":"10.1145\/2799645","type":"journal-article","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T13:41:09Z","timestamp":1441114869000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P\/poly"],"prefix":"10.1145","volume":"7","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}]},{"given":"Or","family":"Meir","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}]}],"member":"320","published-online":{"date-parts":[[2015,8,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2007.0113"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1142\/S012905419500010X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200430"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(74)90473-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_18"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.21"},{"volume-title":"Foundation of Cryptography\u2014Basic Tools","author":"Goldreich O.","key":"e_1_2_1_9_1","unstructured":"O. Goldreich . 2001. Foundation of Cryptography\u2014Basic Tools . Cambridge University Press . O. Goldreich. 2001. Foundation of Cryptography\u2014Basic Tools. Cambridge University Press."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199712)11:4%3C315::AID-RSA3%3E3.0.CO;2-1"},{"volume-title":"Proceedings of the 16th IEEE Conference on Computational Complexity. 2--12","author":"Impagliazzo R.","key":"e_1_2_1_12_1","unstructured":"R. Impagliazzo , V. Kabanets , and A. Wigderson . 2001. In search of an easy witness: Exponential time vs. probabilistic polynomial time . In Proceedings of the 16th IEEE Conference on Computational Complexity. 2--12 . R. Impagliazzo, V. Kabanets, and A. Wigderson. 2001. In search of an easy witness: Exponential time vs. probabilistic polynomial time. In Proceedings of the 16th IEEE Conference on Computational Complexity. 2--12."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804678"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90078-8"},{"key":"e_1_2_1_15_1","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology\u2014CRYPTO\u201994","author":"Krawczyk H.","unstructured":"H. Krawczyk . 1994. LFSR-based hashing and authentication . In Advances in Cryptology\u2014CRYPTO\u201994 . Lecture Notes in Computer Science , Vol. 839 . Springer , 129--139. H. Krawczyk. 1994. LFSR-based hashing and authentication. In Advances in Cryptology\u2014CRYPTO\u201994. Lecture Notes in Computer Science, Vol. 839. Springer, 129--139."},{"key":"e_1_2_1_16_1","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology\u2014EUROCRYPT\u201995","author":"Krawczyk H.","unstructured":"H. Krawczyk . 1995. New hash functions for message authentication . In Advances in Cryptology\u2014EUROCRYPT\u201995 . Lecture Notes in Computer Science , Vol. 921 . Springer , 301--310. H. Krawczyk. 1995. New hash functions for message authentication. In Advances in Cryptology\u2014EUROCRYPT\u201995. Lecture Notes in Computer Science, Vol. 921. Springer, 301--310."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90044-3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979630091X"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90158-6"},{"key":"e_1_2_1_22_1","volume-title":"Mathematical Foundations of Computer Science","author":"Sch\u00f6ning U.","year":"1988","unstructured":"U. Sch\u00f6ning . 1988. Robust oracle machines . In Mathematical Foundations of Computer Science 1988 . Lecture Notes in Computer Science, Vol. 324 . Springer , 93--106. U. Sch\u00f6ning. 1988. Robust oracle machines. In Mathematical Foundations of Computer Science 1988. Lecture Notes in Computer Science, Vol. 324. Springer, 93--106."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2799645","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2799645","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:42:43Z","timestamp":1750225363000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2799645"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,31]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,9,11]]}},"alternative-id":["10.1145\/2799645"],"URL":"https:\/\/doi.org\/10.1145\/2799645","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2015,8,31]]},"assertion":[{"value":"2014-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}