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

• URL: http://arxiv.org/abs/2608.03824v1
• Date: Tue, 04 Aug 2026 15:33:42 GMT
• Title: Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM
• Abstract summary: It is impossible to construct perfectly complete quantum key agreement protocols (QKA) from quantumly secure one-way functions (OWFs) in a black-box manner.<n>This paper shows that there exists an eavesdropper, given the classical messages, that can recover the shared key with certainty using $O((q_mathsfA+q_mathsfB)5)$ classical oracle queries.
• Score: 7.423478193398542
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity [0.0]
  One-way puzzles imply EFI pairs, and whether holds is open.<n>We construct a single classical oracle relative to which one-way puzzles do not exist, even with an unbounded verifier.<n>An EFI pair survives every distinguisher that queries the oracle classically throughout and holds advice about it, making its one superposition query at the end.
  arXiv  Detail & Related papers  (2026-09-10T17:54:55Z)
• Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM [9.538313445597385]
  We make progress towards the impossibility of imperfectly complete quantum-computation, classical-communication (QCCC) key agreement.<n>We construct the first unconditional attacks on quantum key agreement in the following restricted settings.
  arXiv  Detail & Related papers  (2026-08-18T10:19:27Z)
• Computational Monogamy of Entanglement and Non-Interactive Quantum Key Distribution [21.219588497290115]
  Quantum key distribution (QKD) enables Alice and Bob to exchange a secret key over a public, untrusted quantum channel.<n>Compared to classical key exchange, QKD achieves everlasting security: after the protocol execution the key is secure against adversaries.<n>No non-interactive protocol is known that provides everlasting security, even using quantum information.
  arXiv  Detail & Related papers  (2025-10-01T11:41:04Z)
• Cryptomania v.s. Minicrypt in a Quantum World [5.885896375772235]
  We prove that it is impossible to construct perfect-complete quantum public-key encryption (QPKE) with classical keys from quantumly secure one-way functions (OWFs) in a black-box manner.
  arXiv  Detail & Related papers  (2025-04-08T06:07:40Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions [0.5999777817331317]
  It has been recently shown that public-key encryption (PKE) from one-way functions (OWF) is possible if we consider quantum public keys. In this paper, we focus on black-box separation for PKE with classical public key and quantum ciphertext from OWF.
  arXiv  Detail & Related papers  (2023-11-06T20:41:25Z)
• Robust Quantum Public-Key Encryption with Applications to Quantum Key Distribution [16.06159998475861]
  Quantum key distribution (QKD) allows Alice and Bob to agree on a shared secret key, while communicating over a public (untrusted) quantum channel. It has two main advantages: (i) The key is unconditionally hidden to the eyes of any attacker, and (ii) its security assumes only the existence of authenticated classical channels. We propose a two-message QKD protocol that satisfies everlasting security, assuming only the existence of quantum-secure one-way functions.
  arXiv  Detail & Related papers  (2023-04-06T11:14:55Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Succinct Classical Verification of Quantum Computation [30.91621630752802]
  We construct a classically succinct interactive argument for quantum computation (BQP) Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning Errors (LWE)
  arXiv  Detail & Related papers  (2022-06-29T22:19:12Z)
• Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security [67.06003361150228]
  A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
  arXiv  Detail & Related papers  (2020-12-30T18:03:56Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.