{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T04:25:06Z","timestamp":1769574306045,"version":"3.49.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T00:00:00Z","timestamp":1628726400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF"},{"DOI":"10.13039\/100000185","name":"DARPA","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            <jats:bold>Pseudorandom functions<\/jats:bold>\n            (\n            <jats:bold>PRFs<\/jats:bold>\n            ) are one of the foundational concepts in theoretical computer science, with numerous applications in complexity theory and cryptography. In this work, we study the security of PRFs when evaluated on quantum superpositions of inputs. The classical techniques for arguing the security of PRFs do not carry over to this setting, even if the underlying building blocks are quantum resistant. We therefore develop a new proof technique to show that many of the classical PRF constructions remain secure when evaluated on superpositions.\n          <\/jats:p>","DOI":"10.1145\/3450745","type":"journal-article","created":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T19:06:46Z","timestamp":1628795206000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["How to Construct Quantum Random Functions"],"prefix":"10.1145","volume":"68","author":[{"given":"Mark","family":"Zhandry","sequence":"first","affiliation":[{"name":"Stanford University, Sunnyvale, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,8,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.42"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213983"},{"key":"e_1_2_1_3_1","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology (EUROCRYPT\u201920), Part III","author":"Alagic Gorjan","unstructured":"Gorjan Alagic , Christian Majenz , Alexander Russell , and Fang Song . 2020. Quantum-access-secure message authentication via blind-unforgeability . In Advances in Cryptology (EUROCRYPT\u201920), Part III , Lecture Notes in Computer Science , Vol. 12107 , Anne Canteaut and Yuval Ishai (Eds.). Springer , Heidelberg, Germany, 788\u2013817. DOI:https:\/\/doi.org\/10.1007\/978-3-030-45727-3_27 10.1007\/978-3-030-45727-3_27 Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song. 2020. Quantum-access-secure message authentication via blind-unforgeability. In Advances in Cryptology (EUROCRYPT\u201920), Part III, Lecture Notes in Computer Science, Vol. 12107, Anne Canteaut and Yuval Ishai (Eds.). Springer, Heidelberg, Germany, 788\u2013817. DOI:https:\/\/doi.org\/10.1007\/978-3-030-45727-3_27"},{"key":"e_1_2_1_4_1","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology (EUROCRYPT\u201917), Part III","author":"Alagic Gorjan","unstructured":"Gorjan Alagic and Alexander Russell . 2017. Quantum-secure symmetric-key cryptography based on hidden shifts . In Advances in Cryptology (EUROCRYPT\u201917), Part III , Lecture Notes in Computer Science , Vol. 10212 , Jean-S\u00e9bastien Coron and Jesper Buus Nielsen (Eds.). Springer , Heidelberg, Germany, 65\u201393. DOI:https:\/\/doi.org\/10.1007\/978-3-319-56617-7_3 10.1007\/978-3-319-56617-7_3 Gorjan Alagic and Alexander Russell. 2017. Quantum-secure symmetric-key cryptography based on hidden shifts. In Advances in Cryptology (EUROCRYPT\u201917), Part III, Lecture Notes in Computer Science, Vol. 10212, Jean-S\u00e9bastien Coron and Jesper Buus Nielsen (Eds.). Springer, Heidelberg, Germany, 65\u201393. DOI:https:\/\/doi.org\/10.1007\/978-3-319-56617-7_3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.57"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1098650"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25385-0_3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/261342.261346"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.30"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/646760.706007"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1866307.1866323"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/648184.749735"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_42"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-36030-6_10"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.12"},{"key":"e_1_2_1_17_1","volume-title":"Advances in Cryptology (EUROCRYPT\u201913)Lecture Notes in Computer Science","author":"Boneh Dan","unstructured":"Dan Boneh and Mark Zhandry . 2013. Quantum-secure message authentication codes . In Advances in Cryptology (EUROCRYPT\u201913)Lecture Notes in Computer Science , Vol. 7881 , Thomas Johansson and Phong Q. Nguyen (Eds.). Springer , Heidelberg, Germany, 592\u2013608. DOI:https:\/\/doi.org\/10.1007\/978-3-642-38348-9_35 10.1007\/978-3-642-38348-9_35 Dan Boneh and Mark Zhandry. 2013. Quantum-secure message authentication codes. In Advances in Cryptology (EUROCRYPT\u201913)Lecture Notes in Computer Science, Vol. 7881, Thomas Johansson and Phong Q. Nguyen (Eds.). Springer, Heidelberg, Germany, 592\u2013608. DOI:https:\/\/doi.org\/10.1007\/978-3-642-38348-9_35"},{"key":"e_1_2_1_18_1","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology (CRYPTO\u201913), Part II","author":"Boneh Dan","unstructured":"Dan Boneh and Mark Zhandry . 2013. Secure signatures and chosen ciphertext security in a quantum computing world . In Advances in Cryptology (CRYPTO\u201913), Part II , Lecture Notes in Computer Science , Vol. 8043 , Ran Canetti and Juan A. Garay (Eds.). Springer , Heidelberg, Germany, 361\u2013379. DOI:https:\/\/doi.org\/10.1007\/978-3-642-40084-1_21 10.1007\/978-3-642-40084-1_21 Dan Boneh and Mark Zhandry. 2013. Secure signatures and chosen ciphertext security in a quantum computing world. In Advances in Cryptology (CRYPTO\u201913), Part II, Lecture Notes in Computer Science, Vol. 8043, Ran Canetti and Juan A. Garay (Eds.). Springer, Heidelberg, Germany, 361\u2013379. DOI:https:\/\/doi.org\/10.1007\/978-3-642-40084-1_21"},{"key":"e_1_2_1_19_1","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology (CRYPTO\u201919), Part II","author":"Czajkowski Jan","unstructured":"Jan Czajkowski , Andreas H\u00fclsing , and Christian Schaffner . 2019. Quantum indistinguishability of random sponges . In Advances in Cryptology (CRYPTO\u201919), Part II , Lecture Notes in Computer Science , Vol. 11693 , Alexandra Boldyreva and Daniele Micciancio (Eds.). Springer , Heidelberg, Germany, 296\u2013325. DOI:https:\/\/doi.org\/10.1007\/978-3-030-26951-7_11 10.1007\/978-3-030-26951-7_11 Jan Czajkowski, Andreas H\u00fclsing, and Christian Schaffner. 2019. Quantum indistinguishability of random sponges. In Advances in Cryptology (CRYPTO\u201919), Part II, Lecture Notes in Computer Science, Vol. 11693, Alexandra Boldyreva and Daniele Micciancio (Eds.). Springer, Heidelberg, Germany, 296\u2013325. DOI:https:\/\/doi.org\/10.1007\/978-3-030-26951-7_11"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04268-8_9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715949"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53015-3_3"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488678"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.62"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_28_1","volume-title":"Advances in Cryptology (ASIACRYPT\u201919), Part ILecture Notes in Computer Science","author":"Hosoyamada Akinori","unstructured":"Akinori Hosoyamada and Tetsu Iwata . 2019. 4-round Luby-Rackoff construction is a qPRP . In Advances in Cryptology (ASIACRYPT\u201919), Part ILecture Notes in Computer Science , Vol. 11921 , Steven D. Galbraith and Shiho Moriai (Eds.). Springer , Heidelberg, Germany, 145\u2013174. DOI:https:\/\/doi.org\/10.1007\/978-3-030-34578-5_6 10.1007\/978-3-030-34578-5_6 Akinori Hosoyamada and Tetsu Iwata. 2019. 4-round Luby-Rackoff construction is a qPRP. In Advances in Cryptology (ASIACRYPT\u201919), Part ILecture Notes in Computer Science, Vol. 11921, Steven D. Galbraith and Shiho Moriai (Eds.). Springer, Heidelberg, Germany, 145\u2013174. DOI:https:\/\/doi.org\/10.1007\/978-3-030-34578-5_6"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_2_1_30_1","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology (CRYPTO\u201918), Part III","author":"Ji Zhengfeng","unstructured":"Zhengfeng Ji , Yi-Kai Liu , and Fang Song . 2018. Pseudorandom quantum states . In Advances in Cryptology (CRYPTO\u201918), Part III , Lecture Notes in Computer Science , Vol. 10993 , Hovav Shacham and Alexandra Boldyreva (Eds.). Springer , Heidelberg, Germany, 126\u2013152. DOI:https:\/\/doi.org\/10.1007\/978-3-319-96878-0_5 10.1007\/978-3-319-96878-0_5 Zhengfeng Ji, Yi-Kai Liu, and Fang Song. 2018. Pseudorandom quantum states. In Advances in Cryptology (CRYPTO\u201918), Part III, Lecture Notes in Computer Science, Vol. 10993, Hovav Shacham and Alexandra Boldyreva (Eds.). Springer, Heidelberg, Germany, 126\u2013152. DOI:https:\/\/doi.org\/10.1007\/978-3-319-96878-0_5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2700550"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653662.1653677"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1119\/1.1463744"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796316"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796378"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335307"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195134"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/10719994"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/645728.667682"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.61"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5_44"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/2871411.2871413"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450745","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450745","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450745","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:42Z","timestamp":1750195722000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450745"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,12]]},"references-count":44,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3450745"],"URL":"https:\/\/doi.org\/10.1145\/3450745","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,12]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}