{"id":"0c76d739-9e73-4243-821a-31e0590e6201","arxiv_id":"2608.03824","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A polynomial-query classical eavesdropper recovers the shared key with certainty in every perfectly complete many-round QCCC key agreement protocol relative to a quantum-accessible random oracle.","lead":"This paper proves that an eavesdropper can always recover the secret key in any perfectly complete key agreement protocol that uses classical messages and a quantum-accessible random oracle, even if Alice and Bob may query the oracle in superposition. The attack uses only polynomially many classical oracle queries, works for arbitrarily many rounds, and succeeds with certainty.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: proof is internally coherent; the perfect-completeness assumption is an explicit scope limitation, not a hidden flaw.","rationale":"I examined the proof line by line. For Theorem 3.1 to hold, four things must be true: transcript rectangularity, pointwise disjointness of key polynomials, the candidate-count bound, and the separator lemma. Each is supported. A subtle point in Lemma 3.5 is the composition of s with block-wise affine maps: one might worry that multiple variables in the same block raise the degree of r. After multilinearization, each block contributes a univariate polynomial of degree at most 1, and a monomial of s can touch at most its own degree many blocks, so deg(r) <= deg(s) <= 2D holds. The maximal family of pairwise-disjoint maximum monomials and the query set S indeed force a strict degree decrease on every branch, giving depth O(d^4). The only genuinely restrictive assumption is perfect completeness, but that is explicit in the theorem statement and in the paper's declared scope. The reader's ACCEPT verdict is consistent with my read; no verdict change is warranted.","tokens_in":8142,"tokens_out":30161,"duration_ms":373441,"concrete_test":"Independently verify Lemma 3.5 for small parameters: exhaustively enumerate all pairs of degree-<=2 multilinear polynomials with disjoint supports on N<=6 and check that the described decision tree (or an optimal decision tree) has depth bounded by a small constant; also re-derive the degree-drop claim and the deg(r)<=deg(s) bound in the proof of Lemma 3.5. If any pair requires more queries or the degree bound fails, the separator lemma is unsound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. I read the proof in good faith and checked the main chain: Lemma 3.2 transcript rectangularity, Lemma 3.3 pointwise disjointness from exact completeness, Lemma 3.4 candidate-key bound, Lemma 3.5 disjoint-support separator, and the final binary search. Each step is internally coherent. The most fragile premise is indeed perfect completeness: Lemma 3.3's Eq. (2) and the pointwise disjointness of the C_{t,k} supports depend on exact Pr[K_A=K_B]=1, and the paper explicitly states that imperfect completeness would require new ideas. This is a scope limitation of the theorem, not a flaw in the theorem as stated. The separator lemma (Lemma 3.5) is the least standard component; its degree-drop argument and application of Lemma 2.3 survive scrutiny, including the composition step deg(r) <= deg(s) after multilinearization. No circular reasoning or invented entities found. The AI-generated disclosure does not affect mathematical correctness.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves a query-complexity impossibility result for perfectly complete QCCC key-agreement protocols in the QROM. For any finite-round protocol in which Alice and Bob exchange only classical messages and make q_A and q_B quantum queries to a Boolean random oracle, the authors construct a passive eavesdropper that, after seeing the public transcript, recovers the agreed key with certainty using O((q_A+q_B)^5) classical oracle queries. The proof combines transcript rectangularity (Lemma 3.2), pointwise disjointness of key-polynomial supports from exact completeness (Lemma 3.3), an upper bound of 2^d on candidate keys (Lemma 3.4), and a new deterministic decision tree separating two degree-d polynomials with disjoint supports (Lemma 3.5), followed by a binary search. The result is independent of the number of rounds, transcript length, and key length, and removes the conjecture dependence of [ACC+22] while extending the two-round result [LLLL26].","tokens_in":8332,"tokens_out":23608,"duration_ms":262901,"significance":"If correct, this is a significant advance: it establishes that no black-box construction of perfectly complete many-round key agreement from quantumly secure OWFs can exist in the QROM, settling a natural open question left by [ACC+22] and [LLLL26]. The proof is self-contained, the query bound is explicit, and the main limitation—that perfect completeness is essential—is stated clearly in Section 1.1. The decision-tree lemma is novel and its proof is checkable. The paper also gives explicit credit for the AI-assisted discovery; I do not see any effect of that provenance on the mathematical content.","major_comments":[],"minor_comments":[{"comment":"Minor terminology and grammar: 'perfect complete' should be 'perfectly complete' throughout; 'Previous results only applies' should be 'apply'.","section":"Abstract / Section 1.1"},{"comment":"The abstract and introduction advertise a black-box separation from quantumly secure OWFs, but Theorem 3.1 is stated only as a query attack. A short corollary making the standard lifting explicit (the random oracle is a quantumly secure OWF, so a black-box construction would contradict Theorem 3.1) would tie the advertised conclusion to the formal statement.","section":"Section 1.1 and Theorem 3.1"},{"comment":"The case q(z*) != 0 is dismissed as symmetric. Since this lemma is the technical core, please provide the symmetric construction explicitly (or state formally that it is identical with p and q interchanged) to help the reader verify the degree-drop claim in both cases.","section":"Section 3.4, Lemma 3.5"},{"comment":"The model assumes finite transcript and key alphabets but does not restrict private randomness. The purification argument should either assume finite private randomness or explain how continuous/unbounded local randomness is integrated into the nonnegative factors A and B without changing the degree bounds.","section":"Section 2.2 / Lemma 3.2"},{"comment":"Typo: 'The operators composes' should be 'compose'.","section":"Lemma 3.2 proof"}],"recommendation":"minor_revision","confidential_remarks":"The mathematical core is sound; I found no load-bearing flaw. The only technical dependency I could not check directly is Lemma 2.3, attributed to the future reference [KKDWY26]; the editor may wish to confirm that the discrete Markov inequality appears there as stated. The abstract's credit to 'GPT-5.6 Sol Ultra' is unusual for a journal but is an editorial-policy matter, not a correctness issue, since the authors state they verified the proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Longcheng Li, Qian Li, Xingjian Li, Qipeng Liu: Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM.\n\nThe one-liner: if this proof holds up, it closes the many-round version of a major open problem in QROM black-box separations—a round-independent O((qA+qB)^5)-query classical attack on any perfectly complete QCCC key agreement from a Boolean random oracle, with no conjecture. That is a real step up from ACC+22 (which needed Polynomial Compatibility) and from LLLL26 (which handled two rounds, classical states, and a quantum-query adversary).\n\nThe paper does several things well. The transcript-rectangularity lemma (3.2) is standard but cleanly executed; the disjoint-support consequence of exact completeness (3.3) is the right structural observation; the candidate-counting via Nisan-Szegedy (3.4) is a neat use of the degree bound. The most interesting new ingredient is Lemma 3.5—the O(d^4)-depth decision tree that finds which of two disjoint-support degree-d polynomials is nonzero. I checked the degree-drop argument: the maximal pairwise-disjoint family of maximum monomials, the flips on the E_i blocks, and the discrete Markov inequality from KKDWY26 combine correctly, including the deg(r) <= deg(s) step after multilinearization. I don't see a fatal gap.\n\nThe soft spots are real but not fatal. The perfect-completeness assumption is load-bearing: without exact Pr[K_A=K_B]=1, Eq. (2) does not give pointwise disjoint supports, and the authors say plainly that imperfect completeness would need new ideas. That is a scope boundary, not a defect in the theorem as stated. The separator lemma is the least standard component; it deserves independent verification, especially the claim that every stage decreases the total degree on nonterminal branches—I believe that is correct because the queried set S meets every maximum monomial. There is no machine-checked formalization, so I would want a careful referee to check constants and the maximal-family construction. The paper leans heavily on LLLL24-26 and KKDWY26; those citations look relevant, and self-citation is not a problem when the prior results are real, though one should confirm they are all public.\n\nThe AI-assisted provenance (GPT-5.6) is worth a note but not a mathematical objection; the authors state they verified everything. I would not desk-reject on those grounds.\n\nVerdict: This deserves peer review at a strong theory venue. If Lemma 3.5 passes a second pair of eyes, the result is publishable as-is or with minor revisions. I would cite it and would bring it to a reading group.","headline":"A genuine many-round QROM key-agreement impossibility result with a believable polynomial-method proof; the perfect-completeness assumption is explicit and the separator lemma is the main thing to verify.","tokens_in":8839,"tokens_out":3564,"would_cite":true,"duration_ms":37165,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P94","94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"Perfectly complete many-round key agreement is impossible in the QROM","keywords":["quantum random oracle model","key agreement","QCCC","perfect completeness","black-box separation","one-way functions","quantum query complexity","polynomial method"],"falsifier":"Find or construct a perfectly complete QCCC key-agreement protocol for which the optimal passive eavesdropper needs more than c(q_A+q_B)^5 classical oracle queries for a universal constant c; a direct way to test the core lemma is to search computationally for degree-d disjoint-support Boolean polynomials p,q such that every deterministic decision tree deciding which is nonzero at a hidden point has depth above c·d^4, which would refute Lemma 3.5 and, with it, Theorem 3.1.","tokens_in":8022,"feed_emoji":"🔑","tokens_out":7700,"duration_ms":86669,"temperature":0.7,"pith_summary":"This paper proves that no perfectly complete quantum key-agreement protocol with classical messages can hide its key from a passive eavesdropper in the quantum random oracle model. If Alice and Bob make at most q_A and q_B quantum oracle queries and always agree on their key, an eavesdropper who sees the public transcript can recover the same key with certainty using O((q_A+q_B)^5) classical oracle queries. The query bound is independent of the number of rounds, transcript length, key length, and oracle-domain size. A corollary is that quantumly secure one-way functions cannot yield many-round key agreement by any black-box construction in this model. Previous results covered only two rounds, or depended on an unproven conjecture.","feed_headline":"Eavesdropper wins against all perfectly complete key agreement","feed_subtitle":"A passive listener using O((q_A+q_B)^5) classical oracle queries recovers the shared key with certainty.","key_machinery":"Transcript rectangularity (Lemma 3.2) is the central factorization: because all messages are classical, the probability of transcript t and keys a,b under oracle z factors as A_{t,a}(z) B_{t,b}(z), with A_{t,a} and B_{t,b} nonnegative polynomials of degree at most 2q_A and 2q_B (quantum polynomial method). Perfect completeness forces every cross-key product A_{t,a}(z)B_{t,b}(z), a≠b, to vanish on every z, so the degree-d polynomials C_{t,k}=A_{t,k}B_{t,k} have pairwise disjoint supports. Since a nonzero degree-d multilinear polynomial on the Boolean cube is nonzero on at least 2^{N-d} points, the number of candidate keys per transcript is at most 2^d. The inner technical engine is Lemma 3.5,","core_discovery":"The paper's central claim is Theorem 3.1: for every finite-round QCCC key-agreement protocol that is perfectly complete, after any transcript t that has positive probability under the actual Boolean random oracle z, a passive eavesdropper can recover the unique key k with certainty. The eavesdropper computes the finite set of candidate keys from the public transcript using unbounded computation and zero oracle queries, then runs a balanced binary search over at most 2^d candidates, where d = 2(q_A+q_B). Each search step invokes a deterministic decision tree that separates two disjoint-support degree-d polynomials using O(d^4) classical oracle-bit queries, giving O(d^5) total queries. The att","pith_inferences":["Not claimed by the paper: the exact-vanishing structure suggests that a protocol with only negligible completeness error might evade this attack; testing that would require replacing disjoint supports with approximate disjointness and would likely need new polynomial tools.","A direct corollary of the separator lemma, not pursued in the paper, is that any promise problem asking which of two disjoint-support degree-d polynomials is nonzero at a hidden input has O(d^4) classical query complexity; this statement could be reused in other black-box separation settings.","The proof leaves open protocols with any quantum communication between the parties; a concrete next test is whether a single quantum message between Alice and Bob already creates non-rectangular transcripts and blocks the attack.","Because the eavesdropper is computationally unbounded, the result is purely about query complexity; turning it into a computational attack would require making the separator and binary-search steps efficient, which the paper does not address."],"forward_implications":["No black-box construction of perfectly complete many-round key agreement from quantum-secure one-way functions can exist in the QROM; the eavesdropping attack is unconditional and round-independent.","The number of rounds provides no security: the attack's query cost depends only on the honest parties' total quantum query complexity, not on how many classical messages are exchanged.","Allowing the honest parties to keep arbitrary quantum states between rounds does not help, as long as the communicated messages remain classical.","The eavesdropper uses only classical oracle queries even though the honest parties may query the oracle in superposition, giving a strong quantum-versus-classical query separation.","The result removes the unproven conjecture that earlier many-round attacks relied on and extends the two-round unconditional attack to arbitrary finite rounds."],"supporting_citations":[{"why":"Supplies the quantum polynomial method: the acceptance probability of a d-query quantum algorithm has degree at most 2d, used to bound deg(A_{t,a}) and deg(B_{t,b}).","marker":"[BBC+01]"},{"why":"Supplies the support lower bound for degree-d Boolean polynomials and the discrete Markov inequality behind the degree-decrease argument in the separator tree.","marker":"[NS94]"},{"why":"The earlier many-round QCCC attack that required the Polynomial Compatibility Conjecture; this paper removes that conjecture.","marker":"[ACC+22]"},{"why":"The prior two-round unconditional attack on quantum PKE that the present round-independent attack extends.","marker":"[LLLL26]"},{"why":"Provides the version of the discrete Markov inequality (Lemma 2.3) used to bound the number of maximum monomials in the separator tree.","marker":"[KKDWY26]"}],"fun_headline_variants":["Perfect key agreement doomed: eavesdropper always wins","Quantum key agreement impossible under perfect completeness","Eavesdropper recovers key from any classic-message QKA","No perfect QKA: eavesdropper finds key in O(q^5)","Impossibility: perfect QKA cannot exist in QROM"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing premise is perfect completeness: Alice and Bob must agree with probability exactly one, so the cross-key probabilities vanish for every oracle and transcript; if they could disagree with even a tiny probability, the disjoint supports that the attack depends on would not be guaranteed.","fun_headline_variants_meta":{"raw":{"variants":["Perfect key agreement doomed: eavesdropper always wins","Quantum key agreement impossible under perfect completeness","Eavesdropper recovers key from any classic-message QKA","No perfect QKA: eavesdropper finds key in O(q^5)","Impossibility: perfect QKA cannot exist in QROM"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000491,"raw_usage":{"total_tokens":2250,"prompt_tokens":743,"completion_tokens":1507,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":487,"completion_tokens_details":{"reasoning_tokens":1436}},"tokens_in":487,"tokens_out":1507,"duration_ms":13187,"temperature":1.0,"reasoning_tokens":1436,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T11:37:38.393115+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find or construct a perfectly complete QCCC key-agreement protocol for which the optimal passive eavesdropper needs more than c(q_A+q_B)^5 classical oracle queries for a universal constant c; a direct way to test the core lemma is to search computationally for degree-d disjoint-support Boolean polynomials p,q such that every deterministic decision tree deciding which is nonzero at a hidden point has depth above c·d^4, which would refute Lemma 3.5 and, with it, Theorem 3.1.","supporting_citations":[],"review_version":1}