CryptoDB
A Computational Monogamy of Entanglement Theorem with Applications to Non-Interactive Quantum Key Distribution
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2025 |
| Abstract: | Quantum key distribution (QKD) enables Alice and Bob to exchange a secret key over a public, untrusted quantum channel. Compared to classical key exchange, QKD achieves \emph{everlasting security}: after the protocol execution the key is secure against adversaries that can do unbounded computations. On the flip side, while classical key exchange can be achieved non-interactively (with two simultaneous messages between Alice and Bob), no non-interactive protocol is known that provides everlasting security, even using quantum information. In this work, we make progress on this problem. Our main technical contribution is a \emph{computational} variant of the celebrated \emph{monogamy of entanglement} game, where the secret is only computationally hidden from the players, rather than information-theoretically. In these settings, we prove a negligible bound on the maximal winning probability over all strategies. As a direct application, we obtain a non-interactive (simultaneous message) QKD protocol from any post-quantum classical non-interactive key exchange, which satisfies everlastingly secure \emph{assuming Alice and Bob agree on the same key}. The protocol only uses EPR pairs and standard and Hadamard basis measurements, making it suitable for near-term quantum hardware. We also propose how to convert this protocol into a two-round protocol that satisfies the standard notion of everlasting security. Finally, we prove a \emph{no-go theorem} which establishes that (in contrast to the case of ordinary multi-round QKD) entanglement is necessary for non-inter\-active QKD, i.e., the messages sent by Alice and Bob cannot both be unentangled with their respective quantum memories if the protocol is to be everlastingly secure. |
BibTeX
@inproceedings{tcc-2025-36304,
title={A Computational Monogamy of Entanglement Theorem with Applications to Non-Interactive Quantum Key Distribution},
publisher={Springer-Verlag},
author={Alex Grilo and Giulio Malavolta and Michael Walter and Tianwei Zhang},
year=2025
}