⚛️ quantum physics

On the Impossibility of Simulation Security for Quantum Functional Encryption

This paper establishes the impossibility of achieving simulation-secure quantum functional encryption by demonstrating that classical impossibility results extend to the quantum regime, proving unconditional barriers for unbounded challenge messages and impossibility under weaker assumptions like pseudorandom quantum states or public-key encryption for bounded key scenarios.

Original authors: Mohammed Barhoush, Arthur Mehta, Anne Müller, Louis Salvail

Published 2026-01-27

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohammed Barhoush, Arthur Mehta, Anne Müller, Louis Salvail

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: What is Functional Encryption?

Imagine you have a locked safe (encryption) containing a massive library of books.

Traditional Encryption: You either have the master key to open the whole safe and read every book, or you have no key and can't read anything. It's an "all-or-nothing" deal.
Functional Encryption (FE): This is a smarter system. You give a specific person a special "magic lens" (a functional key). If they look at the locked safe through this lens, they can see only the result of a specific math problem on the books (e.g., "What is the average word count?"). They cannot see the actual words, the titles, or any other data. They only get the answer to the specific question they asked.

The Goal: "Simulation Security"

In cryptography, we want to prove that this system is perfectly secure. The gold standard for this is called Simulation Security.

Think of it like a magic trick.

The Real World: A magician (the encryptor) locks the books, and a helper (the key holder) uses the lens to get the answer.
The Simulation World: A second magician (the simulator) tries to create a fake version of the trick without ever seeing the books. They only know the question being asked and the answer that was given.

If the audience (the attacker) cannot tell the difference between the Real World and the Simulation World, the system is secure. It proves that the lens revealed nothing about the books other than the specific answer.

The Problem: The "Impossible" Barrier

In the classical world (using normal computers and bits), researchers already proved that you cannot build a Functional Encryption system that is perfectly "Simulation Secure" in all situations. If you let the attacker ask too many questions or see too many locked safes, the magic trick falls apart.

The Big Question: Does this "impossibility" still hold true in the Quantum World?
Quantum computers use "qubits," which can hold much more information and behave strangely (like being in two places at once). Maybe quantum mechanics offers a loophole that lets us build a perfect, Simulation-Secure system where classical computers failed?

The Paper's Answer: No, the Barrier Still Exists

The authors of this paper say: No. The classical impossibility results largely extend to the quantum world. Even with the superpowers of quantum mechanics, you cannot build a perfectly Simulation-Secure Functional Encryption system in these specific scenarios.

They prove this using three different "traps" or arguments:

1. The "Too Many Messages" Trap (Unconditional Impossibility)

The Scenario: Imagine an attacker who asks to see the results for many different locked safes (ciphertexts) all at once, but then asks for just one special lens (functional key) to decode them all.
The Analogy: Imagine you have 1,000 locked boxes. You ask for a single master key that can open all of them.
The Quantum Twist: In the quantum world, maybe the key can be a tiny, compressed quantum state that holds the instructions for all 1,000 boxes?
The Result: The authors prove this is impossible. It's like trying to fit the instructions for 1,000 distinct books into a single, tiny note. Even with quantum compression, you simply cannot squeeze that much information into a small quantum state without losing the ability to decode the specific books later. If the simulator tries to fake the 1,000 boxes without knowing the contents, it fails because the "key" it generates later would need to be impossibly large to describe all the answers.

2. The "Tiny Key" Trap (Succinct Schemes)

The Scenario: This looks at a system where the "locked box" (ciphertext) is supposed to be very small, regardless of how complex the math problem is.
The Analogy: Imagine a system where you can lock a 100-page novel into a tiny envelope the size of a postage stamp.
The Quantum Twist: The authors use a concept called Pseudorandom Quantum States (PRS). These are quantum states that look completely random to anyone who doesn't have the secret key, but are actually generated by a specific formula.
The Result: They prove that you cannot "compress" these random-looking quantum states. If you try to shrink a random quantum state into a smaller space (to make a tiny ciphertext), you destroy the information. It's like trying to fold a map of the entire world into a square inch; the details get lost. Therefore, a system that promises tiny ciphertexts for complex math problems cannot be Simulation-Secure.

3. The "Many Keys" Trap (Public Key Encryption)

The Scenario: Imagine an attacker who sees one locked box but is allowed to ask for many different lenses (functional keys) to try and figure out what's inside.
The Analogy: You have one locked box. You ask for 1,000 different lenses. Each lens is supposed to reveal a different piece of information.
The Quantum Twist: The authors link this to Public-Key Encryption (PKE), a standard way we secure emails and websites today. They show that if a perfect Quantum Functional Encryption system existed, it would allow you to break the security of standard Public-Key Encryption.
The Result: Since we believe Public-Key Encryption is secure, this implies that a perfect Quantum Functional Encryption system cannot exist. It's a "proof by contradiction": "If this magic system existed, it would break the internet's security. Since the internet's security is real, this magic system is impossible."

Summary of the Findings

The paper essentially closes the door on the hope that quantum mechanics can save us from the limitations of Functional Encryption.

Classical Impossibility: We already knew you couldn't have a perfect "Simulation-Secure" system in the classical world if the attacker asked too many questions or saw too many messages.
Quantum Reality: The authors prove that quantum mechanics does not fix this. Even with qubits, entanglement, and quantum keys, the fundamental laws of information theory prevent a perfect Simulation-Secure system in these scenarios.

They show that the "barrier" is not just a weakness of classical computers, but a fundamental limit of how information (even quantum information) can be compressed and hidden.

What This Means (and Doesn't Mean)

It does NOT mean Functional Encryption is useless. We can still build systems that are "good enough" (Indistinguishability-Secure) for many real-world uses.
It does NOT mean quantum encryption is broken. It just means that one specific, very high-level definition of "perfect security" (Simulation Security) is unattainable, just as it was in the classical world.
It DOES mean that researchers looking for a "holy grail" of quantum Functional Encryption need to stop trying to achieve this specific type of perfect security, as the math says it's impossible.

Technical Summary: On the Impossibility of Simulation Security for Quantum Functional Encryption

Problem Statement
Functional Encryption (FE) is a cryptographic primitive allowing fine-grained access to encrypted data, where a user holding a functional key $fk_F$ can compute $F(m)$ from an encryption of $m$ without learning anything else. The strongest security notion for FE is simulation-based security (SIM-security), which requires that anything an adversary can compute from the ciphertext and functional keys can be simulated using only the function output.

While classical impossibility results have established that SIM-secure FE is unattainable for general polynomial circuits under specific query models (e.g., many ciphertexts with a single adaptive key, or a single ciphertext with many non-adaptive keys), these proofs rely on inherently classical arguments. A critical open question remained: Do these classical impossibilities extend to the quantum regime? Specifically, can quantum resources (quantum ciphertexts, quantum functional keys, or quantum public keys) overcome these barriers to realize SIM-secure Quantum Functional Encryption (QFE)?

Methodology
The authors address this question by extending classical impossibility proofs to the quantum setting, adapting them to handle quantum states and operations. The methodology involves three distinct impossibility proofs, each targeting a different security variant of QFE:

Information-Theoretic Compression Arguments: The authors reinterpret the simulator's task in a SIM-security game as an information compression problem. They demonstrate that if a SIM-secure scheme existed, it would imply the existence of a compression algorithm capable of compressing large amounts of information (messages or states) into a small quantum state (the functional key or ciphertext) while allowing perfect recovery.
Quantum Incompressibility Lemmas:
- For the many-ciphertext case, they utilize a result from [20] regarding entanglement-assisted communication to show that $n$ bits cannot be reliably recovered from fewer than $n/2$ qubits.
- For the succinct scheme case, they prove a novel lemma regarding the incompressibility of Pseudorandom States (PRS). They show that compressing an $n$ -qubit PRS into $n-k$ qubits irreversibly loses almost all structure, with the expected fidelity of recovery dropping exponentially with the compression amount. This is proven using the relationship between average fidelity and entanglement fidelity, combined with Levy's Lemma on the concentration of measure for Haar random states.
Reductions to Standard Cryptographic Assumptions:
- For the many-key query case, they construct a reduction from the existence of a SIM-secure QFE to the breaking of Public-Key Encryption (PKE). They show that a simulator for a 1-M-NA (single-message, many-query, non-adaptive) QFE scheme would act as an information compressor for multiple independent PKE ciphertexts, violating the security of the underlying PKE scheme.

Key Contributions and Results

The paper establishes three main impossibility results for Secret-Key QFE (which immediately implies impossibility for Public-Key QFE):

Unconditional Impossibility of M-1-AD SIM-Secure QFE:
- Setting: The adversary requests encryption of many messages ( $M$ ) and then obtains a single adaptive functional key for the identity function ($1$-AD).
- Result: No such scheme exists.
- Mechanism: The simulator must generate $n$ ciphertexts without knowing the messages. Upon receiving the identity key, it must recover all $n$ messages. This requires compressing $n$ random messages into a functional key of size bounded by a polynomial $p \ll n$ . The authors prove this is impossible even with quantum states, as it violates the information-theoretic limits of compressing classical information into a smaller quantum state.
Conditional Impossibility of Succinct 1-1-NA SIM-Secure QFE:
- Setting: The adversary requests a single message and a single non-adaptive functional key. The scheme is succinct (ciphertext size is independent of the function size).
- Assumption: Existence of Pseudorandom States (PRS).
- Result: No such scheme exists.
- Mechanism: The authors show that a succinct QFE for the circuit class of PRS generators would allow the compression and decompression of PRS. They prove that PRS are incompressible (a property stronger than classical PRFs in some contexts, as PRF $\implies$ PRS, but the reverse is not known). If a succinct QFE existed, one could distinguish PRS from Haar random states by checking if the compressed state could be recovered, breaking the PRS assumption.
Conditional Impossibility of 1-M-NA SIM-Secure QFE:
- Setting: The adversary requests a single ciphertext and many non-adaptive functional keys.
- Assumption: Existence of Public-Key Encryption (PKE) with classical keys.
- Result: No such scheme exists.
- Mechanism: The authors construct an attack where the adversary uses the QFE simulator to compress $n$ independent PKE ciphertexts (encrypting different messages) into a single QFE ciphertext. If the simulator is successful, it allows the recovery of all $n$ messages from the single compressed ciphertext and the functional keys. This violates the security of the underlying PKE scheme. Notably, this result holds for non-succinct schemes, unlike the PRS-based result.

Significance and Claims

The paper claims to resolve the central question of whether quantum resources can bypass the classical barriers to SIM-secure FE. The authors conclude that the classical impossibilities largely extend to the quantum world, though the proofs require new technical tools to handle quantum states.

Nuanced Barriers: The results are more nuanced than classical ones. For instance, the impossibility of 1-M-NA SIM-security in the quantum setting relies on the assumption of PKE (or PRS for succinct schemes), whereas the classical result is unconditional (since classical FE implies PRF). This highlights that while the barrier exists, the specific cryptographic assumptions required to prove it differ in the quantum regime.
Independence of Assumptions: The paper emphasizes that the assumptions used (PRS and PKE) are incomparable. PKE is known to be separated from One-Way Functions (and thus PRS), and no implication exists in the reverse direction. Therefore, the two conditional impossibility results provide independent evidence against the existence of SIM-secure QFE.
Novelty of Proofs: The authors introduce a novel incompressibility property for Pseudorandom States, which they note may be of independent interest. They also provide the first impossibility proof for 1-M-NA SIM-secure QFE that does not rely on the succinctness of the scheme.
Scope: The results apply to general circuit classes. The authors acknowledge that restricted classes (e.g., "preimage sampleable" circuits) or specific models (like the bounded-quantum-storage model) might still permit SIM-security, but for general QFE, the simulation-based security goal appears unattainable.

In summary, the paper demonstrates that the fundamental tension between the information contained in a ciphertext and the limited size of a functional key (or vice versa) persists in the quantum setting, preventing the realization of the strongest security notion for functional encryption.