Cryptomania v.s. Minicrypt in a Quantum World

This paper proves that constructing perfect-complete quantum public-key encryption with classical keys from quantumly secure one-way functions is impossible in a black-box manner within the quantum random oracle model, thereby resolving a long-standing open question and establishing tight limits on known quantum public-key encryption schemes.

The Gist

The Big Picture: The "Magic Box" vs. The "One-Way Street"

Imagine the world of cryptography as a game of building houses.

• Minicrypt is a world where you have a One-Way Street. You can easily drive a car down it (encrypt a message), but it's impossible to drive back up (decrypt it) without a special key. This is the foundation of most current security.
• Cryptomania is a world where you have Public Key Encryption (PKE). This is like a "Magic Box." Anyone can drop a letter into the box (encrypt it) using a public key, but only the person with the secret key can open it. This is much more powerful and convenient.

For decades, computer scientists have asked: Can we build the "Magic Box" (Cryptomania) using only the "One-Way Street" (Minicrypt)?

In the classical world (our current computers), the answer is No. You can't build the Magic Box just from the One-Way Street.

But we are entering the Quantum World (where computers use quantum mechanics). In this new world, some rules change. Scientists wondered: Maybe in the quantum world, the One-Way Street is actually strong enough to build the Magic Box?

This paper says: No. Even in the quantum world, you cannot build a perfect "Magic Box" using only a "One-Way Street."

The Setting: The "Random Oracle" (The Magic Dictionary)

To prove this, the authors imagine a scenario called the Quantum Random Oracle Model (QROM).
Think of the "Oracle" as a giant, magical dictionary that everyone shares.

• If you ask the dictionary a question, it gives you a random answer.
• If you ask the same question again, it gives the same answer.
• But nobody knows the answers in advance; they have to look them up.

In the quantum version, you can ask the dictionary many questions at once (superposition), which makes it very powerful. The authors ask: If we have this super-powerful dictionary, can we build a perfect Quantum Public Key Encryption (QPKE) system?

The Three Main Findings

The paper proves that Perfect-Complete QPKE is impossible in three specific scenarios. "Perfect-Complete" means the system never makes a mistake; if you encrypt a message, it always decrypts correctly.

1. The Standard Case (Classical Keys, Classical Messages)

The Analogy: Imagine Alice and Bob want to send secret notes. They use a shared dictionary to generate a lock (public key) and a key (secret key).
The Result: The authors prove that if Alice and Bob try to build this system using only the "One-Way Street" and the "Magic Dictionary," a hacker (Eve) can always break it.

• How? Eve uses a clever trick. She doesn't need to guess the secret key directly. Instead, she simulates Alice and Bob's conversation, creates a "fake" version of Alice, and then tweaks the dictionary just enough so that the fake Alice can still decrypt the message. Because the dictionary is random, Eve can find a "loophole" that makes the system fail.

2. The Quantum Message Case (Classical Keys, Quantum Messages)

The Analogy: Now, imagine the secret note isn't a piece of paper, but a fragile, glowing quantum bubble.
The Result: Even if the message is a quantum bubble, the system still fails. The authors show that the hacker can still use the same "fake Alice" trick to break the encryption. The fact that the message is quantum doesn't save the system.

3. The Quantum Key Case (Quantum Keys)

The Analogy: This is the most advanced version. Imagine the "lock" (public key) itself is a quantum bubble, not a piece of paper.
The Result: The authors prove this is also impossible, but with a specific condition. The condition is that the quantum lock must be generated in a way that doesn't depend on the "Magic Dictionary" at the moment of creation.

• Why it matters: All the quantum encryption schemes scientists have built so far do depend on the dictionary to create the lock. The authors show that if you try to make a lock that doesn't depend on the dictionary (a "pure" quantum lock), it still can't be built from a One-Way Street. This means the existing quantum schemes are "tight"—they are already at the limit of what is possible, and you can't do better.

The "Hacker's Toolkit" (How they proved it)

The paper introduces a new way for a hacker (Eve) to attack these systems. Previous attempts to prove this were stuck because they relied on unproven guesses or assumed the hackers were too weak.

The authors' new method is like a Master Chef who can taste a soup and perfectly recreate the recipe without knowing the ingredients.

1. The Simulation: Eve watches Alice and Bob talk. She creates a "shadow" version of Alice.
2. The Markov Chain: Using a mathematical tool called a "Quantum Markov Chain," Eve proves that she can create a fake Alice that is statistically almost identical to the real one, even though she doesn't have the secret key.
3. The Dictionary Tweak: The hardest part was making the fake Alice work with the real dictionary. The authors developed a new algorithm (a "Win-Win" strategy) that allows Eve to slightly change the dictionary's answers in a way that:
   • Doesn't break Bob's view of the world (so he doesn't notice).
   • Allows the fake Alice to successfully decrypt the message.

The Conclusion

In the quantum world, the gap between "Minicrypt" (One-Way Streets) and "Cryptomania" (Magic Boxes) remains wide.

• Minicrypt exists: One-way functions are real and useful.
• Cryptomania is out of reach: You cannot build a perfect, black-box Quantum Public Key Encryption system using only those one-way functions.

This resolves a long-standing question in cryptography. It tells us that even with the power of quantum computers, we cannot magically upgrade our basic security tools into public-key systems without adding new, stronger assumptions. The "Magic Box" requires more than just a "One-Way Street," even in a quantum universe.

Technical Summary

Technical Summary: Cryptomania v.s. Minicrypt in a Quantum World

1. Problem Statement

The paper addresses a fundamental open question in quantum cryptography regarding the boundary between "Minicrypt" (a world where only one-way functions (OWFs) exist) and "Cryptomania" (a world where public-key encryption (PKE) exists). Specifically, the authors investigate whether a separation exists between these two worlds in the Quantum Computation Classical Communication (QCCC) setting.

While it is known that quantum communication allows for the construction of many Cryptomania primitives (like key agreement and PKE with quantum public keys) from OWFs, the feasibility of constructing perfect-complete Quantum Public-Key Encryption (QPKE) with classical keys (and either classical or quantum ciphertext) from OWFs in the QCCC setting remained unresolved. Previous attempts to prove such a separation in the Quantum Random Oracle Model (QROM) relied on unproven conjectures (e.g., the "polynomial compatibility conjecture") or imposed restrictive assumptions, such as requiring the key generation algorithm to make only classical queries to the random oracle.

The core problem is to determine if perfect-complete QPKE can be constructed from OWFs in a black-box manner when the key generation process is allowed to make quantum queries to the oracle.

2. Methodology

The authors refine and unify the separation frameworks proposed in previous works [LLLL24, LLLL25] to prove impossibility results without relying on unproven conjectures. Their approach involves constructing an eavesdropper (Eve) who can break the security of a perfect-complete QPKE scheme by making a polynomial number of queries to the random oracle.

The proof strategy proceeds through the following steps:

1. Reduction to Key Agreement: The authors reduce the problem of breaking QPKE to breaking a two-round Quantum Key Agreement (QKA) protocol derived from the QPKE scheme.
2. Heavy Query Identification: Eve identifies "heavy queries" (inputs with significant query weight) made by the honest party (Bob) during the protocol. These queries are recorded and kept unchanged during oracle reprogramming to ensure the modified oracle remains indistinguishable to Bob.
3. Simulating Alice's View (Quantum Markov Chain): Using tools from quantum information theory, specifically the Approximate Quantum Markov Chain theorem [FR15] and properties of conditional mutual information (CMI), Eve constructs a simulated view of Alice ($A'$). By running Bob multiple times and applying a reconstruction channel, Eve generates a fake secret key ($sk'$) such that the joint state of the simulated system is statistically close to the real system.
4. Oracle Reprogramming via Polynomial Analysis: The central technical innovation lies in handling the inconsistency between the simulated Alice's view and the real random oracle.
   • The probability of Alice outputting a specific key pair is modeled as a low-degree polynomial $f(H)$ over the oracle's truth table.
   • The authors introduce a win-win argument based on a structural property of low-degree polynomials (Lemma 3.4). Eve seeks a partial assignment $\mu$ (a set of fixed oracle values) such that:
     • Case (a): The polynomial evaluates to non-zero under the reprogrammed oracle $H_\mu$, meaning the simulated key is valid for the new oracle.
     • Case (b): If Case (a) does not hold immediately, there exist many disjoint partial assignments that make the polynomial non-zero. Eve can then argue that at least one of these assignments is "light" (has low query weight) with respect to the decryption algorithm, allowing for a successful attack via statistical distance arguments.
5. Execution: Eve reprograms the oracle using the found partial assignment $\mu$ and runs the decryption algorithm with the simulated secret key $sk'$ to recover the shared key.

3. Key Contributions

• Resolution of the QCCC Separation: The paper proves that perfect-complete QPKE with classical keys cannot be constructed from OWFs in the QROM, even when the key generation algorithm makes quantum queries. This resolves the separation between Minicrypt and Cryptomania in the QCCC setting without unproven conjectures.
• Removal of Prior Restrictions: Unlike previous works [ACC+22, LLLL24, LLLL25], this result does not require:
  • Unproven conjectures (e.g., polynomial compatibility).
  • Restrictions on the key generation algorithm (e.g., requiring classical queries only).
  • Restrictions on the ciphertext (the result extends to quantum ciphertexts).
• Unified Framework: The authors present a refined framework for proving lower bounds for multiparty computation primitives in the QROM, leveraging a combination of quantum Markov chains and boolean function analysis (specifically the structure of low-degree polynomials).
• Tightness for Quantum Public Keys: The impossibility result is shown to be tight for all known QPKE constructions with quantum public keys, as those constructions inherently rely on the public key depending on the random oracle, a condition the impossibility proof exploits.

4. Main Results

The paper establishes the following theorems in the Quantum Random Oracle Model (QROM):

• Theorem 1.1 (Classical Keys/Ciphertext): Perfect-complete QPKE with classical keys and classical ciphertext does not exist.
• Theorem 1.3 (Classical Keys/Quantum Ciphertext): Perfect-complete QPKE with classical keys and quantum ciphertext does not exist.
• Theorem 1.4 (Quantum Public Keys): Perfect-complete QPKE with quantum public keys (where the public key is a deterministic function of the secret key, independent of the oracle) does not exist.

In all cases, an adversary (Eve) can break the scheme with probability $1 - O(\epsilon)$ using a polynomial number of queries to the random oracle.

5. Significance and Claims

The authors claim that this work provides a definitive characterization of the relationship between one-way functions and public-key encryption in the quantum world under the QCCC setting.

• Closing the Gap: The result closes the gap left by previous works that relied on conjectures or restricted models. It establishes that the "black-box barrier" between Minicrypt and Cryptomania persists even when quantum algorithms are allowed to query the oracle.
• Natural Assumptions: The focus on "perfect completeness" is highlighted as a natural requirement satisfied by many known schemes (including those with quantum keys), making the impossibility result robust and not an artifact of overly strict definitions.
• Framework Utility: The authors suggest that the improved separation framework, particularly the win-win argument involving polynomial reprogramming and quantum Markov chains, may be applicable to proving lower bounds for other MPC-related primitives with perfect completeness.

The paper does not propose new cryptographic constructions or experimental implementations; its contribution is purely theoretical, establishing a fundamental limit on what can be achieved in quantum cryptography based on standard assumptions.