Pseudorandomness: From Quantum States to Binary Strings

Prabhanjan Ananth (UC Santa Barbara) https://simons.berkeley.edu/talks/prabhanjan-ananth-uc-santa-barbara-2023-06-20 Minimum Quantum Assumptions for Cryptography Workshop Pseudorandom generators (PRGs) are widely studied in theoretical computer science and in particular, cryptography. It is well-known in classical cryptography that one-way functions are a necessary assumption for the existence of PRGs. In joint work with Yao-Ting Lin (UCSB) and Henry Yuen (Columbia), we consider a variant of PRGs called quantum PRGs (QPRGs). Quantum PRGs are like PRGs except that (a) they are allowed to have a small determinism error and, (b) the generation is allowed to be a polynomial-time quantum algorithm. We explore the possibility of basing QPRGs on assumptions weaker than one-way functions. We show that QPRGs can be based on the existence of logarithmic-output pseudorandom quantum states, introduced by Ji, Liu, and Song. Our main contribution is to design a (pseudo)-deterministic extractor that can extract uniformly random strings (up to some small error) given Haar-random states. We explore cryptographic applications and variants of QPRGs.