Pseudorandomness: From Quantum States to Binary Strings

Prabhanjan Ananth (UC Santa Barbara)
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.