How to Construct Quantum Random Functions

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Article number33
JournalJournal of the ACM
Volume68
Issue number5
DOIs
StatePublished - Oct 2021

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Quantum
  • pseudorandom function
  • security proofs

Fingerprint

Dive into the research topics of 'How to Construct Quantum Random Functions'. Together they form a unique fingerprint.

Cite this