How (not) to Build Quantum PKE in Minicrypt

The seminal work by Impagliazzo and Rudich (STOC’89) demonstrated the impossibility of constructing classical public key encryption (PKE) from one-way functions (OWF) in a black-box manner. Quantum information has the potential to bypass classical limitations, enabling the realization of seemingly impossible tasks such as quantum money, copy protection for software, and commitment without one-way functions. However, the question remains: can quantum PKE (QPKE) be constructed from quantumly secure OWF? A recent line of work has shown that it is indeed possible to build QPKE from OWF, but with one caveat. These constructions necessitate public keys being quantum and unclonable, diminishing the practicality of such “public” encryption schemes—public keys cannot be authenticated and reused. In this work, we re-examine the possibility of perfect complete QPKE in the quantum random oracle model (QROM), where OWF exists. Therefore, a necessary condition for constructing such QPKE from OWF is to have the key generation classically “un-simulatable”. Previous results (Austrin et al. CRYPTO’22) on the impossibility of QPKE from OWF rely on a seemingly strong conjecture. Our work makes a significant step towards a complete and unconditional quantization of Impagliazzo and Rudich’s results. Our second main result extends to QPKE with quantum public keys. The result is tight due to these existing QPKEs with quantum public keys, classical secret keys, quantum/classical ciphertext and classical-query key generation require the public key to be mixed instead of pure; or require quantum-query key generation, if the public key is pure. Our result further gives evidence on why existing QPKEs lose reusability. We also explore other sufficient/necessary conditions to build QPKE from OWF. Along the way, we use a new argument based on conditional mutual information and Markov chain to reprove the classical result; leveraging the analog of quantum conditional mutual information and quantum Markov chain by Fawzi and Renner (Communications in Mathematical Physics), we extend it to the quantum case and prove all our results. We believe the techniques used in the work will find many other usefulness in separations in quantum cryptography/complexity.