Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM
Abstract
We make progress towards the impossibility of quantum-computation, classical-communication (QCCC) key agreement by giving the first unconditional polynomial-query attacks that tolerate imperfect completeness in the following settings. First, we give a quantum attack on protocols with arbitrarily many rounds in which both parties' oracle queries and communication are classical before the final round, while local computation may be quantum throughout, and the final round may involve quantum oracle queries and one quantum message. Second, we give a classical attack on constant-round QCCC protocols in which Alice has classical oracle access and Bob may make quantum queries throughout. In both settings, the attacker is computationally unbounded and makes poly(λ) queries to recover the key with nonnegligible probability whenever each party's total honest query bound is at most poly(λ) and the valid agreement probability is inverse-polynomial. As consequences, we rule out query-bounded IND-CPA security for quantum public-key encryption with classical public and secret keys and classical messages of polynomially bounded length in the QROM in either of two settings: (i) key generation has classical oracle access, while encryption, decryption, and the ciphertext may be quantum; or (ii) encryption has classical oracle access and ciphertexts are classical, while key generation and decryption may have quantum oracle access. Both results assume negligible correctness error and polynomial honest query complexity. Combining the constant-round attack with the constructions of Bartusek and Khurana (CRYPTO 2025), we also rule out constant-round oblivious state preparation with polynomial honest query complexity and negligible correctness error in the QROM against computationally unbounded quantum receivers making polynomially many oracle queries.
Related
- Halving the cost of QROM again via dense encoding
- Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding
- Comment on arXiv:2510.21705 "Fundamental Impossibility of a Superradiant Neutrino Laser" and comment on arXiv:2510.21692 "Can Bose-Einstein Condensates Enhance Radioactive Decay?"
- Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability
- Enhancing noise robustness in device-independent conference key agreement with asymmetric parity-CHSH inequalities
BibTeX
@misc{kitagawa2026towards,
title = {{Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM}},
author = {Fuyuki Kitagawa and Ryo Nishimaki and Agi Villanyi and Takashi Yamakawa},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.17610},
eprint = {2608.17610},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.17610},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM
AU - Fuyuki Kitagawa
AU - Ryo Nishimaki
AU - Agi Villanyi
AU - Takashi Yamakawa
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2608.17610
UR - https://arxiv.org/abs/2608.17610
AB - We make progress towards the impossibility of quantum-computation, classical-communication (QCCC) key agreement by giving the first unconditional polynomial-query attacks that tolerate imperfect completeness in the following settings. First, we give a quantum attack on protocols with arbitrarily many rounds in which both parties' oracle queries and communication are classical before the final round, while local computation may be quantum throughout, and the final round may involve quantum oracle queries and one quantum message. Second, we give a classical attack on constant-round QCCC protocols in which Alice has classical oracle access and Bob may make quantum queries throughout. In both settings, the attacker is computationally unbounded and makes poly(λ) queries to recover the key with nonnegligible probability whenever each party's total honest query bound is at most poly(λ) and the valid agreement probability is inverse-polynomial. As consequences, we rule out query-bounded IND-CPA security for quantum public-key encryption with classical public and secret keys and classical messages of polynomially bounded length in the QROM in either of two settings: (i) key generation has classical oracle access, while encryption, decryption, and the ciphertext may be quantum; or (ii) encryption has classical oracle access and ciphertexts are classical, while key generation and decryption may have quantum oracle access. Both results assume negligible correctness error and polynomial honest query complexity. Combining the constant-round attack with the constructions of Bartusek and Khurana (CRYPTO 2025), we also rule out constant-round oblivious state preparation with polynomial honest query complexity and negligible correctness error in the QROM against computationally unbounded quantum receivers making polynomially many oracle queries.
ER -