  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.
