In quantum cryptography, the quest for the simplest primitive has narrowed to two leading candidates: EFI pairs and one-way puzzles. EFI pairs—short for Efficiently preparable, statistically Far, and computationally Indistinguishable quantum states—were introduced by Brakerski, Canetti, and Qian at ITCS 2023. They are pairs of quantum states that a quantum computer can produce quickly, yet no efficient algorithm can tell apart, even though the states are very different in a statistical sense. One-way puzzles, formalized by Khurana and Tomer at STOC 2024, are classical objects: a puzzle is easy to generate, but any attempt to solve it fails with high probability. It is known that one-way puzzles imply EFI pairs; if you can make puzzles, you can also construct indistinguishable quantum states. But the reverse question—whether EFI pairs can exist in a world without one-way puzzles—has been stubbornly open. That question matters because EFI pairs are arguably the simpler quantum object, and if they require classical hardness to exist, the minimal assumption for quantum cryptography might be purely classical after all. Now, an anonymous preprint posted to arXiv on September 10, 2026, delivers a clear answer: through an oracle separation, it shows that EFI pairs can survive even when one-way puzzles are impossible, and simultaneously that quantum advantage on tasks with classical inputs and outputs can completely vanish. [arXiv:2609.11901]
The Core Finding
The authors construct a single classical oracle—a theoretical black box that answers specific types of queries—relative to which one-way puzzles do not exist at all. Even an unbounded verifier, with unlimited computational power, cannot solve them because the oracle simply hands out the answers. Yet in that same world, an EFI pair survives every distinguisher that queries the oracle classically throughout, holds advice about the oracle, and makes only one superposition query at the end. The oracle is designed to answer any question about the output probabilities of quantum sampling devices, which destroys all one-way puzzles, while also hiding a randomly chosen half-dimensional subspace inside the quantum states, which keeps the EFI pair indistinguishable.
Think of it like a cryptographic safe that only a quantum key can open, even in a universe where all classical puzzles are instantly solvable. The separation is strict: it proves that the existence of EFI pairs does not force the existence of one-way puzzles, resolving a central open problem. Moreover, the same oracle world yields a classical simulation of any quantum party in a classical-message protocol without pre-shared entanglement, meaning that relative to the oracle there is no proof of quantumness. Consequently, quantum polynomial time offers no advantage on any task with classical inputs and outputs, while the two quantum states stay indistinguishable.
“EFI pairs survive every distinguisher that queries the oracle classically throughout and holds advice about it, making its one superposition query at the end.”
The proof of security for the EFI pair rests on a two-pronged argument. For the classical queries, the authors reduce the adversary’s knowledge to a communication complexity problem. Imagine that the hidden subspace is held by one party, and the attacker’s oracle query answers—which are classical strings—are provided to a second party that must decide whether a vector lies in the subspace. The authors show that any successful distinguisher would give a protocol violating the known lower bound for the Vector-in-Subspace problem, established by Klartag and Regev at STOC 2011. Therefore, no classical querying strategy can break the EFI pair, regardless of what the oracle computes. The single superposition query, made at the very end, cannot be captured by that classical communication complexity framework. To bound its power, the authors deploy tools from random matrix theory, demonstrating that one quantum query cannot extract enough information about the hidden subspace to distinguish the states. The combination of these two bounds—classical communication complexity and random matrix theory—closes the door on all adversaries that fit the model.
The State of the Field
EFI pairs were proposed by Brakerski, Canetti, and Qian as a candidate minimal assumption for quantum cryptography, akin to the role that one-way functions play in classical cryptography. Khurana and Tomer’s one-way puzzles emerged as a competing classical-minimal notion, and they showed that puzzles imply EFI pairs. Before this preprint, no one had proved or disproved the converse, leaving the cryptographic community uncertain whether the two objects were actually equivalent under some relativizing reduction. Prior oracle separations in quantum cryptography—such as those separating quantum and classical communication complexity, or showing that quantum advantage can exist relative to certain oracles—used different techniques, often relying on the random oracle heuristic or black-box separations with specific promise problems. This work breaks new ground by connecting the problem directly to a communication complexity problem (Vector-in-Subspace) and handling the superposition query with random matrix theory, a combination that had not been tried before for EFI pairs.
The broader landscape of quantum computing is now heavily focused on demonstrating quantum advantage in near-term devices, such as Google’s Sycamore and IBM’s superconducting processors, and on advancing quantum simulation for chemistry and materials. Yet foundational questions about the raw materials of quantum security remain far from settled. The NIST post-quantum cryptography standardization process, which finalized its first algorithms in 2024 and 2025, assumes classical hardness against quantum attacks. But if quantum cryptography can be built from weaker assumptions—like EFI pairs without any classical hardness—it could open a different path to security that does not rely on the difficulty of factoring or lattice problems. This preprint helps clarify the logical relationships among those building blocks.
From Lab to Reality
For theoretical computer scientists, the result draws a sharper boundary inside the zoo of quantum cryptographic primitives. It confirms that EFI pairs are not merely a disguised form of one-way puzzles, which may guide the search for the absolute weakest assumption that still enables protocols like quantum bit commitment or quantum oblivious transfer. For experimental physicists and engineers, EFI pairs remain an abstract concept; no physical implementation of an EFI pair that can withstand arbitrary classical attacks has been demonstrated. However, the idea that quantum indistinguishability can be preserved even in worlds where classical hardness fails reinforces the motivation to develop quantum memories and state-preparation techniques that could eventually realize such objects. For investors and strategists monitoring the quantum-safe cybersecurity market—projected to reach several billion dollars by 2030 as enterprises upgrade their cryptographic infrastructure—findings like this underscore that the theoretical foundations of quantum security are still being mapped. True quantum advantage in cryptography may depend not on raw computational speed but on subtle distinctions among cryptographic assumptions, which could influence which protocols get standardized and commercialized in the long run.
What Still Needs to Happen
Two major technical obstacles remain. First, the oracle separation restricts the distinguisher to a single superposition query at the end of its computation. Real-world adversaries could potentially make many quantum queries interleaved with classical processing. The authors state conjectures on how to extend the proof to multiple quantum queries, but a full proof is not yet available. Removing this restriction is essential to claim that EFI pairs can survive in a fully quantum world without puzzles. Second, the entire construction lives in the oracle model—a theoretical framework where a magical black box is assumed to exist. In the real world, such oracles do not exist, and the challenge is to instantiate the separation in the plain model without oracles, or to show that similar separations hold under standard cryptographic assumptions. Research groups at institutions such as MIT, the Simons Institute for the Theory of Computing, and several universities in Israel, Europe, and the U.S. are actively exploring oracle separations and the limits of quantum advantage. Resolving these deeper questions may require new insights into communication complexity with quantum queries, or entirely new proof techniques. No concrete timeline exists, but the preprint’s conjectures provide a roadmap for the next years of investigation.
Conclusion
In short: quantum advantage on classical-input/output tasks can vanish relative to a classical oracle while quantum states remain indistinguishable, formally separating EFI pairs from one-way puzzles. The preprint serves as a new milestone in the quest to understand the absolute minimal requirements for quantum cryptography, and it illustrates how communication complexity can illuminate the boundary between quantum and classical power. For a field that often chases experimental demonstrations of supremacy, this theoretical separation reminds us that the deepest questions about quantum advantage lie in the logic of impossibility, not just in faster computers.