@article{9589005074bb4776a96a49d2e5c6c39e,
title = "How to Construct Quantum Random Functions",
abstract = "Pseudorandom functions (PRFs) 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. ",
keywords = "Quantum, pseudorandom function, security proofs",
author = "Mark Zhandry",
note = "Funding Information: This work was supported by NSF and DARPA. Author{\textquoteright}s address: M. Zhandry, 940 Stewart Drive, Sunnyvale, CA 94085; email: mzhandry@gmail.com. Authors current address: Princeton University and NTT Research. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. {\textcopyright} 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM. 0004-5411/2021/08-ART33 $15.00 https://doi.org/10.1145/3450745 Publisher Copyright: {\textcopyright} 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM.",
year = "2021",
month = oct,
doi = "10.1145/3450745",
language = "English (US)",
volume = "68",
journal = "Journal of the ACM",
issn = "0004-5411",
publisher = "Association for Computing Machinery (ACM)",
number = "5",
}