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.

Original language	English (US)
Article number	33
Journal	Journal of the ACM
Volume	68
Issue number	5
DOIs	https://doi.org/10.1145/3450745
State	Published - 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

Cite this

@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",

}

TY - JOUR

T1 - How to Construct Quantum Random Functions

AU - Zhandry, Mark

N1 - Funding Information: This work was supported by NSF and DARPA. Author’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. © 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: © 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM.

PY - 2021/10

Y1 - 2021/10

N2 - 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.

AB - 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.

KW - Quantum

KW - pseudorandom function

KW - security proofs

UR - http://www.scopus.com/inward/record.url?scp=85121118083&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85121118083&partnerID=8YFLogxK

U2 - 10.1145/3450745

DO - 10.1145/3450745

M3 - Article

AN - SCOPUS:85121118083

VL - 68

JO - Journal of the ACM

JF - Journal of the ACM

SN - 0004-5411

IS - 5

M1 - 33

ER -

How to Construct Quantum Random Functions

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Other files and links

Fingerprint

Cite this