Paper 2023/1720
Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions
Abstract
There has been a recent interest in proposing quantum protocols whose security relies on weaker computational assumptions than their classical counterparts. Importantly to our work, it has been recently shown that public-key encryption (PKE) from one-way functions (OWF) is possible if we consider quantum public keys. Notice that we do not expect classical PKE from OWF given the impossibility results of Impagliazzo and Rudich (STOC'89). However, the distribution of quantum public keys is a challenging task. Therefore, the main question that motivates our work is if quantum PKE from OWF is possible if we have classical public keys. Such protocols are impossible if ciphertexts are also classical, given the impossibility result of Austrin et al. (CRYPTO'22) of quantum enhanced key-agreement (KA) with classical communication. In this paper, we focus on black-box separation for PKE with classical public key and quantum ciphertext from OWF under the polynomial compatibility conjecture, first introduced in Austrin et al.. More precisely, we show the separation when the decryption algorithm of the PKE does not query the OWF. We prove our result by extending the techniques of Austrin et al. and we show an attack for KA in an extended classical communication model where the last message in the protocol can be a quantum state.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Contact author(s)
-
samuel bouaziz-ermann @ lip6 fr
Alex Bredariol-Grilo @ lip6 fr
damien vergnaud @ lip6 fr
quoc huy vu @ ens fr - History
- 2023-11-13: approved
- 2023-11-06: received
- See all versions
- Short URL
- https://ia.cr/2023/1720
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1720,
author = {Samuel Bouaziz--Ermann and Alex B. Grilo and Damien Vergnaud and Quoc-Huy Vu},
title = {Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions},
howpublished = {Cryptology ePrint Archive, Paper 2023/1720},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1720}},
url = {https://eprint.iacr.org/2023/1720}
}
