Query complexity of passive attacks on perfectly complete quantum key agreement

In the Boolean-output quantum random oracle model, can a passive eavesdropper recover the key of every finite-round, perfectly complete protocol with quantum local operations, classical communication and independent initial private states using polynomially many oracle queries?

Why it matters and what counts as progress

Why it matters: This tests query-based security even when the attacker has unbounded computation.

What counts as progress: An unconditional arbitrary-round polynomial-query attack in this model, or a protocol escaping such attacks; computation time and query count must remain distinct.

How the problem developed

2022 · Partial result [1][2]
Austrin, Chung, Chung, Fu, Lin, and Mahmoody Gave quantum-random-oracle attacks for restricted QCCC settings and a polynomial classical attack for general perfectly complete protocols under the Polynomial Compatibility Conjecture.
4 Aug 2026 · Reported claim [2]
Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu; GPT-5.6 Sol The preprint claims a certainty-success classical eavesdropper using O((qA+qB)^5) oracle queries against arbitrary-round perfectly complete QCCC protocols, without the conjecture used in the earlier general result.

AI contribution

Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM

Longcheng Li, Qian Li, Xingjian Li, Qipeng Liu

In the Boolean-output quantum random oracle model, every finite-round perfectly complete key-agreement protocol with quantum local operations, independent initial private states and classical communication admits a passive eavesdropper that recovers the key with certainty using O((q_A+q_B)^5) classical oracle queries. The eavesdropper may use unbounded computation.

AI involvementAI-autonomous

ImportanceNotable

Technical verificationFormal (human)

Human understandingFull