- A new proof (arXiv:2504.05710v2) establishes that perfect-complete quantum public-key encryption (QPKE) with classical keys cannot be built from quantumly secure one-way functions in a black-box way — closing a long-standing open question in quantum cryptography.
- The impossibility holds even in the quantum random oracle model (QROM), and extends to schemes with quantum public keys in natural settings — making it tight against every known QPKE construction.
- For security leaders, the practical signal is about trust foundations: the encryption you migrate to must rest on hardness assumptions that survive scrutiny, not on shortcuts that proofs like this one quietly demolish.
The Problem: You Are Betting Your Migration on Assumptions You Can’t See
Every post-quantum migration decision your team makes — which key encapsulation mechanism to deploy, which certificate authority to trust, which hardware root to standardize on — inherits a chain of mathematical assumptions. Most CISOs never examine that chain. They trust that “NIST-approved” means “proven secure.”
It does not. It means “no one has broken it yet, and the best minds believe the underlying problem is hard.” The difference matters because the entire field of cryptography is organized around what can be built from what. When a researcher proves that one primitive cannot produce another, they are drawing a hard boundary on the map — telling you which security guarantees are achievable and which are mirages.
The paper “Cryptomania v.s. Minicrypt in a Quantum World” draws exactly such a boundary. It proves that you cannot bootstrap quantum public-key encryption from the weakest useful assumption in cryptography — one-way functions — using black-box techniques. If your long-term quantum-security strategy assumed those two worlds were the same, the assumption was wrong, and now there is a proof saying so.
Technical Deep-Dive: What the Proof Actually Establishes
A Definition Worth Memorizing
Quantum public-key encryption (QPKE) is a public-key scheme in which keys, ciphertexts, or the encryption procedure itself exploit quantum information. In the variant this paper targets, the public and secret keys are classical bitstrings, while the ciphertext may be classical or quantum. The appeal is obvious: a public-key system that needs only the mildest cryptographic assumption — a one-way function (OWF), a function easy to compute but hard to invert — would be a remarkably cheap foundation for a quantum-era internet.
The paper’s central result says that foundation does not exist by black-box means.
“We prove that it is impossible to construct perfect-complete quantum public-key encryption (QPKE) with classical keys from quantumly secure one-way functions (OWFs) in a black-box manner, resolving a long-standing open question in quantum cryptography.” — arXiv:2504.05710v2, Cryptomania v.s. Minicrypt in a Quantum World
Three technical qualifiers carry the weight here, and each one matters to anyone reasoning about cryptographic guarantees:
- Perfect-complete — the scheme decrypts honestly generated ciphertexts with probability 1, no error. This is the cleanest, most desirable correctness condition.
- Black-box — the construction uses the one-way function only as an oracle, calling it without exploiting its internal structure. The overwhelming majority of practical cryptographic constructions are black-box, which is precisely why a black-box impossibility result is so consequential.
- Quantumly secure — the one-way function resists inversion even by a quantum adversary, which is the relevant threat model for the PQC era.
The Result Holds Where It Counts: The QROM
The authors do not stop at an abstract oracle. They prove that in the quantum random oracle model (QROM) — the standard idealized setting for analyzing hash-based and quantum-accessible primitives — no perfect-complete QPKE scheme with classical keys and classical or quantum ciphertext can be secure. The QROM is the same model used to argue the security of many deployed and candidate post-quantum schemes, so the impossibility lands inside the territory practitioners actually reason about.
The separation is tight. The paper notes its impossibility “extends to QPKE with quantum public key in natural settings” and is tight to all known QPKE constructions with quantum public keys — meaning there is no obvious construction the proof fails to rule out.
This is also a strict improvement over prior work. Earlier attempts at this boundary either relied on unproven conjectures or imposed artificial restrictions on the key-generation algorithm. This result removes those crutches.
Comparison: Where QPKE Now Stands
| Dimension | Prior results | arXiv:2504.05710v2 |
|---|---|---|
| Assumption needed | Required unproven conjectures | None — unconditional black-box proof |
| Restrictions on key generation | Imposed restrictions | No artificial restrictions |
| Model | Limited / idealized cases | Holds in the QROM |
| Key type covered | Narrower | Classical keys; extends to quantum public keys in natural settings |
| Tightness | Gaps remained | Tight to all known QPKE constructions |
| Open question status | Open | Resolved for the black-box, classical-key case |
Industry Context: The Cryptomania / Minicrypt Map
Cryptographers organize their world into “complexity worlds” named by Russell Impagliazzo. Two of them frame this result:
- Minicrypt — the world where one-way functions exist but public-key encryption does not. Symmetric crypto, hashes, and signatures live here.
- Cryptomania — the richer world where public-key encryption exists, enabling key exchange between strangers.
Classically, a foundational result already separates these worlds: you cannot build public-key encryption from one-way functions alone by black-box means. The quantum era reopened the question, because quantum information offered new tricks — quantum states as keys, quantum ciphertexts, superposition queries — that might collapse the gap. Optimists hoped quantum mechanics would let Minicrypt assumptions reach into Cryptomania.
This paper says: not for QPKE with classical keys, and not by black-box construction. The quantum world inherits the same hard separation.
Why a Theory Result Belongs on a CISO’s Radar
No TLS handshake breaks because of this paper. There is no CVE, no patch, no 90-day clock ticking on an exploit. The honest framing is that this is a foundational impossibility proof, not a deployable vulnerability — and a credible analysis should say so plainly rather than manufacture urgency.
What it changes is the vendor and standards conversation. When a supplier pitches a quantum-era encryption product, the right question is no longer “is it fast?” but “what hardness assumption does its security reduce to, and is that assumption known to be sufficient?” Results like this one are how the field separates marketing from mathematics. A scheme claiming public-key security from nothing more than a one-way function, with classical keys, now has a proof standing in its way.
The BeQuantum Perspective
We build BeQuantum’s stack on a simple discipline: every security guarantee must trace to an assumption we can name and defend. That principle is exactly what this proof rewards.
Our PQC Layer standardizes on NIST-selected lattice and hash-based mechanisms whose security reductions are explicit and conservative — never on speculative constructions hoping that quantum tricks will conjure public-key strength from minimal assumptions. A proof that rules out QPKE-from-OWFs is, for us, confirmation that the conservative path was the correct one.
Our Digital Notary treats this layering as auditable evidence. Rather than asking customers to trust a black box, it records which cryptographic primitive signed or sealed each artifact and anchors that record so the assumption chain behind any verification is inspectable after the fact — turning “trust us” into “check the ledger.”
And our IceCase hardware roots keep classical key material in tamper-resistant custody, which is precisely the regime this paper studies: classical keys feeding quantum-aware protocols. Knowing the theoretical ceiling on what classical-key QPKE can achieve tells us where hardware-enforced boundaries must do the heavy lifting instead of optimistic protocol design.
The takeaway is not a product claim. It is a posture: build on assumptions that survive proofs, and make the assumption chain something an auditor can actually follow.
What You Should Do Next
- Within 90 days, inventory the hardness assumptions behind your PQC choices. For every key exchange and signature mechanism on your roadmap, document what computational problem its security reduces to. If a vendor cannot answer this, treat it as a red flag, not a detail.
- Add a “foundations” line to your cryptographic vendor reviews. Ask whether any product relies on quantum public-key encryption with classical keys derived solely from symmetric-style assumptions. This proof gives you the language to challenge such claims.
- Track theoretical results as a leading indicator. Impossibility proofs arrive years before the products they invalidate reach procurement. Assign someone on your architecture team to monitor quantum-cryptography separations the way you monitor CVEs — early, and as input to strategy rather than incident response.
FAQ
Q: Does this proof mean quantum public-key encryption is impossible? A: No. It proves that perfect-complete QPKE with classical keys cannot be built from quantumly secure one-way functions using black-box techniques. Constructions based on stronger assumptions, or non-black-box methods, are not ruled out by this result.
Q: Should we change any production system because of this paper? A: Not directly. This is a theoretical impossibility proof with no associated vulnerability or patch. Its value is strategic — it sharpens the questions you ask vendors and standards bodies about which assumptions a quantum-era scheme actually depends on.
Q: What is the difference between Minicrypt and Cryptomania, and why does it matter here? A: Minicrypt is the cryptographic world where one-way functions exist but public-key encryption does not; Cryptomania is where public-key encryption exists. This paper shows that, for QPKE with classical keys, the quantum world keeps these two worlds separate — you cannot cheaply cross from one to the other.
Last updated: June 4, 2026. Primary source: Cryptomania v.s. Minicrypt in a Quantum World, arXiv:2504.05710v2.
