Pseudorandom Strings from Pseudorandom Quantum States

Prabhanjan Ananth; Yao-Ting Lin; Henry Yuen

Paper 2023/904

Pseudorandom Strings from Pseudorandom Quantum States

Prabhanjan Ananth, University of California, Santa Barbara

Yao-Ting Lin, University of California, Santa Barbara

Henry Yuen, Columbia University

Abstract

We study the relationship between notions of pseudorandomness in the quantum and classical worlds. Pseudorandom quantum state generator (PRSG), a pseudorandomness notion in the quantum world, is an efficient circuit that produces states that are computationally indistinguishable from Haar random states. PRSGs have found applications in quantum gravity, quantum machine learning, quantum complexity theory, and quantum cryptography. Pseudorandom generators, on the other hand, a pseudorandomness notion in the classical world, is ubiquitous to theoretical computer science. While some separation results were known between PRSGs, for some parameter regimes, and PRGs, their relationship has not been completely understood. In this work, we show that a natural variant of pseudorandom generators called quantum pseudorandom generators (QPRGs) can be based on the existence of logarithmic output length PRSGs. Our result along with the previous separations gives a better picture regarding the relationship between the two notions. We also study the relationship between other notions, namely, pseudorandom function-like state generators and pseudorandom functions. We provide evidence that QPRGs can be as useful as PRGs by providing cryptographic applications of QPRGs such as commitments and encryption schemes. Our primary technical contribution is a method for pseudodeterministically extracting uniformly random strings from Haar-random states.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: quantum cryptography
Contact author(s): prabhanjan @ cs ucsb edu
yao-ting_lin @ ucsb edu
hyuen @ cs columbia edu
History: 2023-09-13: revised; 2023-06-10: received; See all versions
Short URL: https://ia.cr/2023/904
License: CC BY

BibTeX

@misc{cryptoeprint:2023/904,
      author = {Prabhanjan Ananth and Yao-Ting Lin and Henry Yuen},
      title = {Pseudorandom Strings from Pseudorandom Quantum States},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/904},
      year = {2023},
      url = {https://eprint.iacr.org/2023/904}
}