⚛️ quantum physics

From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation

This paper initiates the study of quantum indistinguishability obfuscation (iO) by defining natural variants of the primitive and demonstrating that, combined with the infinitely-often quantum worst-case hardness of $\mathsf{NP}$ , it enables the construction of diverse quantum cryptographic primitives like pseudorandom unitaries and quantum public-key encryption, while also yielding a simplified construction of one-way functions from classical iO.

Original authors: Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa

Published 2026-07-07

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa

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: Locking the "Black Box"

Imagine you have a secret recipe for a cake. You want to give the recipe to a baker so they can bake the cake, but you don't want them to steal the recipe or figure out the secret ingredients.

In the world of cryptography, this is called Obfuscation. It's like taking a clear, readable instruction manual and scrambling it into a tangled, unreadable knot. The knot still works (you can still bake the cake), but if you look at it, you can't tell how it works or what the secret ingredients are.

For a long time, scientists have studied a specific type of scrambling called Indistinguishability Obfuscation (iO). The rule is: If you have two different recipes that produce the exact same cake, the scrambled versions of those recipes should look identical to anyone trying to peek at them.

The Problem: Classical vs. Quantum

Until now, most of this research was "classical." It assumed that the people scrambling the recipes and the people reading them were using standard, non-quantum computers.

However, we are entering the Quantum Era. Quantum computers are like super-powered chefs that can do things classical computers can't. The big question this paper asks is: What happens if we use quantum mechanics to scramble our recipes?

The authors found that quantum scrambling is tricky. In the classical world, you can sometimes "rewind" the scrambling process to prove it's secure. In the quantum world, the act of measuring (looking at) the scrambled recipe changes it, making it impossible to rewind. This made it seem like quantum scrambling might be useless for creating strong security locks.

The Breakthrough: The "Magic Trick" of Hard Problems

The authors discovered that even though quantum scrambling is messy, it becomes incredibly powerful if we assume one specific thing: That some math problems are so hard that even a quantum computer can't solve them quickly.

They call this the "Worst-Case Hardness of NP." Think of it like a giant, unsolvable maze. If we assume that no one can solve this maze, then the authors show that quantum scrambling can be used to build a whole new toolbox of security locks.

The Five Flavors of Quantum Scrambling

The paper defines five different ways to mix "Quantum" and "Classical" parts in this process. Imagine a factory with three stations:

The Scrambler (Obf): Who messes up the recipe.
The Reader (Eval): Who reads the scrambled recipe to bake the cake.
The Recipe Card (Encoding): What the recipe looks like after scrambling.

The authors tested every combination of these stations being either "Classical" (normal) or "Quantum" (super-powered). Here is what they found:

1. The All-Quantum Factory (Q, Q, Q)

Setup: The Scrambler, the Reader, and the Recipe Card are all Quantum.
Result: This creates a Quantum Symmetric Key Encryption.
Analogy: Imagine a secret handshake that only works if both people are using quantum magic. If you try to copy the handshake, the quantum rules break it. This allows for ultra-secure messaging where the "message" itself is a quantum state (like a fragile snowflake).

2. The Quantum Scrambler, Classical Card (Q, Q, C)

Setup: The Scrambler and Reader are Quantum, but the final Recipe Card is a normal piece of paper.
Result: This creates Quantum-Computation Classical-Communication (QCCC) Symmetric Key Encryption.
Analogy: You use quantum magic to scramble the recipe, but you print the result on paper to send it. The person receiving it uses quantum magic to read it. This is great for sending messages over normal phone lines but keeping the processing power quantum.

3. The Quantum Scrambler, Classical Reader (Q, C, C)

Setup: Only the Scrambler is Quantum; the Reader and the Card are normal.
Result: This creates Public Key Encryption (like the locks used for HTTPS websites).
Analogy: You use a quantum machine to lock a box, but anyone with a normal computer can check if the box is locked. This is a huge deal because it means we can build secure websites that are safe even against future quantum hackers, without needing the receiver to have a quantum computer.

4. The Classical Scrambler, Quantum Reader (C, Q, C)

Setup: The Scrambler is normal, but the Reader is Quantum.
Result: This creates One-Way Functions and Public Key Encryption.
Analogy: This is a "Post-Quantum" lock. A normal machine scrambles the recipe, but you need a quantum machine to unscramble it. The authors proved this is strong enough to build the foundation of all modern internet security.

5. The All-Classical Factory (C, C, C)

Setup: Everything is normal (no quantum parts).
Result: This is the "classic" result, but the authors found a simpler way to prove it works.
Analogy: They showed that even with old-school tools, you can build these locks more easily than previously thought, provided you assume the "unsolvable maze" exists.

The "Magic Trick" Explained Simply

How did they prove this? They used a clever trick based on a famous math theorem (Valiant-Vazirani).

Imagine you have a puzzle with a unique solution (a "Unique Witness").

They take a "Zero Function" (a recipe that always says "0") and a "Point Function" (a recipe that says "1" only for one specific secret number).
They scramble both recipes using their Quantum iO.
They proved that no one can tell the difference between the scrambled "Zero" recipe and the scrambled "Point" recipe, unless they can solve the "unsolvable maze" (the hard math problem).
Because no one can tell the difference, they can use this "indistinguishability" to build encryption keys that are mathematically impossible to break.

Why This Matters

Before this paper, we weren't sure if quantum obfuscation could actually do anything useful. We thought the "randomness" of quantum mechanics might ruin the security.

This paper says: No, it works!

If we assume there are math problems too hard for quantum computers to solve, then Quantum Obfuscation is a "Central Hub" for building almost any kind of secure quantum communication.
It allows us to build One-Way State Generators (creating quantum states that are easy to make but impossible to copy), Puzzles that are hard to solve but easy to check, and Encryption that keeps secrets safe.

In short, the authors turned a confusing quantum concept into a reliable blueprint for the future of secure communication. They showed that even in a quantum world, we can still build unbreakable locks, provided we assume some math problems remain unsolvable.

Technical Summary: From Worst-Case Hardness of NP to Quantum Cryptography via Quantum Indistinguishability Obfuscation

Problem Statement

Indistinguishability obfuscation (iO) is a powerful cryptographic primitive that, when combined with one-way functions (OWFs), enables the construction of a vast array of advanced cryptographic tools. However, iO alone does not imply the existence of OWFs; it requires an additional assumption regarding the hardness of NP. In the classical setting, Komargodski et al. [KMN+14] demonstrated that assuming the infinitely-often worst-case hardness of NP ( $NP \not\subseteq i.o.BPP$ ), one can construct OWFs from classical iO.

The central problem addressed in this work is the cryptographic power of quantum indistinguishability obfuscation (quantum iO). Unlike classical obfuscators, quantum obfuscators are inherently randomized due to measurement, meaning they cannot be "derandomized" by fixing a random seed. Consequently, the classical construction of OWFs from iO [KMN+14], which relies on derandomizability, does not directly extend to the quantum setting. It remains unclear whether quantum iO, combined with the quantum worst-case hardness of NP ( $NP \not\subseteq i.o.BQP$ ), can imply the existence of any cryptographic primitives, particularly those that do not require OWFs (often termed "Microcrypt" primitives).

Methodology

The authors initiate a systematic study of quantum iO by formalizing various variants based on the computational nature (classical vs. quantum) of three components:

Obfuscation Algorithm ($Obf$)
Evaluation Algorithm ($Eval$)
Obfuscated Encoding ( $\hat{C}$ )

They define $(X, Y, Z)$ -iO where $X, Y, Z \in \{Q, C\}$ , representing Quantum or Classical for the obfuscator, evaluator, and encoding, respectively. The paper focuses on five meaningful variants: $(Q, Q, Q)$ , $(Q, Q, C)$ , $(Q, C, C)$ , $(C, Q, C)$ , and $(C, C, C)$ .

Core Technical Approach

The foundation of their results is a reduction from the worst-case hardness of NP to the existence of specific cryptographic distributions. The methodology proceeds as follows:

Valiant-Vazirani Reduction: The authors leverage the Valiant-Vazirani theorem to reduce the assumption $NP \not\subseteq i.o.BQP$ to $UP \not\subseteq i.o.BQP$ (where UP is the class of problems with unique witnesses). This allows them to work with problems having a unique witness.
Indistinguishability of Point Functions vs. Zero Functions: The core technical theorem (Theorem 4.1) establishes that under the assumption $NP \not\subseteq i.o.BQP$ $N P \neq \subseteq i . o . B QP$ , the obfuscation of a random point function $P_k$ $P_{k}$ (which outputs 1 only on input $k$ $k$ ) is computationally indistinguishable from the obfuscation of a zero function $Z_m$ $Z_{m}$ (which outputs 0 everywhere), even when the distinguisher is given multiple samples generated with the same secret key $k$ $k$ .
- Proof Sketch: If a distinguisher could tell $Obf(P_k)$ from $Obf(Z_m)$ , one could construct an algorithm to recover the unique witness of a UP instance. This is achieved by constructing a circuit $V[x, v]$ that differs from the zero function on exactly one input ( $w \oplus v$ ). By the security of iO (specifically its equivalence to single-point differing-inputs obfuscation in this setting), distinguishing the obfuscations allows extracting the differing input, thereby recovering the witness $w$ .
Construction of Primitives: Using the indistinguishability of $Obf(P_k)$ $O b f (P_{k})$ and $Obf(Z_m)$ $O b f (Z_{m})$ , the authors construct various encryption schemes and other primitives. The specific construction depends on the $(X, Y, Z)$ $(X, Y, Z)$ variant:
- For Public Key Encryption (PKE), they use $Obf(P_k)$ as the public key and construct a ciphertext by obfuscating a circuit that checks if the input matches the secret key.
- For Symmetric Key Encryption (SKE), they use $Obf(P_k)$ and $Obf(Z_m)$ as the ciphertexts for messages 1 and 0, respectively.

Key Contributions and Results

The paper demonstrates that quantum iO, combined with $NP \not\subseteq i.o.BQP$ , implies a rich hierarchy of cryptographic primitives. The results are summarized by the variant of iO:

$(Q, Q, Q)$ -iO (Quantum Obf, Quantum Eval, Quantum Encoding):
- Implies IND-CPA secure Quantum Symmetric Key Encryption (QSKE) where the secret key is classical and the ciphertext is a quantum state.
- Implies One-Way State Generators (OWSGs) and EFI pairs.
$(Q, Q, C)$ -iO (Quantum Obf, Quantum Eval, Classical Encoding):
- Implies IND-CPA secure QCCC SKE (Quantum-computation Classical-communication SKE), where local computations are quantum but communication is classical.
- Implies EV-OWPuzzs (Efficiently-Verifiable One-Way Puzzles), OWPuzzs, OWSGs, QEFID pairs, and EFI pairs.
$(Q, C, C)$ -iO (Quantum Obf, Classical Eval, Classical Encoding):
- Implies IND-CPA secure QCCC PKE.
- Implies the same set of primitives as $(Q, Q, C)$ -iO (EV-OWPuzzs, OWPuzzs, OWSGs, etc.).
- Note: Since the obfuscator is quantum, it cannot be derandomized, so OWFs are not directly implied in this specific variant via the standard route, but the encryption scheme is constructed directly.
$(C, Q, C)$ -iO (Classical Obf, Quantum Eval, Classical Encoding):
- Implies IND-CPA secure QCCC PKE.
- Implies (Post-quantum) OWFs.
- Consequently, implies all Microcrypt primitives implied by Pseudorandom Unitaries (PRUs).
$(C, C, C)$ -iO (Classical Obf, Classical Eval, Classical Encoding):
- Implies IND-CPA secure PKE and (Post-quantum) OWFs.
- This recovers the classical result of [KMN+14] but with a simplified proof and weaker requirements.

Significance and Claims

The authors claim several significant contributions:

Initiating the Study of Quantum iO: This work is the first to systematically analyze the cryptographic implications of quantum iO, defining natural variants and mapping their power to specific primitives.
Bridging Worst-Case Hardness to Quantum Cryptography: The paper establishes that the infinitely-often worst-case hardness of NP is sufficient to construct a wide range of quantum cryptographic primitives (including OWSGs and EFI pairs) when combined with quantum iO, even in the absence of OWFs for certain variants.
Simplification of Classical Results: Even in the classical setting ( $(C, C, C)$ -iO), the authors provide a new, arguably simpler construction of OWFs from imperfect iO and worst-case NP hardness. Their approach avoids the "cascaded obfuscation" (obfuscating an already obfuscated circuit) required by [KMN+14] and only requires obfuscation for 3CNF formulas rather than general circuits.
Resolution of Open Problems: The construction of OWFs from imperfect iO for 3CNF formulas under worst-case hardness was an open problem left by [KMN+14]. While the authors note this has recently been resolved by other works [HN24, LMP24] using different techniques, their approach offers an alternative, simpler path.

The paper maintains a modest tone, emphasizing that these results are conditional on the existence of quantum iO and the worst-case hardness of NP, and that the specific primitives constructed depend heavily on the quantum/classical nature of the obfuscation components.