{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T04:23:30Z","timestamp":1770783810232,"version":"3.50.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T00:00:00Z","timestamp":1718064000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["1749731"],"award-info":[{"award-number":["1749731"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>\n            We show the following hold, unconditionally unless otherwise stated, relative to a random oracle:\n            <jats:list list-type=\"simple\">\n              <jats:list-item>\n                <jats:label>\u2014<\/jats:label>\n                <jats:p>\n                  There are NP\n                  <jats:italic>search<\/jats:italic>\n                  problems solvable by quantum polynomial-time (QPT) machines but not classical probabilistic polynomial-time (PPT) machines.\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>\u2014<\/jats:label>\n                <jats:p>There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar counterexamples exist for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the counterexample does not necessarily extend to the case of other cryptographic objects such as PRGs.<\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>\u2014<\/jats:label>\n                <jats:p>There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin.<\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>\u2014<\/jats:label>\n                <jats:p>Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction.<\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n            By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and\/or algebraic assumptions in Cryptomania and beyond.\n          <\/jats:p>","DOI":"10.1145\/3658665","type":"journal-article","created":{"date-parts":[[2024,4,22]],"date-time":"2024-04-22T10:53:45Z","timestamp":1713783225000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Verifiable Quantum Advantage without Structure"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1712-3026","authenticated-orcid":false,"given":"Takashi","family":"Yamakawa","sequence":"first","affiliation":[{"name":"Social Informatics Laboratories, Nippon Telegraph and Telephone Corporation, Musashino-shi, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7071-6272","authenticated-orcid":false,"given":"Mark","family":"Zhandry","sequence":"additional","affiliation":[{"name":"NTT Research Inc, Sunnyvale, United States"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"133","DOI":"10.4086\/toc.2014.v010a006","article-title":"The need for structure in quantum speedups","volume":"10","author":"Aaronson Scott","year":"2014","unstructured":"Scott Aaronson and Andris Ambainis. 2014. The need for structure in quantum speedups. Theory of Computing 10 (2014), 133\u2013166.","journal-title":"Theory of Computing"},{"key":"e_1_3_2_3_2","first-page":"333","volume-title":"Proceedings of the 43rd ACM STOC","author":"Aaronson Scott","year":"2011","unstructured":"Scott Aaronson and Alex Arkhipov. 2011. The computational complexity of linear optics. In Proceedings of the 43rd ACM STOC, Lance Fortnow and Salil P. Vadhan (Eds.). ACM Press, 333\u2013342. DOI:DOI:10.1145\/1993636.1993682"},{"issue":"4","key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1145\/1008731.1008735","article-title":"Quantum lower bounds for the collision and the element distinctness problems","volume":"51","author":"Aaronson Scott","year":"2004","unstructured":"Scott Aaronson and Yaoyun Shi. 2004. Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM 51, 4 (2004), 595\u2013605.","journal-title":"Journal of the ACM"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1109\/SFCS.1979.2","volume-title":"Proceedings of the 20th Annual Symposium on Foundations of Computer Science (sfcs 1979)","author":"Adleman Leonard","year":"1979","unstructured":"Leonard Adleman. 1979. A subexponential algorithm for the discrete logarithm problem with applications to cryptography. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science (sfcs 1979). 55\u201360. DOI:DOI:10.1109\/SFCS.1979.2"},{"key":"e_1_3_2_6_2","first-page":"474","volume-title":"Proceedings of the 55th FOCS","author":"Ambainis Andris","year":"2014","unstructured":"Andris Ambainis, Ansis Rosmanis, and Dominique Unruh. 2014. Quantum attacks on classical proof systems: The hardness of quantum rewinding. In Proceedings of the 55th FOCS. IEEE Computer Society Press, 474\u2013483. DOI:DOI:10.1109\/FOCS.2014.57"},{"key":"e_1_3_2_7_2","first-page":"255","volume-title":"Proceedings of the 52nd ACM STOC","author":"Amos Ryan","year":"2020","unstructured":"Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry. 2020. One-shot signatures and applications to hybrid quantum\/classical authentication. In Proceedings of the 52nd ACM STOC, Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy (Eds.). ACM Press, 255\u2013268. DOI:DOI:10.1145\/3357713.3384304"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","unstructured":"Atul Singh Arora Andrea Coladangelo Matthew Coudron Alexandru Gheorghiu Uttam Singh and Hendrik Waldner. 2022. Quantum depth in the random oracle model. In Proceedings of the 55th ACM STOC. ACM Press 1111\u20131124. DOI:10.1145\/3564246.3585153","DOI":"10.1145\/3564246.3585153"},{"key":"e_1_3_2_9_2","series-title":"LNCS","first-page":"165","volume-title":"Proceedings of the CRYPTO 2022, Part II","volume":"13508","author":"Austrin Per","year":"2022","unstructured":"Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, Yao-Ting Lin, and Mohammad Mahmoody. 2022. On the impossibility of key agreements from quantum random oracles. In Proceedings of the CRYPTO 2022, Part II(LNCS, Vol. 13508), Yevgeniy Dodis and Thomas Shrimpton (Eds.). Springer, Heidelberg, 165\u2013194. DOI:DOI:10.1007\/978-3-031-15979-4_6"},{"key":"e_1_3_2_10_2","first-page":"55","volume-title":"Proceedings of the 41st ACM STOC","author":"Babai L\u00e1szl\u00f3","year":"2009","unstructured":"L\u00e1szl\u00f3 Babai, Robert Beals, and \u00c1kos Seress. 2009. Polynomial-time theory of matrix groups. In Proceedings of the 41st ACM STOC, Michael Mitzenmacher (Ed.). ACM Press, 55\u201364. DOI:DOI:10.1145\/1536414.1536425"},{"issue":"4","key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"778","DOI":"10.1145\/502090.502097","article-title":"Quantum lower bounds by polynomials","volume":"48","author":"Beals Robert","year":"2001","unstructured":"Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. 2001. Quantum lower bounds by polynomials. Journal of the ACM 48, 4 (2001), 778\u2013797.","journal-title":"Journal of the ACM"},{"key":"e_1_3_2_12_2","first-page":"352","volume-title":"Proceedings of the 39th FOCS","author":"Beals Robert","year":"1998","unstructured":"Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. 1998. Quantum lower bounds by polynomials. In Proceedings of the 39th FOCS. IEEE Computer Society Press, 352\u2013361. DOI:DOI:10.1109\/SFCS.1998.743485"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1145\/168588.168596","volume-title":"Proceedings of the ACM CCS 93","author":"Bellare Mihir","year":"1993","unstructured":"Mihir Bellare and Phillip Rogaway. 1993. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the ACM CCS 93, Dorothy E. Denning, Raymond Pyle, Ravi Ganesan, Ravi S. Sandhu, and Victoria Ashby (Eds.). ACM Press, 62\u201373. DOI:DOI:10.1145\/168588.168596"},{"issue":"5","key":"e_1_3_2_14_2","doi-asserted-by":"crossref","first-page":"1510","DOI":"10.1137\/S0097539796300933","article-title":"Strengths and weaknesses of quantum computing","volume":"26","author":"Bennett Charles H.","year":"1997","unstructured":"Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh V. Vazirani. 1997. Strengths and weaknesses of quantum computing. SIAM Journal of the Computing 26, 5 (1997), 1510\u20131523.","journal-title":"SIAM Journal of the Computing"},{"key":"e_1_3_2_15_2","first-page":"11","volume-title":"Proceedings of the 25th ACM STOC","author":"Bernstein Ethan","year":"1993","unstructured":"Ethan Bernstein and Umesh V. Vazirani. 1993. Quantum complexity theory. In Proceedings of the 25th ACM STOC. ACM Press, 11\u201320. DOI:DOI:10.1145\/167088.167097"},{"key":"e_1_3_2_16_2","first-page":"671","volume-title":"Proceedings of the 50th ACM STOC","author":"Bitansky Nir","year":"2018","unstructured":"Nir Bitansky, Yael Tauman Kalai, and Omer Paneth. 2018. Multi-collision resistance: A paradigm for keyless hash functions. In Proceedings of the 50th ACM STOC, Ilias Diakonikolas, David Kempe, and Monika Henzinger (Eds.). ACM Press, 671\u2013684. DOI:DOI:10.1145\/3188745.3188870"},{"key":"e_1_3_2_17_2","series-title":"LNCS","first-page":"41","volume-title":"Proceedings of the ASIACRYPT 2011","volume":"7073","author":"Boneh Dan","year":"2011","unstructured":"Dan Boneh, \u00d6zg\u00fcr Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. 2011. Random oracles in a quantum world. In Proceedings of the ASIACRYPT 2011(LNCS, Vol. 7073), Dong Hoon Lee and Xiaoyun Wang (Eds.). Springer, Heidelberg, 41\u201369. DOI:DOI:10.1007\/978-3-642-25385-0_3"},{"key":"e_1_3_2_18_2","first-page":"320","volume-title":"Proceedings of the 59th FOCS","author":"Brakerski Zvika","year":"2018","unstructured":"Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh V. Vazirani, and Thomas Vidick. 2018. A cryptographic test of quantumness and certifiable randomness from a single quantum device. In Proceedings of the 59th FOCS, Mikkel Thorup (Ed.). IEEE Computer Society Press, 320\u2013331. DOI:DOI:10.1109\/FOCS.2018.00038"},{"key":"e_1_3_2_19_2","series-title":"LIPIcs","first-page":"8:1\u20138:14","volume-title":"Proceedings of the TQC 2020","volume":"158","author":"Brakerski Zvika","year":"2020","unstructured":"Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, and Thomas Vidick. 2020. Simpler proofs of quantumness. In Proceedings of the TQC 2020(LIPIcs, Vol. 158). 8:1\u20138:14."},{"key":"e_1_3_2_20_2","article-title":"Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy","author":"Bremner Michael J.","year":"2010","unstructured":"Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. 2010. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 2126 (2010), 459\u2013472.","journal-title":"Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"e_1_3_2_22_2","first-page":"209","volume-title":"Proceedings of the 30th ACM STOC","author":"Canetti Ran","year":"1998","unstructured":"Ran Canetti, Oded Goldreich, and Shai Halevi. 1998. The random oracle methodology, revisited (preliminary version). In Proceedings of the 30th ACM STOC. ACM Press, 209\u2013218. DOI:DOI:10.1145\/276698.276741"},{"key":"e_1_3_2_23_2","series-title":"LNCS","first-page":"181","volume-title":"Proceedings of the TCC 2020, Part III","volume":"12552","author":"Chia Nai-Hui","year":"2020","unstructured":"Nai-Hui Chia, Kai-Min Chung, and Takashi Yamakawa. 2020. Classical verification of quantum computations with efficient verifier. In Proceedings of the TCC 2020, Part III(LNCS, Vol. 12552), Rafael Pass and Krzysztof Pietrzak (Eds.). Springer, Heidelberg, 181\u2013206. DOI:DOI:10.1007\/978-3-030-64381-2_7"},{"key":"e_1_3_2_24_2","series-title":"LNCS","first-page":"1","volume-title":"Proceedings of the TCC 2019, Part II","volume":"11892","author":"Chiesa Alessandro","year":"2019","unstructured":"Alessandro Chiesa, Peter Manohar, and Nicholas Spooner. 2019. Succinct arguments in the quantum random oracle model. In Proceedings of the TCC 2019, Part II(LNCS, Vol. 11892), Dennis Hofheinz and Alon Rosen (Eds.). Springer, Heidelberg, 1\u201329. DOI:DOI:10.1007\/978-3-030-36033-7_1"},{"key":"e_1_3_2_25_2","first-page":"59","volume-title":"Proceedings of the 35th ACM STOC","author":"Childs Andrew M.","year":"2003","unstructured":"Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. 2003. Exponential algorithmic speedup by a quantum walk. In Proceedings of the 35th ACM STOC. ACM Press, 59\u201368. DOI:DOI:10.1145\/780542.780552"},{"issue":"5","key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1080\/00029890.1983.11971218","article-title":"Tricks or treats with the hilbert matrix","volume":"90","author":"Choi Man-Duen","year":"1983","unstructured":"Man-Duen Choi. 1983. Tricks or treats with the hilbert matrix. The American Mathematical Monthly 90, 5 (1983), 301\u2013312. Retrieved from http:\/\/www.jstor.org\/stable\/2975779","journal-title":"The American Mathematical Monthly"},{"key":"e_1_3_2_27_2","first-page":"673","volume-title":"Proceedings of the 61st FOCS","author":"Chung Kai-Min","year":"2020","unstructured":"Kai-Min Chung, Siyao Guo, Qipeng Liu, and Luowen Qian. 2020. Tight quantum time-space tradeoffs for function inversion. In Proceedings of the 61st FOCS. IEEE Computer Society Press, 673\u2013684. DOI:DOI:10.1109\/FOCS46700.2020.00068"},{"key":"e_1_3_2_28_2","series-title":"LNCS","first-page":"227","volume-title":"Proceedings of the EUROCRYPT 2018, Part I","volume":"10820","author":"Coretti Sandro","year":"2018","unstructured":"Sandro Coretti, Yevgeniy Dodis, Siyao Guo, and John P. Steinberger. 2018. Random oracles and non-uniformity. In Proceedings of the EUROCRYPT 2018, Part I(LNCS, Vol. 10820), Jesper Buus Nielsen and Vincent Rijmen (Eds.). Springer, Heidelberg, 227\u2013258. DOI:DOI:10.1007\/978-3-319-78381-9_9"},{"issue":"4","key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/s00453-002-0978-1","article-title":"Sharp quantum versus classical query complexity separations","volume":"34","author":"Beaudrap J. Niel de","year":"2002","unstructured":"J. Niel de Beaudrap, Richard Cleve, and John Watrous. 2002. Sharp quantum versus classical query complexity separations. Algorithmica 34, 4 (2002), 449\u2013461.","journal-title":"Algorithmica"},{"key":"e_1_3_2_30_2","series-title":"LNCS","first-page":"356","volume-title":"Proceedings of the CRYPTO 2019, Part II","volume":"11693","author":"Don Jelle","year":"2019","unstructured":"Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. 2019. Security of the fiat-shamir transformation in the quantum random-oracle model. In Proceedings of the CRYPTO 2019, Part II(LNCS, Vol. 11693), Alexandra Boldyreva and Daniele Micciancio (Eds.). Springer, Heidelberg, 356\u2013383. DOI:DOI:10.1007\/978-3-030-26951-7_13"},{"issue":"1","key":"e_1_3_2_31_2","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1109\/TIT.2007.911222","article-title":"Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy","volume":"54","author":"Guruswami Venkatesan","year":"2008","unstructured":"Venkatesan Guruswami and Atri Rudra. 2008. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on Information Theory 54, 1 (2008), 135\u2013150.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"6","key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"1757","DOI":"10.1109\/18.782097","article-title":"Improved decoding of reed-solomon and algebraic-geometry codes","volume":"45","author":"Guruswami Venkatesan","year":"1999","unstructured":"Venkatesan Guruswami and Madhu Sudan. 1999. Improved decoding of reed-solomon and algebraic-geometry codes. IEEE Transactions on Information Theory 45, 6 (1999), 1757\u20131767.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_3_2_33_2","series-title":"LNCS","first-page":"173","volume-title":"Proceedings of the CRYPTO 2015, Part II","volume":"9216","author":"Haitner Iftach","year":"2015","unstructured":"Iftach Haitner, Yuval Ishai, Eran Omri, and Ronen Shaltiel. 2015. Parallel hashing via list recoverability. In Proceedings of the CRYPTO 2015, Part II(LNCS, Vol. 9216), Rosario Gennaro and Matthew J. B. Robshaw (Eds.). Springer, Heidelberg, 173\u2013190. DOI:DOI:10.1007\/978-3-662-48000-7_9"},{"key":"e_1_3_2_34_2","first-page":"653","volume-title":"Proceedings of the 34th ACM STOC","author":"Hallgren Sean","year":"2002","unstructured":"Sean Hallgren. 2002. Polynomial-time quantum algorithms for Pell\u2019s equation and the principal ideal problem. In Proceedings of the 34th ACM STOC. ACM Press, 653\u2013658. DOI:DOI:10.1145\/509907.510001"},{"issue":"4","key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1137\/S0097539793244708","article-title":"A pseudorandom generator from any one-way function","volume":"28","author":"H\u00e5stad Johan","year":"1999","unstructured":"Johan H\u00e5stad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. 1999. A pseudorandom generator from any one-way function. SIAM Journal of the Computing 28, 4 (1999), 1364\u20131396.","journal-title":"SIAM Journal of the Computing"},{"key":"e_1_3_2_36_2","series-title":"LNCS","first-page":"584","volume-title":"Proceedings of the ASIACRYPT 2019, Part I","volume":"11921","author":"Hhan Minki","year":"2019","unstructured":"Minki Hhan, Keita Xagawa, and Takashi Yamakawa. 2019. Quantum random oracle model with auxiliary input. In Proceedings of the ASIACRYPT 2019, Part I(LNCS, Vol. 11921), Steven D. Galbraith and Shiho Moriai (Eds.). Springer, Heidelberg, 584\u2013614. DOI:DOI:10.1007\/978-3-030-34578-5_21"},{"key":"e_1_3_2_37_2","first-page":"750","volume-title":"Proceedings of the 53rd ACM STOC","author":"Holmgren Justin","year":"2021","unstructured":"Justin Holmgren, Alex Lombardi, and Ron D. Rothblum. 2021. Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge). In Proceedings of the 53rd ACM STOC, Samir Khuller and Virginia Vassilevska Williams (Eds.). ACM Press, 750\u2013760. DOI:DOI:10.1145\/3406325.3451116"},{"key":"e_1_3_2_38_2","first-page":"134","volume-title":"Proceedings of Structure in Complexity Theory. 10th Annual IEEE Conference","author":"Impagliazzo R.","year":"1995","unstructured":"R. Impagliazzo. 1995. A personal view of average-case complexity. In Proceedings of Structure in Complexity Theory. 10th Annual IEEE Conference. 134\u2013147. DOI:DOI:10.1109\/SCT.1995.514853"},{"key":"e_1_3_2_39_2","first-page":"44","volume-title":"Proceedings of the 21st ACM STOC","author":"Impagliazzo Russell","year":"1989","unstructured":"Russell Impagliazzo and Steven Rudich. 1989. Limits on the provable consequences of one-way permutations. In Proceedings of the 21st ACM STOC. ACM Press, 44\u201361. DOI:DOI:10.1145\/73007.73012"},{"key":"e_1_3_2_40_2","series-title":"LNCS","first-page":"253","volume-title":"Proceedings of the ASIACRYPT 2018, Part II","volume":"11273","author":"Katsumata Shuichi","year":"2018","unstructured":"Shuichi Katsumata, Shota Yamada, and Takashi Yamakawa. 2018. Tighter security proofs for GPV-IBE in the quantum random oracle model. In Proceedings of the ASIACRYPT 2018, Part II(LNCS, Vol. 11273), Thomas Peyrin and Steven Galbraith (Eds.). Springer, Heidelberg, 253\u2013282. DOI:DOI:10.1007\/978-3-030-03329-3_9"},{"key":"e_1_3_2_41_2","series-title":"LNCS","first-page":"552","volume-title":"Proceedings of the EUROCRYPT 2018, Part III","volume":"10822","author":"Kiltz Eike","year":"2018","unstructured":"Eike Kiltz, Vadim Lyubashevsky, and Christian Schaffner. 2018. A concrete treatment of fiat-shamir signatures in the quantum random-oracle model. In Proceedings of the EUROCRYPT 2018, Part III(LNCS, Vol. 10822), Jesper Buus Nielsen and Vincent Rijmen (Eds.). Springer, Heidelberg, 552\u2013586. DOI:DOI:10.1007\/978-3-319-78372-7_18"},{"key":"e_1_3_2_42_2","series-title":"LNCS","first-page":"162","volume-title":"Proceedings of the EUROCRYPT 2018, Part II","volume":"10821","author":"Komargodski Ilan","year":"2018","unstructured":"Ilan Komargodski, Moni Naor, and Eylon Yogev. 2018. Collision resistant hashing for paranoids: Dealing with multiple collisions. In Proceedings of the EUROCRYPT 2018, Part II(LNCS, Vol. 10821), Jesper Buus Nielsen and Vincent Rijmen (Eds.). Springer, Heidelberg, 162\u2013194. DOI:DOI:10.1007\/978-3-319-78375-8_6"},{"issue":"11","key":"e_1_3_2_43_2","doi-asserted-by":"crossref","first-page":"2975","DOI":"10.1109\/TIT.2003.819333","article-title":"Reed-solomon codes for correcting phased error bursts","volume":"49","author":"Krachkovsky Victor Yu.","year":"2003","unstructured":"Victor Yu. Krachkovsky. 2003. Reed-solomon codes for correcting phased error bursts. IEEE Transactions on Information Theory 49, 11 (2003), 2975\u20132984.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_3_2_44_2","series-title":"Encyclopedia of Mathematics and its Applications","volume-title":"Finite fields (2nd ed.)","author":"Lidl Rudolf","year":"1997","unstructured":"Rudolf Lidl and Harald Niederreiter. 1997. Finite fields (2nd ed.). Encyclopedia of Mathematics and its Applications, Vol. 20. Cambridge University Press, Cambridge."},{"key":"e_1_3_2_45_2","unstructured":"Yehuda Lindell. 2010. Introduction to Coding Theory Lecture Notes. Retrieved from https:\/\/u.cs.biu.ac.il\/lindell\/89-662\/coding_theory-lecture-notes.pdf"},{"key":"e_1_3_2_46_2","volume-title":"Proceedings of the EUROCRYPT 2023 (to appear)","author":"Liu Qipeng","year":"2023","unstructured":"Qipeng Liu. 2023. Non-uniformity, quantum advice in the quantum random oracle model. In Proceedings of the EUROCRYPT 2023 (to appear)."},{"key":"e_1_3_2_47_2","series-title":"LNCS","first-page":"326","volume-title":"Proceedings of the CRYPTO 2019, Part II","volume":"11693","author":"Liu Qipeng","year":"2019","unstructured":"Qipeng Liu and Mark Zhandry. 2019. Revisiting post-quantum fiat-shamir. In Proceedings of the CRYPTO 2019, Part II(LNCS, Vol. 11693), Alexandra Boldyreva and Daniele Micciancio (Eds.). Springer, Heidelberg, 326\u2013355. DOI:DOI:10.1007\/978-3-030-26951-7_12"},{"key":"e_1_3_2_48_2","first-page":"746","volume-title":"Proceedings of the 19th SODA","author":"Mitzenmacher Michael","year":"2008","unstructured":"Michael Mitzenmacher and Salil P. Vadhan. 2008. Why simple hash functions work: Exploiting the entropy in a data stream. In Proceedings of the 19th SODA, Shang-Teng Huang (Ed.). ACM-SIAM, 746\u2013755."},{"key":"e_1_3_2_49_2","article-title":"Proofs of Quantumness from Trapdoor Permutations","author":"Morimae Tomoyuki","year":"2022","unstructured":"Tomoyuki Morimae and Takashi Yamakawa. 2022. Proofs of Quantumness from Trapdoor Permutations. Cryptology ePrint Archive, Report 2022\/1102. Retrieved from https:\/\/eprint.iacr.org\/2022\/1102","journal-title":"Cryptology ePrint Archive, Report 2022\/1102"},{"key":"e_1_3_2_50_2","article-title":"A Public Key Cryptosystem Based On Pell Equation","author":"Padhye Sahadeo","year":"2006","unstructured":"Sahadeo Padhye. 2006. A Public Key Cryptosystem Based On Pell Equation. Cryptology ePrint Archive, Report 2006\/191. Retrieved from https:\/\/eprint.iacr.org\/2006\/191","journal-title":"Cryptology ePrint Archive, Report 2006\/191"},{"key":"e_1_3_2_51_2","first-page":"84","volume-title":"Proceedings of the 37th ACM STOC","author":"Regev Oded","year":"2005","unstructured":"Oded Regev. 2005. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the 37th ACM STOC, Harold N. Gabow and Ronald Fagin (Eds.). ACM Press, 84\u201393. DOI:DOI:10.1145\/1060590.1060603"},{"key":"e_1_3_2_52_2","volume-title":"List Decoding and Property Testing of Error Correcting Codes","author":"Rudra Atri","year":"2007","unstructured":"Atri Rudra. 2007. List Decoding and Property Testing of Error Correcting Codes. Ph. D. Dissertation. University of Washington."},{"key":"e_1_3_2_53_2","series-title":"LNCS","first-page":"520","volume-title":"Proceedings of the EUROCRYPT 2018, Part III","volume":"10822","author":"Saito Tsunekazu","year":"2018","unstructured":"Tsunekazu Saito, Keita Xagawa, and Takashi Yamakawa. 2018. Tightly-secure key-encapsulation mechanism in the quantum random oracle model. In Proceedings of the EUROCRYPT 2018, Part III(LNCS, Vol. 10822), Jesper Buus Nielsen and Vincent Rijmen (Eds.). Springer, Heidelberg, 520\u2013551. DOI:DOI:10.1007\/978-3-319-78372-7_17"},{"key":"e_1_3_2_54_2","first-page":"124","volume-title":"Proceedings of the 35th FOCS","author":"Shor Peter W.","year":"1994","unstructured":"Peter W. Shor. 1994. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th FOCS. IEEE Computer Society Press, 124\u2013134. DOI:DOI:10.1109\/SFCS.1994.365700"},{"issue":"5","key":"e_1_3_2_55_2","doi-asserted-by":"crossref","first-page":"1474","DOI":"10.1137\/S0097539796298637","article-title":"On the power of quantum computation","volume":"26","author":"Simon Daniel R.","year":"1997","unstructured":"Daniel R. Simon. 1997. On the power of quantum computation. SIAM Journal of the Computing 26, 5 (October 1997), 1474\u20131483.","journal-title":"SIAM Journal of the Computing"},{"key":"e_1_3_2_56_2","series-title":"LNCS","first-page":"192","volume-title":"Proceedings of the TCC 2016-B, Part II","volume":"9986","author":"Targhi Ehsan Ebrahimi","year":"2016","unstructured":"Ehsan Ebrahimi Targhi and Dominique Unruh. 2016. Post-quantum security of the fujisaki-okamoto and OAEP transforms. In Proceedings of the TCC 2016-B, Part II(LNCS, Vol. 9986), Martin Hirt and Adam D. Smith (Eds.). Springer, Heidelberg, 192\u2013216. DOI:DOI:10.1007\/978-3-662-53644-5_8"},{"key":"e_1_3_2_57_2","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/978-3-540-74143-5_12","volume-title":"Proceedings of the CRYPTO 2007","volume":"4622","author":"Unruh Dominique","year":"2007","unstructured":"Dominique Unruh. 2007. Random oracles and auxiliary input. In Proceedings of the CRYPTO 2007(LNCS, Vol. 4622), Alfred Menezes (Ed.). Springer, Heidelberg, 205\u2013223. DOI:DOI:10.1007\/978-3-540-74143-5_12"},{"issue":"3","key":"e_1_3_2_58_2","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S009753970343141X","article-title":"Quantum algorithms for some hidden shift problems","volume":"36","author":"Dam Wim van","year":"2006","unstructured":"Wim van Dam, Sean Hallgren, and Lawrence Ip. 2006. Quantum algorithms for some hidden shift problems. SIAM Journal of the Computing 36, 3 (2006), 763\u2013778.","journal-title":"SIAM Journal of the Computing"},{"key":"e_1_3_2_59_2","series-title":"LNCS","first-page":"568","volume-title":"Proceedings of the EUROCRYPT 2021, Part II","volume":"12697","author":"Yamakawa Takashi","year":"2021","unstructured":"Takashi Yamakawa and Mark Zhandry. 2021. Classical vs quantum random oracles. In Proceedings of the EUROCRYPT 2021, Part II(LNCS, Vol. 12697), Anne Canteaut and Fran\u00e7ois-Xavier Standaert (Eds.). Springer, Heidelberg, 568\u2013597. DOI:DOI:10.1007\/978-3-030-77886-6_20"},{"issue":"13","key":"e_1_3_2_60_2","doi-asserted-by":"crossref","first-page":"1089","DOI":"10.26421\/QIC14.13-14-2","article-title":"A quantum lower bound for distinguishing random functions from random permutations","volume":"14","author":"Yuen Henry","year":"2014","unstructured":"Henry Yuen. 2014. A quantum lower bound for distinguishing random functions from random permutations. Quantum Information & Computation 14, 13\u201314 (oct 2014), 1089\u20131097.","journal-title":"Quantum Information & Computation"},{"key":"e_1_3_2_61_2","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1007\/978-3-642-32009-5_44","volume-title":"Proceedings of the CRYPTO 2012","volume":"7417","author":"Zhandry Mark","year":"2012","unstructured":"Mark Zhandry. 2012. Secure identity-based encryption in the quantum random oracle model. In Proceedings of the CRYPTO 2012(LNCS, Vol. 7417), Reihaneh Safavi-Naini and Ran Canetti (Eds.). Springer, Heidelberg, 758\u2013775. DOI:DOI:10.1007\/978-3-642-32009-5_44"},{"issue":"7","key":"e_1_3_2_62_2","doi-asserted-by":"crossref","first-page":"557","DOI":"10.26421\/QIC15.7-8-2","article-title":"A note on the quantum collision and set equality problems","volume":"15","author":"Zhandry Mark","year":"2015","unstructured":"Mark Zhandry. 2015. A note on the quantum collision and set equality problems. Quantum Information & Computation 15, 7\u20138 (May 2015), 557\u2013567.","journal-title":"Quantum Information & Computation"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658665","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3658665","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:44:13Z","timestamp":1750290253000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658665"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,11]]},"references-count":61,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3658665"],"URL":"https:\/\/doi.org\/10.1145\/3658665","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,11]]},"assertion":[{"value":"2023-02-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-09","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}