  Quantum key distribution (QKD) allows Alice and Bob to agree on a shared
secret key, while communicating over a public (untrusted) quantum channel.
Compared to classical key exchange, 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 which, in
practice, can be realized using Minicrypt assumptions, such as the existence of
digital signatures. On the flip side, QKD protocols typically require multiple
rounds of interactions, whereas classical key exchange can be realized with the
minimal amount of two messages using public-key encryption. A long-standing
open question is whether QKD requires more rounds of interaction than classical
key exchange. In this work, we propose a two-message QKD protocol that
satisfies everlasting security, assuming only the existence of quantum-secure
one-way functions. That is, the shared key is unconditionally hidden, provided
computational assumptions hold during the protocol execution. Our result
follows from a new construction of quantum public-key encryption (QPKE) whose
security, much like its classical counterpart, only relies on authenticated
classical channels.
