Search papers, labs, and topics across Lattice.
This paper advances the understanding of key agreement protocols in the quantum random oracle model (QROM) by presenting unconditional attacks on quantum key agreement in two specific settings: a two-message scenario and a round-independent scenario. The authors utilize heavy-query learning techniques and reprogramming strategies to demonstrate that an attacker can recover the key with polynomial queries, effectively ruling out imperfectly correct quantum public-key encryption for classical messages. These findings highlight significant vulnerabilities in existing quantum key agreement protocols, particularly when classical communication is involved, challenging the security assumptions of such systems.
Unconditional attacks reveal that quantum key agreement protocols are fundamentally flawed when classical communication is involved, jeopardizing their security.
We make progress towards the impossibility of imperfectly complete quantum-computation, classical-communication (QCCC) key agreement by constructing the first unconditional attacks on quantum key agreement in the following restricted settings. In the two-message setting, we assume that Alice makes only classical queries to the oracle in the first round and that her message to Bob is classical, but otherwise both parties may perform arbitrary quantum computation, make quantum queries, and send a quantum state in the second round. Our attack and analysis are based on the heavy-query learning techniques from Austrin et al. (CRYPTO 2022) and the reprogramming techniques of Katz and Sela (arXiv 2401.14319). In the round-independent setting, we show that the attack of Barak and Mahmoody (CRYPTO 2009; J. Cryptology 2017) can be extended to multiple rounds when Alice and Bob share classical communication and make only classical queries in all but the final round. In both settings, the attacker is computationally unbounded and makes $poly(\lambda)$ queries to recover the key whenever each honest query bound is at most $poly(\lambda)$ and the valid agreement probability is inverse-polynomial. As a consequence, we rule out imperfectly correct quantum public-key encryption for classical messages whose length is bounded by a polynomial in $\lambda$ in the QROM when key generation has classical oracle access, even if encryption, decryption, and the ciphertext are quantum. In particular, the one-bit case applies to the imperfectly correct PKE obtained from two-round OSP by Bartusek and Khurana (CRYPTO 2025) whenever the classical OSP sender makes only classical random-oracle queries.
