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

Longcheng Li; Qian Li; Qipeng Liu; Xingjian Li

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

T0 review · 0 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Perfectly complete many-round key agreement is impossible in the QROM

desk verdict 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. read the letter →

arxiv 2608.03824 v1 pith:LPHG5KHR submitted 2026-08-04 quant-ph

Longcheng Li , Qian Li , Xingjian Li , Qipeng Liu This is my paper · ORCID

classification quant-ph MSC 68Q1281P9494A60

keywords quantumrandomoraclemodelkeyagreementQCCCperfectcompletenessblack-boxseparationone-wayfunctionsquerycomplexitypolynomialmethod

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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,

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Longcheng Li, Qian Li, Xingjian Li, Qipeng Liu: Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM.

The 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).

The 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.

The 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.

The 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.

Verdict: 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.

Referee Report

0 major / 5 minor

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].

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.

minor comments (5)

[Abstract / Section 1.1] Minor terminology and grammar: 'perfect complete' should be 'perfectly complete' throughout; 'Previous results only applies' should be 'apply'.
[Section 1.1 and Theorem 3.1] 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 3.4, Lemma 3.5] 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 2.2 / Lemma 3.2] 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.
[Lemma 3.2 proof] Typo: 'The operators composes' should be 'compose'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: proof is self-contained and uses external standard lemmas.

full rationale

The paper's derivation is a direct mathematical proof with no fitted parameters, no prediction that reduces to an input by construction, and no load-bearing self-citation. The central factorization (Lemma 3.2) follows from the tensor-product structure of QCCC protocols and the quantum polynomial method [BBC+01]. Perfect completeness is used in Lemma 3.3 to derive pointwise vanishing of cross-key products; this is a valid implication from the stated assumption, not an assumption equivalent to the theorem's conclusion. The candidate-key count and the decision-tree separator (Lemma 3.5) rely on external lemmas [NS94] and [KKDWY26] that do not incorporate the target result. Self-citations to [LLLL24, LLLL25, LLLL26] appear only as contextual comparisons of prior work and are not used as premises in the proof. The explicit statement that perfect completeness is essential is a scope limitation of the theorem, not a hidden circular step. The GPT-generated discovery note is a disclosure and does not affect the mathematical derivation. No step reduces to its own inputs.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central proof rests on standard polynomial-method and Boolean-analysis theorems plus explicit protocol-model assumptions. No free parameters are fitted to data, and no new physical or mathematical entities are postulated. The only imported analytic ingredient is the discrete Markov inequality Lemma 2.3 from [KKDWY26], stated without proof.

assumptions (5)

domain assumption QCCC protocol model: classical communication only, independent private states, no preshared entanglement or quantum communication, finite transcript and key alphabets per security parameter.
Stated in Section 2.2 and used in Lemma 3.2 to factor the branch probability as A_{t,a}(z) B_{t,b}(z).
domain assumption Perfect completeness: Pr[K_A=K_B]=1 exactly.
Assumed in Theorem 3.1 and used in Lemma 3.3 to make all cross-key terms vanish pointwise, producing disjoint key supports. The authors note that imperfect completeness would require different ideas.
standard math Quantum polynomial method (Lemma 2.2): the acceptance probability of a q-query quantum algorithm, and the squared norm of a postselected branch, have degree at most 2q.
Imported from [BBC+01] and used to bound deg(A_{t,a}) and deg(B_{t,b}) in Lemma 3.2.
standard math Nisan-Szegedy support lemma (Lemma 2.1): a nonzero multilinear polynomial of degree at most d on {0,1}^N has support size at least 2^{N-d}.
Imported from [NS94] and used in Lemma 3.4 to bound |K_t| <= 2^d.
standard math Discrete Markov inequality (Lemma 2.3): if |r|<=1, |r(0^b)|=1, and r flips sign on every neighbor of 0^b, then deg(r) >= sqrt(b/2).
Imported from [KKDWY26, Theorem 4] without proof in this paper. It is the analytic engine behind the O(d^4) depth bound in Lemma 3.5.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM." pith.science (2026). https://pith.science/paper/LPHG5KHR

@misc{pith2026260803824,
  author       = {Pith},
  title        = {Pith review of: Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LPHG5KHR}},
  note         = {Machine review of arXiv:2608.03824}
}

abstract

This paper proves that it is impossible to construct perfectly complete quantum key agreement protocols (QKA) from quantumly secure one-way functions (OWFs) in a black-box manner. Specifically, consider any protocol in which Alice and Bob exchange only classical messages, make at most $q_{\mathsf{A}}$ and $q_{\mathsf{B}}$ quantum queries, respectively, to a Boolean-valued random oracle, and agree on a shared key with certainty. This paper shows that there exists an eavesdropper, given the classical messages, that can recover the shared key with certainty using $O((q_{\mathsf{A}}+q_{\mathsf{B}})^5)$ classical oracle queries. The bound is independent of the number of rounds, transcript length, key length, and oracle-domain size. Previous results only applies to two-round key agreement (Li et al. CRYPTO 26) or relies on unproven conjectures (Austrin et al. CRYPTO 22). GPT-5.6 Sol Ultra found this proof in a one-shot conversation and drafted a preliminary version of this paper. The authors are fully responsible for the correctness, writing and discussions of this paper.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 10 canonical work pages

[1]

On the impossibility of key agreements from quantum random oracles

Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, Yao-Ting Lin, and Mohammad Mahmoody. On the impossibility of key agreements from quantum random oracles. In Advances in Cryptology -- CRYPTO 2022 , volume 13508 of Lecture Notes in Computer Science , pages 165--194. Springer, 2022

work page 2022
[2]

Quantum lower bounds by polynomials

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM , 48(4):778--797, 2001

work page 2001
[3]

Random oracles in a quantum world

Dan Boneh, \"O zg \"u r Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random oracles in a quantum world. In Advances in Cryptology -- ASIACRYPT 2011 , volume 7073 of Lecture Notes in Computer Science , pages 41--69. Springer, 2011

work page 2011
[4]

Merkle puzzles are optimal --- an O(n^2) -query attack on any key exchange from a random oracle

Boaz Barak and Mohammad Mahmoody-Ghidary. Merkle puzzles are optimal --- an O(n^2) -query attack on any key exchange from a random oracle. In Advances in Cryptology -- CRYPTO 2009 , volume 5677 of Lecture Notes in Computer Science , pages 374--390. Springer, 2009

work page 2009
[5]

Limits on the provable consequences of one-way permutations

Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing , pages 44--61. ACM, 1989

work page 1989
[6]

Rational degree is polynomially related to degree

Robin Kothari, Matt Kovacs-Deak, Daochen Wang, and Rain Zimin Yang. Rational degree is polynomially related to degree. arXiv:2601.08727v2, 2026. To appear in FOCS 2026

work page Pith review arXiv 2026
[7]

How (not) to build quantum PKE in Minicrypt

Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu. How (not) to build quantum PKE in Minicrypt . In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology -- CRYPTO 2024 , volume 14926 of Lecture Notes in Computer Science , pages 152--183. Springer, 2024

work page 2024
[8]

Toward the impossibility of perfect complete quantum PKE from OWF s

Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu. Toward the impossibility of perfect complete quantum PKE from OWF s. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) , volume 325 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 71:1--71:16. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r In...

work page 2025

Show all 11 references

[9]

Cryptomania v.s

Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu. Cryptomania v.s. Minicrypt in a quantum world. In Advances in Cryptology -- CRYPTO 2026 , 2026. To appear; IACR ePrint 2025/639

2026
[10]

Exact quantum query complexity for total boolean functions

Gatis Midrijanis. Exact quantum query complexity for total boolean functions. arXiv preprint quant-ph/0403168 , 2004

2004 arXiv
[11]

On the degree of boolean functions as real polynomials

Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Comput. Complex. , 4:301--313, 1994

1994

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [1]

On the impossibility of key agreements from quantum random oracles

Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, Yao-Ting Lin, and Mohammad Mahmoody. On the impossibility of key agreements from quantum random oracles. In Advances in Cryptology -- CRYPTO 2022 , volume 13508 of Lecture Notes in Computer Science , pages 165--194. Springer, 2022

work page 2022

[2] [2]

Quantum lower bounds by polynomials

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM , 48(4):778--797, 2001

work page 2001

[3] [3]

Random oracles in a quantum world

Dan Boneh, \"O zg \"u r Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random oracles in a quantum world. In Advances in Cryptology -- ASIACRYPT 2011 , volume 7073 of Lecture Notes in Computer Science , pages 41--69. Springer, 2011

work page 2011

[4] [4]

Merkle puzzles are optimal --- an O(n^2) -query attack on any key exchange from a random oracle

Boaz Barak and Mohammad Mahmoody-Ghidary. Merkle puzzles are optimal --- an O(n^2) -query attack on any key exchange from a random oracle. In Advances in Cryptology -- CRYPTO 2009 , volume 5677 of Lecture Notes in Computer Science , pages 374--390. Springer, 2009

work page 2009

[5] [5]

Limits on the provable consequences of one-way permutations

Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing , pages 44--61. ACM, 1989

work page 1989

[6] [6]

Rational degree is polynomially related to degree

Robin Kothari, Matt Kovacs-Deak, Daochen Wang, and Rain Zimin Yang. Rational degree is polynomially related to degree. arXiv:2601.08727v2, 2026. To appear in FOCS 2026

work page Pith review arXiv 2026

[7] [7]

How (not) to build quantum PKE in Minicrypt

Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu. How (not) to build quantum PKE in Minicrypt . In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology -- CRYPTO 2024 , volume 14926 of Lecture Notes in Computer Science , pages 152--183. Springer, 2024

work page 2024

[8] [8]

Toward the impossibility of perfect complete quantum PKE from OWF s

Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu. Toward the impossibility of perfect complete quantum PKE from OWF s. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) , volume 325 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 71:1--71:16. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r In...

work page 2025