{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T13:10:47Z","timestamp":1765113047790,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","funder":[{"name":"NSF (National Science Foundation)","award":["CCF-2145474"],"award-info":[{"award-number":["CCF-2145474"]}]},{"name":"Defense Advanced Research Projects Agency","award":["HR00112020023"],"award-info":[{"award-number":["HR00112020023"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718144","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"189-200","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Quantum-Computable One-Way Functions without One-Way Functions"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7784-9817","authenticated-orcid":false,"given":"William","family":"Kretschmer","sequence":"first","affiliation":[{"name":"University of California, Berkeley, Berkeley, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1112-8822","authenticated-orcid":false,"given":"Luowen","family":"Qian","sequence":"additional","affiliation":[{"name":"NTT Research, Inc., Sunnyvale, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0375-6554","authenticated-orcid":false,"given":"Avishay","family":"Tal","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a001"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806711"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","unstructured":"Scott Aaronson. 2016. The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes. https:\/\/doi.org\/10.48550\/arXiv.1607.05256 arxiv:1607.05256. 10.48550\/arXiv.1607.05256","DOI":"10.48550\/arXiv.1607.05256"},{"key":"e_1_3_2_1_4_1","unstructured":"Scott Aaronson. 2018. The relativized BQP vs. PH problem (1993-2018). https:\/\/scottaaronson.blog\/?p=3827"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a006"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897644"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.20"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a007"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22318-1_9"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2024.6"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15802-5_8"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15979-4_6"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","unstructured":"Mohammed Barhoush Amit Behera Lior Ozer Louis Salvail and Or Sattath. 2024. Signatures From Pseudorandom States via \u22a5 -PRFs. https:\/\/doi.org\/10.48550\/arXiv.2311.00847 arxiv:2311.00847v5. 10.48550\/arXiv.2311.00847","DOI":"10.48550\/arXiv.2311.00847"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.76.2818"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-48624-1_8"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1999.766280"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"volume-title":"Proceedings of IEEE International Conference on Computers, Systems and Signal Processing. IEEE Computer Society","author":"Charles","key":"e_1_3_2_1_18_1","unstructured":"Charles H. Bennett and Gilles Brassard. 1984. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of IEEE International Conference on Computers, Systems and Signal Processing. IEEE Computer Society, New York, NY, USA. 8."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008908.1008911"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","unstructured":"John Bostanci Yuval Efron Tony Metger Alexander Poremba Luowen Qian and Henry Yuen. 2023. Unitary Complexity and the Uhlmann Transformation Problem. https:\/\/doi.org\/10.48550\/arXiv.2306.13073 arxiv:2306.13073. 10.48550\/arXiv.2306.13073","DOI":"10.48550\/arXiv.2306.13073"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.62056\/ahvr-11zn4"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-36030-6_10"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-56880-1_15"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00037"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68394-7_8"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00068"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","unstructured":"Andrea Coladangelo. 2023. Quantum trapdoor functions from classical one-way functions. https:\/\/doi.org\/10.48550\/arXiv.2302.12821 arxiv:2302.12821. 10.48550\/arXiv.2302.12821","DOI":"10.48550\/arXiv.2302.12821"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892121"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90010-U"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Daniel Gottesman and Isaac Chuang. 2001. Quantum Digital Signatures. https:\/\/doi.org\/10.48550\/arXiv.quant-ph\/0105032 arxiv:quant-ph\/0105032. 10.48550\/arXiv.quant-ph\/0105032","DOI":"10.48550\/arXiv.quant-ph"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1995.514853"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63483"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73012"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96878-0_5"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","unstructured":"Dakshita Khurana and Kabir Tomer. 2024. Founding Quantum Cryptography on Quantum Advantage or Towards Cryptography from #P-Hardness. https:\/\/doi.org\/10.48550\/arXiv.2409.15248 arxiv:2409.15248. 10.48550\/arXiv.2409.15248","DOI":"10.48550\/arXiv.2409.15248"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68394-7_4"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2021.2"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585225"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","unstructured":"William Kretschmer Luowen Qian and Avishay Tal. 2024. Quantum-Computable One-Way Functions without One-Way Functions. https:\/\/doi.org\/10.48550\/arXiv.2411.02554 arxiv:2411.02554. 10.48550\/arXiv.2411.02554","DOI":"10.48550\/arXiv.2411.02554"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68394-7_6"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649650"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","unstructured":"Fermi Ma and Hsin-Yuan Huang. 2024. How to Construct Random Unitaries. https:\/\/doi.org\/10.48550\/arXiv.2410.10116 arxiv:2410.10116. 10.48550\/arXiv.2410.10116","DOI":"10.48550\/arXiv.2410.10116"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5_41"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68394-7_5"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","unstructured":"Tony Metger Alexander Poremba Makrand Sinha and Henry Yuen. 2024. Simple constructions of linear-depth t-designs and pseudorandom unitaries. https:\/\/doi.org\/10.48550\/arXiv.2404.12647 arxiv:2404.12647. 10.48550\/arXiv.2404.12647","DOI":"10.48550\/arXiv.2404.12647"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15802-5_10"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316315"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24638-1_1"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11659-4_15"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450745"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:40:17Z","timestamp":1750693217000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":52,"alternative-id":["10.1145\/3717823.3718144","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718144","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}