⚛️ quantum physics

Quantum Cryptomania with Classical Communication without One-Way Functions

This paper establishes that quantum public-key encryption with classical communication can exist even in the absence of one-way functions by proving a black-box separation between the two primitives and providing a construction based on quantum indistinguishability obfuscation and one-way puzzles.

Original authors: Mohammed Barhoush, Amit Behera

Published 2026-10-26

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohammed Barhoush, Amit Behera

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 digital security, the foundation of almost every secret-keeping system is a specific kind of mathematical lock called a one-way function. Imagine a machine that is incredibly easy to run in one direction but nearly impossible to reverse; you can feed it a number and get a result, but you cannot figure out the original number just by looking at the result. For decades, scientists have believed that without these locks, the most advanced forms of encryption, such as the public-key systems that secure our online banking and private messages, simply could not exist. This belief created a hierarchy where the simple one-way lock was the necessary key to building the complex vault.

However, the rules change when we step into the realm of quantum computing, where information behaves according to the strange laws of physics rather than classical logic. In this quantum world, researchers have discovered that some basic security tools can exist even without these one-way locks. This has left a major question hanging over the field: does the most powerful form of encryption, public-key encryption, still require the one-way lock to function, even when the keys and messages themselves remain classical and easy to read? If the answer is yes, then the quantum world is not as different from the classical one as we hoped. If the answer is no, it would mean we can build the strongest digital vaults using only weaker, more fragile tools.

A team of researchers has now answered this question, revealing that the strongest form of encryption does not actually need the one-way lock to exist. They demonstrated that it is possible to construct a secure public-key encryption system where the keys and messages are entirely classical, yet the underlying one-way functions required by traditional theory simply do not exist. This finding overturns a long-held assumption that these two concepts were inextricably linked. The researchers did not just suggest this possibility; they provided a rigorous mathematical proof showing that in a specific quantum environment, a secure encryption scheme can operate perfectly while the one-way functions it was thought to depend on are completely absent.

To understand how this works, one must look at the nature of the tools being used. In classical computing, a one-way function is defined by its strict predictability; if you put the same input in, you must get the same output every single time. The researchers showed that in the quantum setting, this strict requirement is not necessary for encryption. They constructed a scenario where the encryption system works flawlessly, but any attempt to build a one-way function fails because the system is too flexible. The encryption scheme relies on a process that can produce different outputs for the same input, a feature that breaks the rigid definition of a one-way function but is perfectly acceptable for keeping messages secret.

The team proved this by creating a theoretical model, or a "world," governed by specific quantum rules. In this world, they built an encryption system that is secure against any attacker, even one with immense computing power. They then showed that in this same world, it is impossible to create a one-way function. The proof relies on a clever separation technique. They demonstrated that if an attacker could break the encryption, they would also be able to break the one-way function, but since the one-way function does not exist in this model, the encryption must remain secure. This creates a clear separation between the two concepts, proving that the existence of one does not guarantee the existence of the other.

Furthermore, the researchers explored what could replace the one-way function in this new landscape. They found that a different, weaker type of puzzle, known as an efficiently verifiable one-way puzzle, combined with a powerful tool called indistinguishability obfuscation, is sufficient to build the encryption system. This puzzle is easier to create than a one-way function but still hard enough to solve to provide security. By combining this puzzle with the obfuscation tool, which hides the inner workings of a computer program, they constructed a fully functional public-key encryption scheme. This construction is significant because it shows a path forward for quantum cryptography that does not rely on the strongest, and perhaps hardest-to-find, assumptions.

The implications of this work are profound for the future of cryptography. It suggests that the landscape of quantum security is more complex and nuanced than the simple hierarchy seen in classical computing. The researchers did not just find a loophole; they mapped out a new territory where the rules of security are different. They showed that the necessity of one-way functions is not a universal law but a feature of the classical world that does not necessarily apply when quantum mechanics is involved. This means that the quest for quantum-safe encryption might not require finding the elusive one-way function, but rather focusing on these weaker, more accessible puzzles.

The study also addressed the robustness of their findings. They showed that their results hold even when the attacker has access to the most powerful tools available in quantum mechanics, including the ability to reverse operations or copy quantum states in specific ways. The proof is not based on a guess or a simulation that might fail under different conditions; it is a mathematical certainty within the defined model. The researchers also clarified that while their encryption system works without one-way functions, it does not mean that one-way functions are useless. They simply showed that they are not a mandatory requirement for this specific type of encryption.

In the end, this research provides a comprehensive picture of the relationship between the building blocks of quantum security. It confirms that the quantum world allows for a richer variety of cryptographic possibilities than previously thought. The ability to build secure public-key encryption without the traditional one-way lock opens up new avenues for research and development. It challenges scientists to rethink the fundamental assumptions of their field and to explore new combinations of tools that were previously considered too weak to be useful. The work stands as a definitive proof that in the quantum realm, the path to secure communication is not as narrow as once believed.

Technical Summary: Quantum Cryptomania with Classical Communication without One-Way Functions

1. Problem Statement

In classical cryptography, the existence of One-Way Functions (OWFs) is a foundational assumption, necessary for most non-trivial primitives including signatures, private-key encryption, and bit commitments. While OWFs are implied by stronger primitives like Public-Key Encryption (PKE), it is known that OWFs alone may not be sufficient to construct PKE via black-box reductions (Impagliazzo and Rudich).

In the quantum setting, recent work has demonstrated that "Minicrypt" primitives (e.g., signatures, private-key encryption) can exist relative to quantum oracles even when quantum-computable one-way functions (qOWFs) do not exist, even under the restriction of classical communication. However, the relationship between qOWFs and "Cryptomania" primitives—specifically Public-Key Encryption with classical keys and ciphertexts (qPKE)—remained an open question. The central problem addressed by this work is Open Problem 1: Does public-key encryption still require quantum-computable one-way functions in the quantum setting, even if the keys and communication remain entirely classical?

2. Methodology

The authors employ a combination of oracle separation techniques and constructive cryptography to answer the open problem.

2.1 Oracle Separation (Negative Result)

To demonstrate that qOWFs are not necessary for qPKE, the authors construct a specific quantum oracle relative to which a secure qPKE scheme exists, but no qOWFs exist.

Oracle Design: The oracle is defined by a unitary, real, and self-inverse operation. It utilizes two independent random tables ( $A$ and $B$ ) and an interpolation parameter $\tau \in [0, 1]$ . The oracle operations (Key Sampling $O_{samp}$ , Encryption $O_{enc}$ , and Decryption $O_{dec}$ ) interpolate between the states defined by table $A$ and table $B$ based on $\tau$ .
The Barrier Theorem: A key technical contribution is a "General Barrier Theorem" (Theorem 5.2), a generalization of previous results by Bouaziz–Ermann et al. This theorem establishes that if a distribution of oracles admits random paths with bounded change (Lipschitz continuity) between independent samples, then any candidate evaluator that is "reliable" (deterministic) on a large fraction of inputs must compute the same function across a large set of oracles.
Conditioning Strategy: The authors condition the oracle distribution on events that force candidate qOWF evaluators to either:
1. Fail the determinism requirement (failing to produce a fixed output for a given input).
2. Become invertible via a PSPACE oracle (because their behavior is consistent enough across the oracle space to be simulated/averaged).
  By iterating this conditioning over all possible polynomial-time evaluators, they construct a distribution where no qOWF exists, yet the qPKE scheme remains secure due to the relative entropy bounds preserving the security of the underlying encryption.

2.2 Constructive Approach (Positive Result)

To show that qPKE can be built from weaker assumptions, the authors construct qPKE using:

Efficiently Verifiable One-Way Puzzles (EV-OWPuzz): A primitive weaker than qOWFs, consisting of a sampler and a verifier.
Quantum Indistinguishability Obfuscation (qiO): Specifically for quantum circuits that compute classical functions and produce classical obfuscated descriptions.

The construction adapts the classical paradigm of building PKE from OWFs and Indistinguishability Obfuscation (iO). A critical technical hurdle is that EV-OWPuzz verifiers may accept multiple answers with intermediate probabilities, whereas the classical proof relies on unique answers. The authors overcome this via a Suppression Lemma (Lemma 6.1), which uses hashing and amplification to suppress all but one accepting answer for a given puzzle, effectively converting the puzzle verifier into a point-function-like circuit suitable for obfuscation.

3. Key Contributions and Definitions

The paper introduces a nuanced framework for defining qOWFs to clarify the separation results:

qOWF1: Requires determinism on every input (except negligible error) and security against arbitrary quantum input samplers.
qOWF2: Requires determinism on average over uniform inputs, with security against uniform inputs.
qOWF3: Requires determinism on average over arbitrary quantum input samplers.

Key Results:

Oracle Separation (Theorem 1.1 & 1.3): There exists a quantum real, self-inverse unitary oracle relative to which perfectly correct, IND-CPA-secure qPKE exists, but neither qOWF1 nor qOWF2 exists. This establishes a black-box separation between qPKE and these stronger notions of qOWF.
Equivalence of qOWF3 and EV-OWPuzz (Theorem 1.4): The paper proves that qOWF3 exists if and only if EV-OWPuzz exists. Since qPKE implies EV-OWPuzz, it follows that qPKE implies qOWF3. This highlights that the separation is specific to the stronger definitions (qOWF1/2) and that the weakest definition (qOWF3) is equivalent to the puzzle primitive.
Construction of qPKE (Theorem 1.2 & 6.3): The authors construct IND-CPA-secure qPKE with classical communication and keys from the combination of EV-OWPuzz and qiO. This demonstrates that qPKE can be achieved from assumptions potentially weaker than qOWFs.
Point-Function Obfuscation: The separation result also rules out the black-box construction of qOWFs from point-function obfuscation, as the constructed oracle admits point-function obfuscation but no qOWFs.

4. Significance and Claims

The paper claims to provide a "comprehensive picture" of the relationship between qOWFs and qPKE in the quantum setting with classical communication.

Refutation of Necessity: The primary significance is the negative answer to Open Problem 1. The authors demonstrate that qOWFs are not necessary for qPKE, even when restricted to classical keys and ciphertexts. This contrasts with the classical intuition where PKE is often viewed as strictly stronger than OWFs, yet the existence of PKE without OWFs (in a black-box sense) was previously an open question in the quantum realm.
Complexity of the Quantum Landscape: The results highlight a fundamental difference between classical and quantum cryptography. In the classical world, a hierarchical structure often links PKE to OWFs. In the quantum world, the authors show a "two-way black-box separation" between perfectly correct qPKE and qOWF1/qOWF2, indicating a more complex and less hierarchical landscape.
Weakening Assumptions: By constructing qPKE from EV-OWPuzz and qiO, the paper suggests that the cryptographic assumptions required for public-key encryption in the quantum world can be weakened to the level of puzzles, provided one has access to quantum indistinguishability obfuscation.
Robustness of Separation: The separation holds even against adversaries with access to unitary, inverse, transpose, and complex-conjugate operations of the oracle, ruling out a broad class of black-box constructions.

The authors conclude that while qOWFs are not necessary for qPKE, the weakest notion (qOWF3) is equivalent to EV-OWPuzz, which is implied by qPKE. Thus, the necessity of "one-wayness" for qPKE depends critically on the specific definition of determinism and input sampling used.