For twenty years, quantum key agreement has presented a hard problem. In a paper posted on Cornell University's arXiv on 2026-08-18, cryptographers confront it directly. It is straightforward to design protocols that look secure against classical eavesdroppers, but proving that no quantum protocol can achieve a task is much harder. In the quantum random oracle model, or QROM, honest parties and adversaries may query a random function in quantum superposition. That one feature invalidates many classical impossibility proofs and has left the security boundaries of quantum key agreement unsettled. [arXiv:2608.17610]
In a paper posted on Cornell University's arXiv on 2026-08-18, cryptographers make progress by constructing the first unconditional attacks in restricted settings. The paper targets imperfectly complete quantum-computation, classical-communication key agreement, the kind where honest parties may fail with small probability even when no adversary is present.
Key agreement is the process by which two parties, Alice and Bob, agree on a secret key over a public channel. In QCCC, the computation is quantum but the communication is classical. Perfectly complete protocols always succeed; imperfectly complete protocols may fail with non-negligible probability. The quantum random oracle model adds a public hash function that all parties can query, including in superposition.
Why was this hard? A random oracle is supposed to hide information because each query answer is independent. But quantum queries can be entangled with the oracle, and a computationally unbounded attacker cannot simply be assumed polynomial. The new result must show that even an unbounded attacker needs only poly(Ξ») queries to recover the key. That requires combining learning from heavy queries with reprogramming of oracle responses.
The Core Finding
The authors construct the first unconditional attacks on quantum key agreement in two restricted QROM settings. In the two-message setting, Alice makes only classical queries to the oracle in the first round and sends a classical message to Bob; in the second round both parties may perform arbitrary quantum computation, make quantum queries, and send a quantum state. In the round-independent setting, Alice and Bob share classical communication and make only classical queries in all but the final round. In both settings, a computationally unbounded attacker recovers the key with poly(Ξ») queries whenever the honest query bound is at most poly(Ξ») and the valid agreement probability is inverse-polynomial.
βWe construct the first unconditional attacks on quantum key agreement in the following restricted settings.β
Think of it like a lockpicker who cannot see the key but can count which pins the honest users touch most often, then rewrites the lock's response to force the key to turn. The attack combines heavy-query learning from Austrin et al. (CRYPTO 2022) with reprogramming techniques from Katz and Sela ([arXiv:2401.14319]).
The consequence is sharp. The paper rules out imperfectly correct quantum public-key encryption for classical messages whose length is bounded by a polynomial in Ξ» in the QROM when key generation has classical oracle access, even if encryption, decryption, and the ciphertext are quantum. The one-bit case applies to the imperfectly correct public-key encryption obtained from two-round OSP by Bartusek and Khurana (CRYPTO 2025) whenever the classical OSP sender makes only classical random-oracle queries.
The State of the Field
Before this work, the main impossibility tool for key agreement in the random oracle model came from Barak and Mahmoody (CRYPTO 2009; J. Cryptology 2017), which handled classical random oracles. Extending that to quantum settings has been difficult because quantum queries can be made in superposition and intermediate quantum states may encode oracle answers.
Austrin et al. (CRYPTO 2022) introduced heavy-query learning, and Katz and Sela ([arXiv:2401.14319]) developed reprogramming arguments, but these tools had not been assembled to attack imperfectly complete QCCC key agreement. This paper relaxes the completeness requirement. Many prior impossibility arguments assumed perfect completeness, meaning honest parties always agree if no adversary is present. Real protocols may fail with small probability, and attacking imperfectly complete schemes requires handling noisy transcripts.
The broader quantum computing landscape makes these cryptographic boundary questions urgent. Quantum error correction has moved from theory to experimental practice: Google's 2024 Willow chip demonstrated below-threshold surface code error correction on 105 qubits, and IBM's road map continues to push logical qubit counts upward. As fault tolerant quantum computing becomes less speculative, the question of what quantum communication can and cannot achieve becomes practical, not merely theoretical.
From Lab to Reality
For scientists, the result opens a path toward the full impossibility of imperfectly complete QCCC key agreement in the QROM. The restrictionsβclassical first-round queries and messages in one setting, classical queries until the final round in the otherβare now the main obstacles to remove. Each restriction identifies exactly which quantum power prevents current learning techniques from succeeding.
For engineers, this is a negative design constraint. Quantum public-key encryption for classical messages with classical key generation or classical random-oracle access cannot be proven secure in the QROM under these assumptions. That does not affect all quantum key distribution, but it narrows the design space for QCCC key agreement and prevents wasted effort on schemes that fit these profiles.
For investors, the affected market is quantum-safe cryptography and quantum networking rather than quantum error correction hardware directly. This paper removes a class of attempted products: schemes that combine classical key generation with quantum ciphertexts. That is valuable because standards bodies and startup investors can redirect capital toward designs that do not rely on the ruled-out profiles. The quantum error correction market, while separate, continues to attract hardware investment as surface code and logical qubit teams scale toward fault tolerant quantum computing.
What Still Needs to Happen
Two technical challenges remain. First, the two-message attack assumes Alice's first-round oracle queries and her first message are classical. Lifting this to quantum first-round queries or a quantum first message would require new learning methods that can extract heavy queries from superposition without collapsing useful information. Second, the round-independent attack assumes classical queries in all but the final round. Extending it to quantum queries in earlier rounds would require controlling the entanglement between the oracle and the honest parties.
The likely route forward is to strengthen heavy-query learning. Austrin et al. laid the foundation; Katz and Sela showed how to reprogram after learning. The authors of this paper combine those techniques but leave the fully quantum case open. No false optimism: a complete impossibility result for QCCC key agreement in the QROM may be years away, and it may require techniques beyond current query learning.
Researchers working on adjacent problems include the cryptography groups that produced the underlying tools, particularly the authors of the CRYPTO 2022 heavy-query learning paper and the 2024 reprogramming paper. Their ongoing work on quantum random oracle separations is the most relevant to closing these gaps.
The Bottom Line
In short: quantum error correction is not the only boundary moving in quantum computing; this paper gives the first unconditional poly(Ξ»)-query attacks ruling out imperfectly complete QCCC key agreement in two restricted QROM settings.
The result changes the cryptographic map by eliminating a class of public-key encryption schemes and clarifying which quantum powers make key agreement hard to prove impossible.