{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:59:27Z","timestamp":1781078367567,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["SATC-1704788,RI-1703846"],"award-info":[{"award-number":["SATC-1704788,RI-1703846"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451121","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"722-735","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity"],"prefix":"10.1145","author":[{"given":"Yanyi","family":"Liu","sequence":"first","affiliation":[{"name":"Cornell University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[{"name":"Cornell University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45294-X_1"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628994"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706594"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055466"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96884-1_26"},{"key":"e_1_3_2_1_6_1","volume-title":"The Average-Case Complexity of Counting Cliques in Erdos-R\u00e9nyi Hypergraphs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). Pages 1256\u20131280","author":"Enric","unstructured":"Enric Boix-Adser\\`a, Matthew Brennan, and Guy Bresler. 2019. The Average-Case Complexity of Counting Cliques in Erdos-R\u00e9nyi Hypergraphs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). Pages 1256\u20131280."},{"key":"e_1_3_2_1_7_1","volume-title":"Beyond Natural Proofs: Hardness Magnification and Locality. In 11th Innovations in Theoretical Computer Science Conference (ITCS","author":"Chen Lijie","year":"2020","unstructured":"Lijie Chen, Shuichi Hirahara, Igor C Oliveira, J\u00e1n Pich, Ninad Rajgopal, and Rahul Santhanam. 2020. Beyond Natural Proofs: Hardness Magnification and Locality. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00077"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.30"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316333"},{"key":"e_1_3_2_1_11_1","volume-title":"New Techniques for Proving Fine-Grained Average-Case Hardness. arXiv preprint arXiv:2008.06591","author":"Dalirrooyfard Mina","year":"2020","unstructured":"Mina Dalirrooyfard, Andrea Lincoln, and Virginia Vassilevska Williams. 2020. New Techniques for Proving Fine-Grained Average-Case Hardness. arXiv preprint arXiv:2008.06591, 2020."},{"key":"e_1_3_2_1_12_1","volume-title":"Foundations of Cryptography \u2013- Basic Tools","author":"Goldreich Oded","unstructured":"Oded Goldreich. 2001. Foundations of Cryptography \u2013- Basic Tools. Cambridge University Press."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Oded Goldreich Shafi Goldwasser and Silvio Micali. 1984. On the Cryptographic Applications of Random Functions. In CRYPTO. Pages 276\u2013288.","DOI":"10.1007\/3-540-39568-7_22"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00017"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Iftach Haitner Danny Harnik and Omer Reingold. 2006. On the Power of the Randomized Iterate. In CRYPTO. Pages 22\u201340.","DOI":"10.1007\/11818175_2"},{"key":"e_1_3_2_1_17_1","first-page":"2010","article-title":"Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions","volume":"17","author":"Haitner Iftach","year":"2010","unstructured":"Iftach Haitner, Omer Reingold, and Salil P. Vadhan. 2010. Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions. Electronic Colloquium on Computational Complexity (ECCC), 17, 2010. Pages 89.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.21"},{"key":"e_1_3_2_1_19_1","first-page":"4","article-title":"A Pseudorandom Generator from any One-way Function","volume":"28","author":"Johan","year":"1999","unstructured":"Johan H\\r astad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. 1999. A Pseudorandom Generator from any One-way Function. SIAM J. Comput., 28, 4, 1999. Pages 1364\u20131396.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384251"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335314"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90081-2"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207166808803030"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26954-8_20"},{"key":"e_1_3_2_1_25_1","volume-title":"Amplifying circuit lower bounds against polynomial time, with applications. computational complexity, 22, 2","author":"Lipton Richard J","year":"2013","unstructured":"Richard J Lipton and Ryan Williams. 2013. Amplifying circuit lower bounds against polynomial time, with applications. computational complexity, 22, 2, 2013. Pages 311\u2013343."},{"key":"e_1_3_2_1_26_1","first-page":"2020","article-title":"On One-way Functions and Kolmogorov Complexity","volume":"42","author":"Liu Yanyi","year":"2020","unstructured":"Yanyi Liu and Rafael Pass. 2020. On One-way Functions and Kolmogorov Complexity. Electronic Colloquium on Computational Complexity (ECCC), 42, 2020.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316396"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2019.102735"},{"key":"e_1_3_2_1_29_1","volume-title":"Hardness magnification near state-of-the-art lower bounds","author":"Oliveira Igor","year":"2019","unstructured":"Igor Oliveira, J\u00e1n Pich, and Rahul Santhanam. 2019. Hardness magnification near state-of-the-art lower bounds. 2019."},{"key":"e_1_3_2_1_30_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Oliveira Igor Carboni","year":"2019","unstructured":"Igor Carboni Oliveira. 2019. Randomness and intractability in Kolmogorov complexity. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00016"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808762"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/230514.571645"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00110-7"},{"key":"e_1_3_2_1_35_1","first-page":"4","article-title":"A survey of Russian approaches to perebor (brute-force searches) algorithms","volume":"6","author":"Trakhtenbrot Boris A","year":"1984","unstructured":"Boris A Trakhtenbrot. 1984. A survey of Russian approaches to perebor (brute-force searches) algorithms. Annals of the History of Computing, 6, 4, 1984. Pages 384\u2013400.","journal-title":"Annals of the History of Computing"},{"key":"e_1_3_2_1_36_1","first-page":"1","article-title":"The algorithmic difficulties of synthesizing minimal switching circuits","volume":"2","author":"Yablonski Sergey","year":"1959","unstructured":"Sergey Yablonski. 1959. The algorithmic difficulties of synthesizing minimal switching circuits. Problemy Kibernetiki, 2, 1, 1959. Pages 75\u2013121.","journal-title":"Problemy Kibernetiki"},{"key":"e_1_3_2_1_37_1","first-page":"1","article-title":"On the impossibility of eliminating perebor in solving some problems of circuit theory","volume":"124","author":"Yablonski Sergey V","year":"1959","unstructured":"Sergey V Yablonski. 1959. On the impossibility of eliminating perebor in solving some problems of circuit theory. Doklady Akademii Nauk SSSR, 124, 1, 1959. Pages 44\u201347.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"e_1_3_2_1_38_1","first-page":"91","volume-title":"23rd Annual Symposium on Foundations of Computer Science","author":"Chi-Chih Yao Andrew","year":"1982","unstructured":"Andrew Chi-Chih Yao. 1982. Theory and Applications of Trapdoor Functions (Extended Abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982. Pages 80\u201391."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451121","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451121","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":38,"alternative-id":["10.1145\/3406325.3451121","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451121","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}