Paper 2023/877

Public-Key Encryption with Quantum Keys

Khashayar Barooti, École Polytechnique Fédérale de Lausanne
Alex B. Grilo, Sorbonne University, CNRS, LIP6
Loïs Huguenin-Dumittan, École Polytechnique Fédérale de Lausanne
Giulio Malavolta, Max Planck Institute for Security and Privacy
Or Sattath, Ben-Gurion University of the Negev
Quoc-Huy Vu, Sorbonne University, CNRS, LIP6
Michael Walter, Ruhr University Bochum

In the framework of Impagliazzo's five worlds, a distinction is often made between two worlds, one where public-key encryption exists (Cryptomania), and one in which only one-way functions exist (MiniCrypt). However, the boundaries between these worlds can change when quantum information is taken into account. Recent work has shown that quantum variants of oblivious transfer and multi-party computation, both primitives that are classically in Cryptomania, can be constructed from one-way functions, placing them in the realm of quantum MiniCrypt (the so-called MiniQCrypt). This naturally raises the following question: Is it possible to construct a quantum variant of public-key encryption, which is at the heart of Cryptomania, from one-way functions or potentially weaker assumptions? In this work, we initiate the formal study of the notion of quantum public-key encryption (qPKE), i.e., public-key encryption where keys are allowed to be quantum states. We propose new definitions of security and several constructions of qPKE based on the existence of one-way functions (OWF), or even weaker assumptions, such as pseudorandom function-like states (PRFS) and pseudorandom function-like states with proof of destruction (PRFSPD). Finally, to give a tight characterization of this primitive, we show that computational assumptions are necessary to build quantum public-key encryption. That is, we give a self-contained proof that no quantum public-key encryption scheme can provide information-theoretic security.

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2023
Quantum cryptographyPublic-key encryption
Contact author(s)
khashayar barooti @ epfl ch
Alex Bredariol-Grilo @ lip6 fr
lois huguenin-dumittan @ epfl ch
giulio malavolta @ hotmail it
sattath @ gmail com
quoc huy vu @ ens fr
michael walter @ rub de
2023-09-21: last of 2 revisions
2023-06-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Khashayar Barooti and Alex B. Grilo and Loïs Huguenin-Dumittan and Giulio Malavolta and Or Sattath and Quoc-Huy Vu and Michael Walter},
      title = {Public-Key Encryption with Quantum Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2023/877},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.