{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,28]],"date-time":"2024-04-28T00:15:24Z","timestamp":1714263324874},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2023,5]]},"abstract":"\n Let\n Kt<\/jats:italic>\n (\n x<\/jats:italic>\n ) denote the Levin-Kolmogorov Complexity of the string\n x<\/jats:italic>\n , and let MKtP denote the language of pairs (\n x<\/jats:italic>\n ,\n k<\/jats:italic>\n ) having the property that\n Kt<\/jats:italic>\n (\n x<\/jats:italic>\n ) \u2264\n k.<\/jats:italic>\n We demonstrate that:\n <\/jats:p>\n \n \u2022 MKtP \u2209 Heur\n neg<\/jats:sub>\n BPP (i.e., MKtP is\n two-sided error<\/jats:italic>\n mildly average-case hard) iff infinitely-often OWFs exist.\n <\/jats:p>\n \n \u2022 MKtP \u2209 Avg\n neg<\/jats:sub>\n BPP (i.e., MKtP is\n errorless<\/jats:italic>\n mildly average-case hard) iff EXP \u2260 BPP.\n <\/jats:p>\n Taken together, these results show that the only \"gap\" toward getting (infinitely-often) OWFs from the assumption that EXP \u2260 BPP is the seemingly \"minor\" technical gap between two-sided error and errorless average-case hardness of the MKtP problem.<\/jats:p>","DOI":"10.1145\/3587167","type":"journal-article","created":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T14:34:35Z","timestamp":1682087675000},"page":"91-99","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Toward Basing Cryptography on the Hardness of EXP"],"prefix":"10.1145","volume":"66","author":[{"given":"Yanyi","family":"Liu","sequence":"first","affiliation":[{"name":"Cornell Tech, New York, NY, USA"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[{"name":"Cornell Tech, New York, NY, and Tel-Aviv University, Israel"}]}],"member":"320","published-online":{"date-parts":[[2023,4,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628994"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"e_1_2_1_3_1","volume-title":"Manuscript","author":"Bogdanov A.","year":"2008","unstructured":"Bogdanov, A., Trevisan, L. Average-case complexity. Manuscript, 2008. http:\/\/arxiv.org\/abs\/cs.CC\/0606037."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36494-3_20"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/321526.321530"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"e_1_2_1_7_1","first-page":"288","article-title":"On the cryptographic applications of random functions","volume":"276","author":"Goldreich O.","year":"1984","unstructured":"Goldreich, O., Goldwasser, S., Micali, S. On the cryptographic applications of random functions. In CRYPTO. 1984, 276--288.","journal-title":"CRYPTO"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.21"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0170805-7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63483"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_2_1_14_1","first-page":"743","article-title":"Randomness vs. time: de-randomization under a uniform assumption. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280)","volume":"734","author":"Impagliazzo R.","year":"1998","unstructured":"Impagliazzo, R., Wigderson, A. Randomness vs. time: de-randomization under a uniform assumption. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280). IEEE, 1998, 734--743.","journal-title":"IEEE"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90081-2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207166808803030"},{"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","first-page":"3","article-title":"Universal search problems (russian), translated into English by BA Trakhtenbrot in [27]","volume":"9","author":"Levin L.A","year":"1973","unstructured":"Levin, L.A. Universal search problems (russian), translated into English by BA Trakhtenbrot in [27]. Prob. Inf. Transm 9, 3 (1973), 265--266.","journal-title":"Prob. Inf. Transm"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023645529386"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00118"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_2_1_22_1","first-page":"17","article-title":"One-way fuctions are essential for non-trivial zero-knowledge","volume":"3","author":"Ostrovsky R.","year":"1993","unstructured":"Ostrovsky, R., Wigderson, A. One-way fuctions are essential for non-trivial zero-knowledge. In ISTCS, 1993, 3--17.","journal-title":"ISTCS"},{"key":"e_1_2_1_23_1","first-page":"57","article-title":"Hardness of KT characterizes parallel cryptography","volume":"28","author":"Ren H.","year":"2021","unstructured":"Ren, H., Santhanam, R. Hardness of KT characterizes parallel cryptography. Electron. Colloquium Comput. Complex 28, 57 (2021).","journal-title":"Electron. Colloquium Comput. Complex"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808762"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/230514.571645"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90223-2"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1984.10036"},{"key":"e_1_2_1_28_1","first-page":"0129","article-title":"Pseudorandomness and average-case complexity via uniform reductions. In Proceedings 17th IEEE Annual Conference on Computational Complexity","volume":"0129","author":"Trevisan L.","year":"2002","unstructured":"Trevisan, L., Vadhan, S. Pseudorandomness and average-case complexity via uniform reductions. In Proceedings 17th IEEE Annual Conference on Computational Complexity. IEEE Computer Society, 2002, 0129--0129.","journal-title":"IEEE Computer Society"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382790"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3587167","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,27]],"date-time":"2024-04-27T10:05:38Z","timestamp":1714212338000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3587167"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,21]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["10.1145\/3587167"],"URL":"https:\/\/doi.org\/10.1145\/3587167","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,21]]},"assertion":[{"value":"2023-04-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}