How to construct quantum random functions

Mark Zhandry

Research output: Contribution to journalConference articlepeer-review

136 Scopus citations


In the presence of a quantum adversary, there are two possible definitions of security for a pseudorandom function. The first, which we call standard-security, allows the adversary to be quantum, but requires queries to the function to be classical. The second, quantum-security, allows the adversary to query the function on a quantum superposition of inputs, thereby giving the adversary a superposition of the values of the function at many inputs at once. Existing techniques for proving the security of pseudorandom functions fail when the adversary can make quantum queries. We give the first quantum-security proofs for pseudorandom functions by showing that some classical constructions of pseudorandom functions are quantum-secure. Namely, we show that the standard constructions of pseudorandom functions from pseudorandom generators or pseudorandom synthesizers are secure, even when the adversary can make quantum queries. We also show that a direct construction from lattices is quantum-secure. To prove security, we develop new tools to prove the indistinguishability of distributions under quantum queries. In light of these positive results, one might hope that all standard-secure pseudorandom functions are quantum-secure. To the contrary, we show a separation: under the assumption that standard-secure pseudorandom functions exist, there are pseudorandom functions secure against quantum adversaries making classical queries, but insecure once the adversary can make quantum queries.

Original languageEnglish (US)
Article number6375347
Pages (from-to)679-687
Number of pages9
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
StatePublished - Dec 1 2012
Externally publishedYes
Event53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 - New Brunswick, NJ, United States
Duration: Oct 20 2012Oct 23 2012

All Science Journal Classification (ASJC) codes

  • Computer Science(all)


  • Pseudorandom Function
  • Quantum

Cite this