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

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

Problem Statement
This paper addresses the fundamental limits of Quantum Key Agreement (QKA) within the Quantum Random Oracle Model (QROM). Specifically, it investigates whether two parties, Alice and Bob, can establish a shared secret key with perfect completeness (probability 1) using only classical communication, while performing local quantum computations and making quantum queries to a random oracle. The setting is the Quantum Computation with Classical Communication (QCCC) model. The central question is whether such protocols can be secure against a passive eavesdropper who observes the classical transcript and has access to the same oracle, assuming the protocol is constructed from quantumly secure one-way functions (OWFs) in a black-box manner.

Previous work had established separations for classical protocols and specific quantum cases, but gaps remained for general, multi-round QCCC protocols. Notably, Austrin et al. (CRYPTO 22) provided a polynomial-query attack under an unproven "Polynomial Compatibility Conjecture," while Li et al. (CRYPTO 26) resolved the case for two-round protocols unconditionally. This paper seeks to close the gap for arbitrary-round protocols without relying on unproven conjectures.

Methodology
The authors employ a combination of quantum query complexity theory, polynomial analysis over Boolean functions, and decision tree complexity to construct an unconditional attack. The core methodology proceeds as follows:

1. Polynomial Factorization of Transcript Probabilities:
   By fixing the complete classical transcript $t$ and the oracle truth table $z$, the probability of Alice and Bob outputting specific keys $a$ and $b$ is shown to factorize into $A_{t,a}(z) \cdot B_{t,b}(z)$. Here, $A$ and $B$ are non-negative functions representing the local execution probabilities of Alice and Bob, respectively.

   • Using the quantum polynomial method (specifically Lemma 2.2 from [BBC+01]), the authors bound the degrees of these functions: $\deg(A_{t,a}) \le 2q_A$ and $\deg(B_{t,b}) \le 2q_B$, where $q_A$ and $q_B$ are the number of quantum queries made by the honest parties.

2. Disjoint Key Supports via Perfect Completeness:
   The condition of perfect completeness ($Pr[K_A = K_B] = 1$) implies that for any valid transcript $t$ and oracle $z$, the product $A_{t,k}(z)B_{t,\ell}(z)$ must be zero for all distinct keys $k \neq \ell$.

   • Defining $C_{t,k}(z) = A_{t,k}(z)B_{t,k}(z)$, the authors demonstrate that the supports of these polynomials are pairwise disjoint on the Boolean cube $\{0,1\}^N$.
   • This disjointness, combined with the fact that a non-zero multilinear polynomial of degree $d$ must be non-zero on at least $2^{N-d}$ points (Lemma 2.1), limits the number of candidate keys $|K_t|$ to at most $2^d$, where $d = 2(q_A + q_B)$.

3. Decision Tree for Disjoint Polynomials:
   The critical technical contribution is a deterministic procedure (Lemma 3.5) to identify which of two disjoint-support polynomials, $p$ and $q$, is non-zero at a specific oracle $z$, given the promise that one is non-zero.

   • The procedure uses a recursive decision tree. In each step, it identifies a set of $O(d^3)$ oracle bits such that querying them either determines the answer or strictly reduces the degree of one of the polynomials.
   • This reduction relies on a discrete Markov inequality (Lemma 2.3) applied to a constructed polynomial $r$ derived from the difference of squares of the inputs.
   • The depth of this decision tree is shown to be $O(d^4)$.

4. Binary Search Strategy:
   The eavesdropper performs a balanced binary search over the set of candidate keys $K_t$ (size $\le 2^d$). At each level, the candidate set is split into two halves, and the sums of the corresponding polynomials ($P$ and $Q$) are formed. Since the supports are disjoint, exactly one of $P(z)$ or $Q(z)$ is non-zero. The decision tree from step 3 is used to determine which half contains the correct key.

   • With at most $d$ levels of binary search and $O(d^4)$ queries per level, the total query complexity is $O(d^5)$.

Key Contributions and Results

• Unconditional Impossibility: The paper proves that it is impossible to construct perfectly complete, finite-round QCCC key agreement protocols from quantumly secure one-way functions (OWFs) in a black-box manner in the QROM. This result is unconditional, removing the "Polynomial Compatibility Conjecture" required by previous work [ACC+22].
• Query Complexity Bound: The authors construct an eavesdropper that recovers the shared key with probability 1 using $O((q_A + q_B)^5)$ classical oracle queries.
  • This bound is independent of the number of communication rounds, the transcript length, the key length, and the oracle domain size.
  • Crucially, while the honest parties may use superposition queries, the eavesdropper only requires classical queries.
• Generalization: The result generalizes previous findings on two-round protocols [LLLL26] to arbitrary rounds and allows parties to maintain arbitrary quantum states between communication stages, a scenario not covered by prior unconditional results.

Significance and Claims
The paper claims to provide a definitive negative answer to the security of many-round, perfectly complete QKA in the QROM.

• Theoretical Impact: It establishes a strict black-box separation between quantumly secure one-way functions and perfectly complete key agreement in the QCCC setting.
• Methodological Advance: The proof introduces a novel application of polynomial degree reduction and decision tree complexity to the problem of key recovery, specifically handling the case where honest parties use quantum superposition but the attacker is restricted to classical queries.
• Limitations: The authors explicitly state that the proof relies on perfect completeness. Extending this result to protocols with imperfect completeness (where parties might fail to agree with some small probability) would require significantly different ideas and is not covered by this work.
• Attribution: The paper notes that the core proof was discovered by GPT-5.6 Sol Ultra in a single conversation, with the human authors responsible for verification, refinement, and the final exposition.

In summary, the paper demonstrates that in the QROM, the combination of classical communication and perfect completeness is insufficient to protect key agreement from an efficient classical eavesdropper, regardless of the number of rounds or the complexity of the local quantum computations.