⚛️ quantum physics

Separating Quantum Indistinguishability Obfuscation from Falsifiable Assumptions

This paper establishes a barrier to constructing quantum indistinguishability obfuscation (qIO) and witness encryption for QMA from standard falsifiable cryptographic assumptions by proving that their security cannot be reduced to such assumptions via restricted classical black-box reductions, contingent on the existence of a specific QMA gap problem.

Original authors: Mohammed Barhoush, Tomoyuki Morimae, Ramis Movassagh

Published 2026-08-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohammed Barhoush, Tomoyuki Morimae, Ramis Movassagh

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

In the world of cryptography, the ultimate goal is often to hide the inner workings of a program while keeping its function intact. Imagine a piece of software that performs a complex calculation; the ideal tool would scramble its code so thoroughly that no one could reverse-engineer it, yet the program would still run perfectly for anyone who needed to use it. This concept, known as obfuscation, has long been a holy grail for computer scientists. While researchers have made significant progress in scrambling classical computer programs, the rise of quantum computing has introduced a new frontier. Quantum programs operate on the strange rules of quantum mechanics, where information can exist in multiple states at once, making them far more difficult to protect. A specific type of protection called quantum indistinguishability obfuscation aims to make these quantum programs unintelligible, serving as a foundation for advanced security systems like witness encryption, which allows data to be locked behind a statement that can only be unlocked if a specific secret proof exists.

For years, the scientific community has been trying to build these quantum security tools using standard, well-understood mathematical assumptions. These assumptions are like the bedrock of modern encryption; they are problems that are believed to be hard to solve, such as finding a specific key in a massive haystack. If a new security tool can be built on top of these known hard problems, it is considered trustworthy. However, a new study by researchers at IonQ and Kyoto University suggests that this path may be blocked. They have proven that a specific, powerful form of quantum security cannot be constructed from any of these standard, testable mathematical assumptions, provided the security proof follows a certain logical structure. This finding does not mean the security tool is impossible to build, but rather that if it exists, it must rely on a foundation that is fundamentally different from the ones we currently use to secure our digital world.

The researchers focused their investigation on a specific scenario involving witness encryption for a class of problems known as QMA. In simple terms, QMA problems are those where the answer can be verified quickly if you are given a special quantum piece of evidence, called a witness, but finding that evidence is incredibly difficult. The researchers asked a straightforward question: Can we build a system that encrypts data based on a statement, such that only someone with the correct quantum witness can decrypt it, using only standard mathematical assumptions? To answer this, they employed a rigorous method of proof that acts like a logical trap. They imagined a scenario where a security proof tries to link the safety of this encryption system to a standard mathematical assumption. They then showed that if such a link existed, it would lead to a contradiction.

The core of their discovery relies on a clever simulation. They demonstrated that if a standard mathematical assumption were true, it would be possible to create a "fake" attacker who could break the encryption system just as well as a real, infinitely powerful attacker, without actually knowing the secret. In the world of cryptography, if a system can be broken by a fake attacker that looks identical to a real one, the system is considered insecure. The researchers proved that for the specific type of quantum encryption they studied, this fake attacker can always be constructed using a standard mathematical assumption. This means that if the encryption system were truly secure, the underlying mathematical assumption would have to be false. Since we believe these standard assumptions are true, the logical conclusion is that the encryption system cannot be built upon them.

This result is significant because it places a hard limit on how we can approach quantum security. The study does not say that quantum indistinguishability obfuscation is impossible to achieve; it simply says that we cannot build it using the standard, testable assumptions that have served us well for decades. The researchers were careful to define the boundaries of their proof. Their conclusion applies to a specific class of security proofs where the testing process follows certain rules, such as checking the system with standard, non-adaptive queries. They also noted that their result specifically concerns systems that output classical information, like standard digital bits. It leaves open the possibility that obfuscators which output quantum states might still be built from standard assumptions, though this remains an open question.

The study introduces a new concept to support its argument: a gap between what can be verified with two messages of classical communication and what can be verified with quantum witnesses. They assume that there are certain quantum problems that cannot be solved or verified efficiently using just two rounds of classical conversation, even with the help of a powerful oracle. This assumption is supported by current knowledge in the field, where the best known methods for verifying quantum computations require more than two messages. By relying on this gap, the researchers were able to construct their logical trap, showing that the bridge between standard assumptions and this specific quantum security tool cannot be built.

Ultimately, this work serves as a guidepost for future research. It tells the cryptographic community that if they wish to build these advanced quantum security tools, they must look beyond the standard assumptions they have relied on for years. They may need to find new, perhaps more exotic, mathematical foundations or accept that these tools rely on assumptions that are harder to test and verify. The paper does not close the door on quantum obfuscation, but it firmly closes the door on one specific, widely hoped-for path to achieving it. By ruling out this possibility, the researchers have clarified the landscape, forcing scientists to rethink their strategies and perhaps look for entirely new ways to secure the quantum future.

Technical Summary: Separating Quantum Indistinguishability Obfuscation from Falsifiable Assumptions

1. Problem Statement

The paper addresses the foundational challenge of constructing Quantum Indistinguishability Obfuscation (qIO) and Witness Encryption (WE) for QMA from standard, falsifiable cryptographic assumptions. While classical IO has been constructed from well-founded assumptions (albeit with assumptions broken by quantum attacks), the status of qIO remains unsettled. No construction of qIO exists in the plain model with a security proof from standard assumptions, nor is there a known impossibility result explaining this absence.

Specifically, the authors investigate whether the security of WE for QMA (and by extension, null-qIO) can be based on any falsifiable assumption. A falsifiable assumption is defined as one where an efficient challenger can decide if an adversary has won an interactive game. The paper notes that WE for QMA is inherently non-falsifiable because verifying an adversary's success (e.g., proving a statement is outside the language or that two circuits are null) is computationally hard. Consequently, the authors ask: Can we build qIO (or WE for QMA) from standard falsifiable assumptions?

2. Methodology

The authors employ the simulatable-adversary paradigm, originally introduced by Gentry and Wichs for classical SNARGs and extended to quantum settings by Alagic et al. and Barhoush et al. The core strategy involves demonstrating that if a black-box reduction existed, it would lead to a contradiction regarding the hardness of a specific assumption.

The methodology proceeds through the following technical steps:

Modified Security Game: The authors redefine the WE security game to be interactive. Unlike previous separations where the adversary chooses the instance $x$ as a static input, here the adversary must first commit to an instance $x$ (which it claims is outside the language $L$ ) and then attempt to decrypt a ciphertext generated under $x$ . This interactivity is crucial for the separation but complicates the simulation.
The QMA–QCIP[2] Gap Assumption: The impossibility result relies on a new assumption: the existence of a QMA–QCIP[2] gap problem. This posits a QMA language $L$ $L$ where:
1. Yes-instances can be efficiently sampled with witnesses.
2. No-instances can be sampled (possibly inefficiently).
3. No efficient quantum algorithm can distinguish between these distributions, even with access to a QCIP[2] oracle (an oracle that decides the value of any two-message interactive proof over a classical channel).
Restricted Reductions: The impossibility applies to restricted quantum black-box reductions. These reductions must:
1. Query the adversary non-adaptively.
2. Preserve the security parameter (no queries with smaller parameters).
3. Query the adversary classically.
4. Query only on honestly generated ciphertexts (ciphertexts produced by the honest encryption algorithm on random bits).
Simulation via Hidden Tests: To simulate an unbounded adversary that breaks WE, the authors construct a simulator using the QCIP[2] oracle. A key technical innovation is the use of hidden planted ciphertexts. The simulator interleaves real ciphertexts with test ciphertexts (whose plaintexts are known) and shuffles them. The verifier in the QCIP[2] protocol rejects if any test ciphertext is answered incorrectly. This forces the optimal prover (the oracle's output) to behave as a Bayesian decryptor (outputting the most likely plaintext) for all ciphertexts, including the real ones, to avoid rejection. This allows the efficient simulator to mimic the behavior of the unbounded adversary.

3. Key Contributions and Results

Main Theorem (Theorem 2): Assuming the existence of a QMA–QCIP[2] gap problem, the security of WE for QMA cannot be based on any falsifiable cryptographic assumption via restricted quantum black-box reductions.
Corollary for Null-qIO: Since null-qIO implies WE for QMA (as shown by Bartusek and Malavolta), the same separation applies to null-qIO.
Uniform Security: Unlike prior separations that relied on non-uniform advice (hardwiring adversary behavior), this result rules out reductions even for falsifiable assumptions that are secure only against uniform adversaries. This is achieved because the interactive nature of the WE game prevents compressing the adversary's exponential behavior into non-uniform advice.
Technical Barrier: The paper establishes that if one believes a falsifiable assumption is true, then no security proof of the stated form can exist to base WE for QMA on it.

4. Limitations and Scope

The paper is explicit about the boundaries of its result:

Ciphertext Type: The impossibility applies only to WE with classical ciphertexts. It does not rule out qIO or WE where the obfuscator or ciphertext is a quantum state. The authors note that existing constructions for pseudo-deterministic quantum circuits and unitary programs output quantum states and thus fall outside this separation.
Reduction Restrictions: The result is limited to reductions that are non-adaptive, parameter-preserving, and query only honestly generated ciphertexts. Removing these restrictions remains an open problem. The authors argue these restrictions are natural for WE but acknowledge that lifting them is the primary open challenge.
Classical IO: The techniques do not apply to classical IO for classical circuits. Classical IO implies WE for NP, and for NP, a QCIP[2] oracle decides the language outright (since the witness is a one-message certificate), meaning no gap problem exists.
Assumption Validity: The separation is conditional on the existence of a QMA–QCIP[2] gap problem. While supported by the current landscape (e.g., Mahadev's protocol requiring four messages, and prior black-box separations), a concrete instantiation or oracle separation for this specific gap is not provided in the paper.

5. Significance

The paper provides a structural barrier to constructing qIO and WE for QMA from standard assumptions. It suggests that the difficulty in constructing these primitives is not merely a lack of cleverness in construction but may be fundamental, rooted in the inability to base non-falsifiable primitives on falsifiable ones via standard black-box techniques.

By introducing the QMA–QCIP[2] gap problem and demonstrating a separation in the simulatable-adversary paradigm for an interactive security game (as opposed to the one-shot games of prior work), the authors extend the frontier of impossibility results in quantum cryptography. The work highlights that the interactive nature of witness encryption creates unique challenges that prevent the direct application of previous non-interactive separation techniques, necessitating new tools like the hidden-test protocol to force optimal prover behavior.

Ultimately, the paper concludes that unless the QMA–QCIP[2] gap assumption is false, or unless one moves beyond restricted black-box reductions (or to non-falsifiable assumptions), the construction of qIO from standard assumptions is likely impossible.