⚛️ quantum physics

Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM

This paper establishes the first unconditional attacks on quantum key agreement in the Quantum Random Oracle Model (QROM) for specific restricted settings involving classical queries and communication, thereby proving the impossibility of imperfectly complete quantum public-key encryption for classical messages under these conditions.

Original authors: Fuyuki Kitagawa, Ryo Nishimaki, Agi Villanyi, Takashi Yamakawa

Published 2026-08-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Fuyuki Kitagawa, Ryo Nishimaki, Agi Villanyi, 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

In the digital world, two strangers often need to agree on a secret code to communicate safely, even though they have never met and are talking over a channel that anyone can listen to. For decades, the standard way to do this relied on a mathematical puzzle: one person creates a difficult problem, the other solves it, and the solution becomes their shared secret. A listener trying to eavesdrop would have to solve the same puzzle, but the laws of classical physics suggest they would need to do vastly more work than the honest participants, making the secret safe. However, the rise of quantum computers, which can process information in ways that classical machines cannot, has thrown this assumption into doubt. Scientists have long wondered if quantum mechanics allows two people to create a secret key that is completely safe from any eavesdropper, even one with unlimited computing power, or if there is a fundamental limit to how secure such a system can be.

A team of researchers has now taken a significant step toward answering that question by proving that a specific type of quantum secret-sharing system is fundamentally impossible to make secure. They focused on a scenario where two parties, Alice and Bob, try to agree on a key while a third party, Eve, listens in. In their model, Alice and Bob are allowed to use powerful quantum computers and can send messages that exist in a fragile quantum state, but there is a catch: in the early stages of their conversation, Alice is restricted to asking simple, classical questions about a shared random source. The researchers demonstrated that under these conditions, an eavesdropper with unlimited computing power can always break the system. They showed that Eve can learn the secret key with a number of attempts that is manageable, provided the honest parties are also limited to a manageable number of attempts. This finding rules out the possibility of creating a secure quantum public-key encryption system for short messages if the key generation process relies on those early, simple questions, even if the rest of the system uses advanced quantum technology.

The researchers built their proof by developing a new method for an attacker to learn the secret. Imagine the conversation between Alice and Bob as a series of steps where they ask questions to a giant, random dictionary to generate their key. In the first step, Alice asks a few questions and sends a message to Bob. The researchers showed that an attacker can watch this first message and then systematically guess which questions Alice likely asked. By focusing on the questions that are most probable, the attacker can reconstruct a partial map of the dictionary that Alice used. Once this map is built, the attacker can simulate Alice's entire process, including her final quantum calculations, to figure out the secret key without ever needing to know the full dictionary. This technique works because, once the initial questions are fixed, the rest of the system behaves in a predictable way that the attacker can replicate.

This attack is not just a theoretical possibility; the researchers provided a concrete recipe for how an attacker would do it. They proved that if the honest parties make a reasonable number of queries to the random source, the attacker can recover the key with a similar number of queries. The success rate of this attack is directly tied to how often the honest parties successfully agree on a key. If Alice and Bob agree on a key with a probability that is not vanishingly small, the attacker can also succeed with a high probability. This result is a strong negative finding: it establishes that you cannot build a secure system in this specific setting. The researchers extended this logic to more complex, multi-round conversations where Alice and Bob exchange many messages before the final quantum step. They found that as long as all the early messages and questions are classical, the attacker can still break the system, regardless of how many rounds of conversation occur.

The implications of this work are significant for the future of quantum cryptography. It clarifies the boundaries of what is possible. While quantum computers offer new ways to protect information, they do not offer a magic shield that makes all forms of key agreement secure. Specifically, if a system relies on a classical key generation phase, it remains vulnerable to a powerful eavesdropper. The researchers also applied their findings to a specific type of encryption called quantum public-key encryption, where the public key is used to encrypt a message. They showed that if the key generation process uses only classical queries, such a system cannot be secure against an attacker with unlimited resources, even if the encryption and decryption steps are fully quantum. This means that for these systems to be truly secure, the key generation process itself must involve quantum queries, a much more difficult requirement to implement.

The study does not claim to have broken every form of quantum cryptography, nor does it suggest that all quantum communication is unsafe. Instead, it draws a precise line in the sand. It proves that in the specific world where early interactions are classical, the dream of an unbreakable key agreement is an impossibility. The researchers achieved this by combining two powerful mathematical techniques: one that identifies the most likely paths an attacker could take, and another that allows the attacker to reprogram the random source to match their simulation. By weaving these techniques together, they created a scenario where the attacker's view of the system becomes indistinguishable from the honest parties' view, allowing them to steal the secret. This work serves as a crucial guide for cryptographers, showing them exactly where not to look for security and pointing them toward the more complex, fully quantum approaches that might still hold the key to true safety.

Technical Summary: Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM

1. Problem Statement

The paper addresses the security of Quantum-Computation, Classical-Communication (QCCC) key agreement protocols in the Quantum Random Oracle Model (QROM). Specifically, it investigates the feasibility of imperfectly complete protocols, where honest parties agree on a valid key with only inverse-polynomial probability ( $\alpha > 0$ ), rather than with certainty (perfect completeness).

Prior work had established unconditional impossibility results for perfectly complete QCCC key agreement and Quantum Public-Key Encryption (QPKE) under various restrictions. However, the case of imperfectly complete protocols with unrestricted quantum oracle access by honest parties remained open. A significant barrier identified by Austrin et al. (2022) suggests that if the "Simulation Conjecture" holds, classical attackers cannot break such protocols. This paper bypasses the need for this conjecture by restricting the honest parties' oracle access in specific ways, allowing for unconditional attacks by computationally unbounded quantum adversaries.

2. Methodology and Technical Approach

The authors construct unconditional attacks using a combination of heavy-query learning and random reprogramming techniques. The core strategy involves an attacker (Eve) who intercepts communication, learns a "heavy" set of oracle queries made by the honest parties, and then resamples the honest parties' views conditioned on this partial oracle to recover the key.

2.1 The Two-Message Attack

The first setting considers a two-round protocol where:

Alice makes only classical queries to the oracle in the first round and sends a classical message ( $m_1$ ) to Bob.
Bob may perform arbitrary quantum computation, make quantum queries, and send a quantum message ( $\Psi$ ).
Alice may perform quantum computation and make quantum queries in the final round.

Attack Mechanism:

Heavy-Query Learning: Upon receiving $m_1$ , Eve uses a learning algorithm (based on Austrin et al. and Katz & Sela) to identify "heavy" inputs—values likely to be queried by Alice in the first round, conditioned on $m_1$ . She builds a partial oracle $h$ by querying these heavy inputs.
Conditioned Resampling: Because Alice's first-round queries are classical, once $m_1$ and the transcript of answers $h$ are fixed, Alice's residual quantum state depends only on these classical variables. Eve can therefore sample a fresh view $(T'_A, S'_A)$ from the conditional distribution $\omega_{m_1, h}$ .
Reprogramming: Eve intercepts Bob's quantum message $\Psi$ . She runs Alice's final algorithm on the sampled state $S'_A$ and $\Psi$ , using a reprogrammed oracle $H[T'_A]$ that agrees with the sampled transcript $T'_A$ on its domain and behaves like the original oracle elsewhere.
Analysis: The security loss is bounded by the Random Reprogramming Lemma (Katz & Sela). Since the probability of Alice querying a point outside the learned set $Dom(h)$ is small (controlled by a parameter $\delta$ ), the reprogramming does not significantly alter the acceptance probability of the quantum algorithm.

2.2 The Multi-Round Attack

The second setting extends the result to protocols with an arbitrary number of rounds, provided there is a classical-communication prefix:

All messages and oracle queries during the prefix are classical.
Parties may retain quantum states and perform local quantum computation.
The final round involves a possibly quantum message from Bob and Alice's final quantum computation.

Attack Mechanism:

Classical Simulation: Eve treats the classical prefix as an auxiliary classical protocol. Since she is computationally unbounded, she can exactly simulate the classical views of Alice and Bob, including their conditional residual states.
Barak-Mahmoody Learner: Eve applies the Barak-Mahmoody learner (originally for classical protocols) to the simulated classical views to learn a partial oracle $h$ and ensure that the views of Alice and Bob are approximately independent (product state) conditioned on $h$ .
Resampling and Coupling: Eve samples independent views for Alice and Bob conditioned on $h$ . She then couples these views with a consistent oracle by sampling a base oracle for Bob and reprogramming it for Alice.
Final Attack: Eve intercepts the final quantum message and runs Alice's final algorithm on the sampled state with the reprogrammed oracle.

3. Key Contributions and Results

3.1 Main Theorems

Theorem 1.1 (Two-Message Attack): For any protocol where Alice's first-stage queries and message are classical, there exists a computationally unbounded quantum attacker that recovers Bob's key with probability $> \alpha/2$ using $O(\text{poly}(q, 1/\alpha))$ queries. The attacker makes classical queries before Bob's response and quantum queries after.
Theorem 1.2 (Multi-Round Attack): For protocols with a classical-query prefix of arbitrary length, a similar attack exists. The query complexity depends on the total number of prefix queries but is independent of the number of rounds.
Theorem 1.3 (QPKE Attack): These results imply that Quantum Public-Key Encryption (QPKE) for classical messages (of polynomial length) with classical-query key generation cannot be IND-CPA secure against computationally unbounded attackers making polynomially many queries, even if encryption, decryption, and ciphertexts are quantum.

3.2 Specific Applications

Imperfectly Correct PKE from OSP: The paper applies its results to the PKE scheme derived from Oblivious State Preparation (OSP) by Bartusek and Khurana (CRYPTO 2025). It shows that if the OSP sender makes only classical random-oracle queries, the resulting PKE is insecure in the QROM, specifically when the underlying OSP protocol is negligibly incorrect (i.e., imperfectly complete).
Classical Eavesdropping: If the entire protocol (including Bob's response) is classical, the attack reduces to a passive classical eavesdropping attack.

4. Significance and Claims

The paper claims to make progress toward the impossibility of imperfectly complete QCCC key agreement by providing the first unconditional attacks in restricted settings where honest parties have unrestricted quantum oracle access in later stages.

Overcoming the Simulation Barrier: The authors note that a fully general classical attack on imperfectly complete QCCC would require disproving the Simulation Conjecture. By restricting the honest parties' early queries to be classical, this work bypasses that barrier, allowing for unconditional attacks without assuming the conjecture is false.
Tightness of Restrictions: The results highlight a critical trade-off: the attacks rely on the fact that early oracle queries are classical. If the prefix queries were quantum, the parties would be entangled with the oracle, preventing the "resampling" technique used here. The authors explicitly state that extending these results to quantum queries in the prefix requires novel techniques and is left as future work.
Security Notion: The paper defines a specific security notion (interception key-recovery) which is stronger than standard CC1QM security in the sense that it only requires the attacker to recover the key, not to simulate a valid state for Alice. However, this is sufficient to break the IND-CPA security of the derived QPKE schemes.

In summary, the paper demonstrates that classical oracle access during the initial phases of a key agreement protocol is a fatal weakness for imperfectly complete schemes in the QROM, rendering them insecure against unbounded quantum attackers even if the rest of the protocol is fully quantum.