On the Feasibility of Simulation-Secure Quantum Functional Encryption

Abstract

Functional encryption is a powerful cryptographic primitive that enables fine-grained access to encrypted data and underlies numerous applications. Although the ideal security notion for FE, simulation security, has been shown to be impossible in the plain classical setting, those impossibility results rely on inherently classical arguments. This raises a fundamental question: can simulation-secure FE be realized in the quantum regime or in alternative models? We resolve both directions of this question. On the negative side, we show that the classical impossibility results largely extend to the quantum setting. When the adversary can submit an unbounded number of challenge messages, we establish an unconditional impossibility, matching the classical barrier. In the case where the adversary may obtain many functional keys, classical arguments only yield impossibility under the assumption of pseudorandom functions; we strengthen this by proving impossibility under the potentially weaker assumption of pseudorandom quantum states. We additionally give an independent impossibility based solely on public-key encryption with classical public-keys. Since public-key encryption is not known to imply pseudorandom states, this yields complementary evidence of the barrier and, in particular, establishes unconditional impossibility of public-key functional encryption with classical public-keys. A key technical ingredient in our proofs is a novel incompressibility property for pseudorandom states, which may be of independent interest. On the positive side, we show how to circumvent these fundamental barriers in memory-restricted models, where the adversary's quantum or classical memory is bounded. In this setting, we obtain new feasibility results for simulation-secure FE that allow many challenge ciphertexts or many functional key queries.