#  How (not) to Build Quantum PKE in Minicrypt

Longcheng Li Qian Li Xingjian Li Qipeng Liu State Key Lab of Processors,
Institute of Computing Technology, Chinese Academy of Sciences. Email:
<EMAIL_ADDRESS>International Center For Industrial And
Applied Mathematics, Shenzhen Research Institute of Big Data. Email:
<EMAIL_ADDRESS>University. Email:
<EMAIL_ADDRESS>of California San Diego. Email:
<EMAIL_ADDRESS>
###### Abstract

The seminal work by Impagliazzo and Rudich (STOC’89) demonstrated the
impossibility of constructing classical public key encryption (PKE) from one-
way functions (OWF) in a black-box manner. Quantum information has the
potential to bypass classical limitations, enabling the realization of
seemingly impossible tasks such as quantum money, copy protection for
software, and commitment without one-way functions. However, the question
remains: can quantum PKE (QPKE) be constructed from quantumly secure OWF?

A recent line of work has shown that it is indeed possible to build QPKE from
OWF, but with one caveat. These constructions necessitate public keys being
quantum and unclonable, diminishing the practicality of such “public”
encryption schemes — public keys cannot be authenticated and reused. In this
work, we re-examine the possibility of perfect complete QPKE in the quantum
random oracle model (QROM), where OWF exists.

  * Our first main result: QPKE with classical public keys, secret keys and ciphertext, does not exist in the QROM, if the key generation only makes classical queries.

Therefore, a necessary condition for constructing such QPKE from OWF is to
have the key generation classically “un-simulatable”. Previous results
(Austrin et al. CRYPTO’22) on the impossibility of QPKE from OWF rely on a
seemingly strong conjecture. Our work makes a significant step towards a
complete and unconditional quantization of Impagliazzo and Rudich’s results.

Our second main result extends to QPKE with quantum public keys.

  * The second main result: QPKE with quantum public keys, classical secret keys and ciphertext, does not exist in the QROM, if the key generation only makes classical queries and the quantum public key is either pure or “efficiently clonable”.

The result is tight due to these existing QPKEs with quantum public keys,
classical secret keys, quantum/classical ciphertext and classical-query key
generation require the public key to be mixed instead of pure; or require
quantum-query key generation, if the public key is pure. Our result further
gives evidence on why existing QPKEs lose reusability.

We also explore other sufficient/necessary conditions to build QPKE from OWF.
Along the way, we use a new argument based on conditional mutual information
and Markov chain to reprove the classical result; leveraging the analog of
quantum conditional mutual information and quantum Markov chain by Fawzi and
Renner (Communications in Mathematical Physics), we extend it to the quantum
case and prove all our results. We believe the techniques used in the work
will find many other usefulness in separations in quantum
cryptography/complexity.

##  1 Introduction

Quantum information and computation has the remarkable capability to transform
classical impossibility into reality, ranging from breaking classically secure
cryptosystems (Shor’a algorithm [Sho99]), realizing classically impossible
primitives (quantum money [Wie83], quantum copy-protection [Aar09, ALL+21]) to
weakening assumptions (quantum key distribution [BB14], oblivious
transfer/multi-party computation [BCKM21, GLSV21], commitment [AQY22,
MY22a])111Here, we only cite works that initialized each area..

In the seminal work by Impagliazzo and Rudich [IR89], they proved that one-way
functions (OWFs) were insufficient to imply the existence of public-key
encryption (PKE) in a black-box manner. Coined by Impagliazzo [Imp95], the
word “Minicrypt” was referred to a world where only one-way functions exist;
this word now broadly denotes all cryptographic primitives that are
constructible from one-way functions. Thus, their result is now often
interpreted as “classical PKE is not in Minicrypt”. Given the increasing
instances of quantum making classical impossibility feasible, we explore the
following question in this work:

Does quantum PKE (with classical plaintext) exist in Minicrypt?

Upon posing the question, ambiguity arises. A general quantum public-key
encryption (QPKE) scheme allows everything to be quantum: its interaction with
an OWF, both its public key and secret key, as well as ciphertext. Indeed,
many efforts have already been made towards understanding different cases.

#### Classical Keys, Classical Ciphertext.

In the work by Austrin, Chung, Chung, Fu, Lin and Mahmoody [ACC+22], they
initialized the study on the impossibility of quantum key agreement (QKA) in
the quantum random oracle model. QKA is a protocol that Alice and Bob can
exchange classical messages in many rounds, quantumly query a random oracle,
and eventually agree on a classical key. They show that, under a seemingly
strong222It seems strong because it implies that the eavesdropper can attack
quantum Alice and Bob with only a polynomial number of classical queries.
assumption called “polynomial compatibility conjecture”, such QKA with perfect
completeness does not exist. Since QPKE with both keys and ciphertext being
classical implies a two-round QKA, their conditional impossibility extends to
this type of QPKE as well.

The result provides evidence on the negative side: such QPKE does not exist
under the polynomial compatibility conjecture. However, not only proving or
refuting the conjecture is quite challenging, but also the conjecture (or some
form of the conjecture) is necessary. To prove QKA is impossible, one needs to
design an eavesdropper that observes the whole transcript, interacts with the
random oracle, and guesses a classical key. In a general QKA, both Alice and
Bob can make quantum queries to the random oracle; the eavesdropper in the
attack by Austrin et al. only makes classical queries. It inherently requires
a simulation of a quantum-query algorithm using only classical queries (at
least for the QKA functionality). Although not directly comparable, such
efficient simulation for decision problems [AA09] (Aaronson-Ambainis
conjecture) is conjectured to exist but the question still remains open until
now. Moreover, [ACC+22] showed that if the Aaronson-Ambainis conjecture is
false, a classical-query eavesdropper is insufficient to break imperfect
complete QKA protocols.

In light of these considerations, our focus in this work centers on the
following question:

Q1. Can we separate QPKE with classical keys, classical ciphertext from
Minicrypt,
without any conjecture?

#### Quantum Public Key, Classical Secret Key and Quantum/Classical
Ciphertext.

The quantum landscape introduces a paradigm shift. It was first realized by
Morimae and Yamakawa [MY22] that some forms of QPKE with quantum public keys
and quantum ciphertext might be constructed from OWFs (or even presumably
weaker primitives). Subsequent QPKE schemes were later proposed by Coladangelo
[Col23], Kitagawa et al. [KMNY23], Malavolta and Walter [MW23] and Barooti et
al. [BGH+23].

On the surface, it seems to give a good answer: QPKE with quantum public keys
exists in Minicrypt, showcasing a notable distinction between the quantum and
classical world. However, is this demarcation as unequivocal as it seems?
Indeed, all the aforementioned constructions share one limitation — they lose
one of the most important properties inherent in all classical PKE —
reusability. A classical PKE scheme allows a user who possesses a public key
to encrypt any polynomial number of messages, by reusing the classical public
key. In contrast, public keys in [MY22, Col23, KMNY23, MW23, BGH+23] are
essentially unclonable333Although unclonability does not necessarily imply no-
reusability, it is an evidence of no-reusability. and not reusable. Although
some may argue for the practicality of QPKE with an additional public
interface for generating quantum public keys, it introduces additional
complexities such as the authentication of quantum keys, leading to increased
interactions and other potential challenges.

Thus, our second focus is the question:

Q2. Must reusability be sacrificed in constructing QPKE with quantum public
keys from OWFs?

###  1.1 Our Main Results

We make progress towards these two questions. A table discussing and comparing
all existing results and our results is provided on the next page (Table 1).
Our first main result establishes an impossibility result on QPKE with
classical keys and classical ciphertext in the QROM.

######  Theorem 1.1.

QPKE with classical keys and classical ciphertext does not exist in the QROM,
if

  1. 1.

It has perfect completeness.

  2. 2.

The key generation algorithm only makes classical queries to the random
oracle.

Unlike the approaches used in [ACC+22], our result does not require any
conjecture, as the eavesdropper in our attack makes quantum queries. Perfect
completeness is a natural property shared by many PKE schemes444Very recently,
Mazor [Maz23] proposed the first perfectly complete “Merkle Puzzle”, which was
not known for many years.

Consequently, if QPKE could be constructed in the QROM, one must have the key
generation procedure being classical-query “un-simulatable”; meaning the keys
can not be computed by an efficient classical-query algorithm. If we believe
the Aaronson-Ambainis conjecture [AA09] (all quantum-query-solvable decision
problems can be simulated by classical-query), the theorem suggests that the
key generation must be a sampling procedure. Thus, to build QPKE in the QROM,
we need to find a search/sampling problem that is only tractable by quantum
queries; one such example is the Yamakawa-Zhandry problem [YZ22].

[ACC+22] ruled out perfect complete QPKE with classical keys and classical
ciphertext in the QROM, if (i) the encryption only makes classical queries, or
(ii) both the key generation and decryption makes classical queries, without
using the polynomial compatibility conjecture. Our result immediately improves
their result (ii). Additionally, both of their impossibility results apply to
the case where the oracle access in encryption and decryption procedure is
asymmetric. Our result further completes the picture by making both encryption
and decryption symmetric (quantum queries).

Another difference in our work is that our eavesdropper makes quantum queries.
The capability of leveraging quantum eavesdroppers and conditioning on quantum
events in this work, immediately gives us two strengthened versions (Theorem
1.2 and Theorem 1.3) of Theorem 1.1, which works for quantum public keys and
quantum ciphertext. These two extensions provide many interesting discussions
on the feasibility and impossibility of building QPKE in Minicrypt. [BGVV23]
also discussed the feasibility of QPKE with quantum ciphertext, with a weaker
result and based on the polynomial compatibility conjecture. Thus, we believe
our framework is versatile and has the potential to completely answer these
questions. We elaborate on them now.

Our second main result extends the previous theorem to QPKE with quantum
public keys and ciphertexts. This scheme is tight to all existing QPKE with
quantum public keys and perfect completeness, see Table 2.

######  Theorem 1.2 (Subsuming Theorem 1.1).

QPKE with quantum public key, classical secret key, and classical or quantum
ciphertext does not exist in the QROM, if

  1. 1.

It has perfect completeness.

  2. 2.

The key generation algorithm only makes classical queries to the random
oracle.

  3. 3.

The quantum public key is either pure or “efficiently clonable”.

At first glance, the theorem may appear unexciting: how can a classical-query
key generation produce meaningful quantum public keys? Interestingly, the QPKE
constructions in [KMNY23, MW23] have only classical-query key generation
procedures. Namely, their public keys are of the form
$\frac{1}{\sqrt{2}}(\ket{s_{0}}+\ket{s_{1}})$ of two strings $s_{0},s_{1}$,
which can be computed using only classical queries.

Let us explain the third condition in our result. In QPKE, one needs to
guarantee that having multiple copies of a quantum public key, the IND-CPA
security still holds. If the public key generation procedure outputs a pure
state, in other words the security holds against copies of the same pure
state, we call the public key pure. Otherwise, each copy of a quantum public
key is a mixed state (a distribution of pure states) and even holding multiple
copies from the same distribution does not mean having the same pure
states555For example, even if having two copies of the same mixed state
$\frac{\mathbb{I}}{2}$, they can be two different states, like
$\ket{0}\ket{1}$.. In the latter case, we require that there exists a query-
efficient cloning procedure that can perfectly duplicate the pure state of the
quantum public key.

As the schemes in [KMNY23, MW23] have perfect completeness and classical-query
key generation, our result essentially says that their public keys must be
mixed and can not be cloned. While the absence of perfect cloning does not
imply non-reusability, our result provides crucial insights into the
feasibility of building QPKE with quantum public keys and reusability from
OWFs. Many intriguing open questions will be discussed further at the end of
this section.

Our second theorem also is tight to the QPKE scheme by [Col23, BGH+23]. Their
scheme has perfect completeness, pure state quantum public keys. Our theorem
suggests that their schemes must make quantum queries; which is the case in
their construction, as they need to query a pseudorandom function (implied by
OWFs in a black-box manner) on an equal superposition.

Our next result is on the type of QPKE with classical keys and quantum
ciphertext, whose decryption makes no queries to an oracle. The impossibility
extends to any oracle model (even quantum oracles), not just the random oracle
model.

######  Theorem 1.3.

(Imperfect/Perfect) QPKE with classical keys and quantum ciphertext does not
exist _in any oracle model_ , if

  1. 1.

The decryption algorithm makes no queries to the oracle.

Here, an oracle model means an oracle is sampled from a distribution, and the
KA is executed under this oracle; both the key generation algorithm, the
encryption algorithm and the attacker can have quantum access to the oracle.
We remark that in our impossibility result, such QPKE does not need to be
perfectly complete. We also note that, our theorem holds in the classical
setting; PKE does not exist in any oracle model if the decryption algorithm
makes no queries. This does not contradict constructions in the generic group
model, as the decryption algorithm is required to make oracle queries.

A recent work by Bouaziz–Ermann, Grilo, Vergnaud and Vu [BGVV23] also
discusses a similar separation. They proved that, under the polynomial
compatibility conjecture, perfect complete QPKE with classical keys and
quantum ciphertext does not exist in the QROM, if decryption makes no queries.
Our Theorem 1.3 improves their results in three aspects: we remove the
conjecture and the requirement on perfect completeness, and the impossibility
works in any oracle model.

#### Other results.

As we progress towards achieving our main results, our techniques also enable
us to establish additional impossibility results on QPKE and QKA as well.
These results include

  * •

Separation between pseudorandom quantum states and QKA (Remark 5.3);

  * •

Impossibility of Merkle-like QKA (more generally, non-interactive QKA) in _any
oracle model_ (Theorem 5.2); we emphasize that this result also holds for
quantum oracles, e.g., when a black-box unitary is chosen from Haar measure.

  * •

Impossibility of QPKE with a short classical secret key in _any oracle model_
(Appendix C).

We refer interested readers to these sections for more details.

| [ACC+22] | [ACC+22] | [ACC+22] | Thm 1.1 | [BGVV23] | Thm 1.3
---|---|---|---|---|---|---
perfect complete |  |  |  |  |  |
ciphertext | C | C | C | C | Q | Q
${\sf Gen}$ | Q | Q | C | C | Q | Q
${\sf Enc}$ | Q | C | Q | Q | Q | Q
${\sf Dec}$ | Q | Q | C | Q | $\star$ | $\star$
conjecture |  |  |  |  |  |
oracle | RO | RO | RO | RO | RO | any oracle
Table 1: Comparing impossibility results on classical public keys. ‘Q’ denotes quantum, ‘C’ denotes classical, ‘checkmark’ denotes yes, and ‘$\star$’ denotes no oracle queries. “RO” stands for “(quantum) random oracle”.  | Thm 1.2 (Impossibility) | [KMNY23, MW23] | [Col23, BGH+23]
---|---|---|---
perfect complete |  |  |
ciphertext | pure or “efficiently clonable” | mixed and unclonable | pure
${\sf Gen}$ | C | C | Q
Table 2: Comparing our Thm 1.2 with existing constructions. [KMNY23, MW23]
overcame the impossibility by allowing the ciphertext to be mixed; [Col23,
BGH+23] overcame the impossibility by allowing the Gen procedure to make
quantum queries.

###  1.2 Open Questions and Discussions

Before the overview of our techniques in the next section, we discuss some
open questions and directions. Some discussions may become clearer upon
reviewing both the overview and the entirety of the paper.

#### Remove perfect completeness.

Our Theorem 1.1 and Theorem 1.2 both rely on the underlying QPKE is perfectly
complete. Can we remove this condition and make the impossibility result work
for any QPKE?

#### Extending clonable keys to reusable keys.

When quantum public keys are reusable, that means there exists an encryption
procedure ${\sf Enc}^{\prime}$ that takes two messages $m,m^{\prime}$ and only
one quantum public key ${\sf pk}$, and outputs two valid ciphertexts. Since
${\sf Enc}^{\prime}$ is not necessarily honest, it seems difficult to convert
such assumptions into the setting of a QKA protocol. An intermediate goal is
to have ${\sf Enc}$ “deterministic”, which means it takes ${\sf pk}$ and $m$,
outputs the original ${\sf pk}$ together with a valid ${\sf ct}$ — this is a
weaker but promising step towards a full understanding of reusability. Another
direction is to relax the “clonable” condition to some form of “approximate
clonable” in our impossibility result.

#### Make key generation quantum.

Our Theorem 1.1 and Theorem 1.2 assume key generation procedure only makes
classical queries. The current techniques require addressing some sorts of
“heavy queries” made by an encryption procedure. For classical-query key
generation, the number of such possible inputs is only polynomial. But it will
be less clear how to handle this, when the key generation is fully quantum.
Upon resolving this, one can get a full separation between QPKE and OWFs.

The basic idea of our approach is to keep the conditional mutual information
(between Alice and Bob, conditioned on quantum Eve) small during the execution
of QKA protocols or QPKE schemes. The characterization of quantum states with
small CMI provided by Fawzi and Renner [FR15] (see Theorem 3.11) plays a major
role. To achieve a full separation between QPKE and OWF, the argument has to
critically utilize the condition that $H$ is a uniform random function rather
than drawn from a general oracle distribution. This is because our separation
works in both the quantum and classical setting, but in the full classical KA
case, KA exists in the generic group model. Thus, we really need to use the
structures of a random oracle. In this work, we show it is possible when key
generation only makes classical queries but not clear for quantum-query key
generation.

### Acknowledgement

Qipeng Liu would like to thank Navid Alamati for bringing up this problem in
2019 while interning at Fujitsu Research of America, and Jan Czajkowski,
Takashi Yamakawa and Mark Zhandry for insightful discussions at Princeton
during 2019 and 2020. The authors also thank Luowen Qian for pointing out the
problem of Merkle-like QKA with Haar-random unitary, which prompted the
realization of Theorem 1.3 applicable to even quantum oracles.

Qian Li’s work was supported by the National Natural Science Foundation of
China Grants (No. 62002229), and Hetao Shenzhen-Hong Kong Science and
Technology Innovation Cooperation Zone Project (No. HZQSWS-KCCYB-2024016).

Longcheng Li was supported in part by the National Natural Science Foundation
of China Grants No. 62325210, 62272441, 12204489, 62301531, and the Strategic
Priority Research Program of Chinese Academy of Sciences Grant No.
XDB28000000.

##  2 Technical Overview

In this section, we shed light on several key ideas used in the work,
especially those on how to attack with quantum queries and how to deal with
quantum public keys. Our method for handling quantum ciphertext is similar to
that in [BGVV23] by leveraging the Gentle Measurement Lemma.

#### Translating QPKE to QKA.

Although we focus on the separation between QPKE and OWFs (or the quantum
random oracle model), we will mostly study two-round QKA protocols. Say, if we
have a QPKE scheme in the QROM (${\sf Gen},{\sf Enc},{\sf Dec}$), we can
easily convert it to a two-round QKA:

######  Definition 2.1 (Informal, Two-round QKA).

We define a two-round QKA as follows.

  * •

Alice runs ${\sf Gen}$ to produce ${\sf pk},{\sf sk}$ and sends ${\sf pk}$ as
the first message $m_{1}$ to Bob. We call Alice’s algorithm at this stage
$\mathcal{A}_{1}$.

  * •

Bob upon receiving $m_{1}:={\sf pk}$, it samples a uniformly random key $k$.
It computes ${\sf ct}\leftarrow{\sf Enc}({\sf pk},k)$ and sends $m_{2}:={\sf
ct}$ to Alice. We call Bob’s algorithm at this stage $\mathcal{B}$.

  * •

Alice will then run ${\sf Dec}({\sf sk},{\sf ct})$ to retrieve $k$. We call
Alice’s algorithm at this stage $\mathcal{A}_{2}$.

If the QPKE has security against randomly chosen messages, then the underlying
QKA is secure. Quantum public keys will make $m_{1}$ quantum in the
corresponding QKA, quantum ciphertext translates to a quantum $m_{2}$ and
classical-query ${\sf Gen}$ makes $\mathcal{A}_{1}$ classical-query. Thus, we
focus on breaking various types of two-round QKA with perfect completeness.

###  2.1 Recasting the Classical Idea for Merkle-like KA

The classical proofs [IR89, BM09] shares one common idea: as long as an
eavesdropper Eve learns all the queries that are both used in Alice and Bob’s
computation, Eve can learn the key666[BKSY11] also gave a proof for the case
of perfect completeness. Their proof works even if not all intersection
queries are learned.. Here we re-interpret the idea for a special case: two-
round Merkle-like KA. In this type of KA, $m_{1},m_{2}$ are generated based on
oracle queries and sent simultaneously to the other party (so that $m_{2}$ has
no dependence on $m_{1}$). Furthermore, to recover the shared key, Alice and
Bob only need to do local computation on their internal states and the
communication, _without making any oracle queries_. This is a strong form of
KA, which is not implied by PKE using the aforementioned reduction. We refer
to it as Merkle-like because the famous Merkle Puzzles are of this form.

Let us assume for a specific execution of Alice and Bob, the queries made by
Alice is the list $R_{A}$, her private coins are $s_{A}$ and similarly
$R_{B},s_{B}$, $R_{E}$ is the query made by Eve; we define ${\sf
View}_{A}=(s_{A},R_{A})$ as the personal view of Alice, similarly ${\sf
View}_{B}$ for Bob. A tuple $({\sf View}_{A},{\sf View}_{B},m_{1},m_{2},H)$ is
a possible execution of the KA right after Alice and Bob exchange their
messages but have not started working on computing the key. The tuple
specifies Alice’s random coins and queries, similarly for Bob, communication
$m_{1},m_{2}$ and the oracle $H$ under which the protocol is executed. We say
$({\sf View}_{A},{\sf View}_{B})$ is consistent with a transcript
$(m_{1},m_{2})$ if there exists an oracle $H$, such that $({\sf View}_{A},{\sf
View}_{B},m_{1},m_{2},H)$ has _strictly positive_ probability of appearing in
some real execution. Similarly, ${\sf View}_{A}$ is consistent with
$(m_{1},m_{2})$ if $({\sf View}_{A},m_{1},m_{2},H)$ has non-zero probability
for some oracle $H$.

For a transcript $(m_{1},m_{2})$, it is always easy to find a pair of Alice’s
fake ${\sf View}_{A}^{\prime}=(s^{\prime}_{A},T^{\prime}_{A})$ that is
consistent with $m_{1},m_{2}$. Since we do not care about the actual
computation cost, and only the number of queries matters, we can keep sampling
oracles until we see a transcript $(m_{1},m_{2})$. Upon receiving ${\sf
View}_{A}^{\prime}$, we hope that $({\sf View}_{A}^{\prime},{\sf View}_{B})$
has the same distribution as $({\sf View}_{A},{\sf View}_{B})$; if that is
true, based on perfect completeness, any non-zero support in $({\sf
View}_{A},{\sf View}_{B})$ should provide us with the agreed key.

Unfortunately, this does not hold true. The overlap in inputs between $R_{A}$
and $R_{B}$ leads to a correlation in the distribution $({\sf View}_{A},{\sf
View}_{B})$, making it impossible to sample independently. This correlation is
the resource for Alice and Bob to compute an agreed key, akin to Merkle
Puzzles.

The key insight from [IR89, BM09] is to eliminate this correlation, often
referred to as “intersection queries”. In their attacks, Eve queries the
oracle in a manner such that $R_{E}$ encompasses all the shared knowledge
between Alice and Bob. More precisely, for any execution $R_{A},R_{B}$
consistent with $(m_{1},m_{2})$, it holds that $R_{A}\cap R_{B}\subseteq
R_{E}$. Consequently, conditioned on $R_{E}$ and the transcript, the
distribution $({\sf View}_{A},{\sf View}_{B})$ becomes close to a product
distribution. Eve can then sample ${\sf View}_{A}^{\prime}$ conditioned on
$m_{1},m_{2},R_{E}$, and this fake view will yield the correct key.

Finally, [IR89, BM09] demonstrate that as long as Eve queries Alice and Bob’s
“heavy queries” (those with a relatively noticeable probability of being
queried), with high probability $R_{E}$ will contain all intersection queries.

###  2.2 A Quantization Attempt by Austrin et al.

[ACC+22] focuses on the fully general QKA, but here we explain their ideas for
the Merkle-like protocols. The first challenge arises when attempting to
formally describe an execution for both quantum Alice and Bob. As they can
make quantum queries, neither the random coins $s_{A}$ nor the query list
$R_{A}$ can be explicitly delineated. A quantum algorithm can possess
randomness that is impossible to be purified as random coins, and can make
quantum superposition queries. An execution right after Alice and Bob exchange
messages, is represented by $({\sf View}_{A},{\sf View}_{B},m_{1},m_{2},H)$
where ${\sf View}_{A}:=\rho_{A},{\sf View}_{B}:=\rho_{B}$ are the internal
quantum states of Alice and Bob.

To quantize the strategy of [IR89, BM09], one needs to define “heavy quantum
queries” and “quantum intersection queries”, and establish some form of
independence between Alice and Bob conditioned on transcripts and Eve’s
knowledge. Austrin et al., leveraged the breakthrough technique (“compressed
oracle”) by Zhandry [Zha19], defined “heavy quantum queries”. On a very high
level (without introducing Zhandry’s technique), “heavy quantum queries” are
classical inputs that have high weights on the oracle, when the oracle is
examined under the Fourier basis. Their proposed attack queries all “heavy
quantum queries” classically. Under their polynomial compatibility conjecture,
they can argue the success of their attacks.

This approach is less ideal in the following aspects. First, even for Merkle-
like protocols, the polynomial compatibility conjecture seems necessary.
Second, the classical-query Eve has to somehow “simulate” the ability of
quantum Alice or quantum Bob. Although such simulation is believed to be true
for decision problems [AA09], this kind of simulation in the QKA setting is
both unclear to hold and potentially unnecessary. Finally, establishing
independence between two quantum states (quantum Alice and Bob) is challenging
to define and can be intricate.

###  2.3 Step Back — Classical and Quantum Proofs Using Markov Chain

Stepping back, let’s reconsider if there are other approaches that are more
quantum-friendly: potentially can take advantage of quantum-query Eve. The key
insight in [IR89, BM09] is, when conditioned on some query list $R_{E}$ and
$(m_{1},m_{2})$, the distribution $({\sf View}_{A},{\sf View}_{B})$ is a
product distribution, meaning Alice and Bob are independent. Based on this,
Eve can therefore sample ${\sf View}_{A}^{\prime}$ and they together with the
real ${\sf View}_{B}$ have the same distribution as $({\sf View}_{A},{\sf
View}_{B})$.

Our first contribution is to give an alternative view of the classical proofs
for Merkle-like KA. We realize that, in the classical proof, when intersection
queries $R_{A}\cap R_{B}$ always is in $R_{E}$, the conditional mutual
information (CMI) between $R_{A},R_{B}$ conditioned on $E,m_{1},m_{2}$ is 0.

$\displaystyle I({\sf View}_{A}:{\sf View}_{B}|(m_{1},m_{2},R_{E}))=0.$

There are two seemingly classically equivalent consequences when CMI is 0.

  * •

Perspective 1. From Pinsker’s inequality, a CMI of 0 immediately implies that
${\sf View}_{A}$ and ${\sf View}_{B}$ are independent conditioned on
$(m_{1},m_{2},R_{E})$. This further implies that we can sample ${\sf
View}_{A}^{\prime}$ accordingly.

  * •

Perspective 2. Another perspective is that, ${\sf
View}_{B}\rightarrow(m_{1},m_{2},R_{E})\rightarrow{\sf View}_{A}$ forms a
Markov chain.

Three random variables $XYZ$ form a Markov chain if $p_{xyz}=p_{xy}p_{z|y}$.
In our case, it says there exists a way to take $(m_{1},m_{2},R_{E})$ as
inputs and sample ${\sf View}^{\prime}_{A}$ such that $({\sf
View}^{\prime}_{A},{\sf View}_{B})$ and $({\sf View}_{A},{\sf View}_{B})$ are
identically distributed.

The above discussion explains the attacks for Merkle-like protocols, through
the lens of CMI.

From this, we propose one candidate quantum attack for Merkle-like QKA:
Quantum Eve: A Framework • Eve makes some quantum queries and let ${\sf
View}_{E}:=\rho_{E}$ be its internal quantum state. It “somehow” makes sure
that the CMI between Alice and Bob, conditioned on Eve and the transcript is
small enough. $\displaystyle I({\sf View}_{A}:{\sf View}_{B}\mid
m_{1},m_{2},{\sf View}_{E})<\epsilon.$ • Use “some quantum analogy” of 1 or 2
above to produce a quantum state ${\sf View}^{\prime}_{A}:=\rho_{A^{\prime}}$
from $\rho_{E}$ such that, $\displaystyle{\sf View}^{\prime}_{A}{\sf
View}_{B}\approx_{{\sf poly}(\epsilon)}{\sf View}_{A}{\sf View}_{B}.$ There
are two questions remain to be answered:

Does there exist a query-efficient Eve’s strategy that always makes CMI small?

Does there exist a quantum analogy of step 1 or 2?

We answer both of the questions affirmatively.

#### Decreasing CMI.

Assume Alice and Bob each makes at most $d$ queries and
$H:[2^{n}]\to\\{0,1\\}$ be any oracle of domain $[2^{n}]$ and binary range. We
show that,

######  Lemma 2.2 (Informal).

For any standard two-round QKA right after Alice receives $m_{2}$, Eve can run
the same Bob $t$ times for some $t\in\\{0,1,\ldots,2dn/\epsilon\\}$ and store
all $t$ copies of Bob’s internal states, such that the CMI between Alice and
Bob conditioned on Eve’s register and $m_{1},m_{2}$ is at most $\epsilon$.

A couple of things we clarify here. First, why don’t we set $t:=2dn/\epsilon$
(the largest value)? This is due to the nature of quantum conditional mutual
information. Classically, when we condition on more classical queries, the CMI
will never increase. However, quantum entropy and mutual information behave
unlike their classical counterparts. Still, we are able to show the existence
of such small $t$. The existence of such $t$ will not make our Eve non-
uniform, as $t$ is (inefficiently) computable without making any oracle
query.777One can also guess a uniform $t$ if we do not require finding the key
with probability close to $1$.

Second, this strategy works for any oracles. Third, the lemma does not
distinguish between whether $m_{1}$ is classical or quantum. Even if Bob takes
a quantum input, as long as we have access to $t$ copies of the same quantum
state, we can run Bob with the same pure state $t$ times and thus the lemma
still holds. This fact will be useful for the case of quantum public keys.

Finally, the lemma works for any two-round QKA888It is a general lemma that
works for any two-classical-message quantum interactive protocol. We focus on
its application in QKA in this paper.. As Alice and Bob are asymmetric for
general protocols, we do not know how to only simulate Alice’s queries and
make the CMI small in the general two-round QKA case. We will mention it after
finishing the discussion on Merkle-like QKA.

#### Sampling Fake Alice.

When the CMI is small, we need to sample a fake Alice. If the CMI is $0$,
Hayden et al. [HJPW04] showed an approach that can be viewed as a quantum
analogy of Perspective 1. However, their approach only works for the case of
CMI being exactly $0$ and is not robust.

We realize the second interpretation works much better. The work by Fawzi and
Renner showed that

######  Lemma 2.3 (Approximate Quantum Markov Chain, [FR15]).

Let $X,Y,Z$ be three quantum registers, and $\rho_{XYZ}$ be the state. If
$I(X:Z|Y)<\epsilon$, then there exists a channel $\mathcal{T}:Y\to
Y^{\prime}Z^{\prime}$ such that

$\displaystyle\left|\rho_{XZ}-\sigma_{XZ^{\prime}}\right|_{\sf
Tr}\leq\left|\rho_{XYZ}-\sigma_{XY^{\prime}Z^{\prime}}\right|_{\sf Tr}\leq
O(\sqrt{\epsilon}),$

where $\sigma_{XY^{\prime}Z^{\prime}}$ is the state from applying
$\mathcal{T}$ on the $Y$ register of $\rho_{XY}$. Furthermore, $\mathcal{T}$
is explicitly (and inefficiently) constructible if knowing the state
$\rho_{XYZ}$.

On a high level, Lemma 2.3 states that if the CMI $I(X:Z|Y)$ for a tripartite
state $\rho_{XYZ}$ is small enough, then we can apply a local channel on $Y$
to generate a state close to the original state in $XY$. This directly
provides us a way to sample a fake Alice. In our case, $X$ is the view of Bob,
$Z$ is the view of Alice and $Y$ is the view of Eve and the transcript. Thus,
the whole density matrix of $\rho_{XYZ}$ is known by Eve999$\rho_{XYZ}$ in
this case, is not the state under a particular oracle, but the mixed state
averaged over the distribution of all oracles. Only in this case, Eve knows
$\rho_{XYZ}$.. By applying the lemma, Eve can sample $Z^{\prime}:={\sf
View}^{\prime}_{A}$ such that ${\sf View}_{A}^{\prime}{\sf
View}_{B}\approx_{O(\sqrt{\epsilon})}{\sf View}_{A}{\sf View}_{B}$; although
$\mathcal{T}$ in this case could be inefficient, it makes no queries. This
completes the second step of our Eve.

Combining the approach of making the CMI arbitrarily small with the quantum
Markov chain for sampling a fake Alice, our Eve can attack any Merkle-like QKA
in any oracle model. We remark that for a general two-round QKA, Lemma 2.2 and
Lemma 2.3 only cover the part up to receiving the last message $m_{2}$. In the
next subsection, we will discuss how to handle additional queries made after
the last message.

###  2.4 Ruling out QPKE with Classical-Query Key Generation

The exact same idea from the previous section also applies to the standard
two-round QKA as defined in Definition 2.1, particularly when
$\mathcal{A}_{2}$ (or the decryption algorithm) makes no queries to the
oracle. In this scenario, we let ${\sf View}_{A}$ and ${\sf View}_{B}$
represent the views of Alice and Bob right after $m_{1}$ is received by Alice,
and she has not yet begun working on producing the key. When we sample ${\sf
View}_{A}^{\prime}{\sf View}_{B}\approx{\sf View}_{A}{\sf View}_{B}$, since
$\mathcal{A}_{2}$ only applies a local unitary that is independent of the
oracle, Eve can perform the same on the fake view and still successfully
obtain the key. However, what if $\mathcal{A}_{2}$ makes queries?

It is not immediately clear whether our CMI-based method works when
$\mathcal{A}_{1}$, $\mathcal{A}_{2}$, and $\mathcal{B}$ all make classical
queries only, as in the case of classical KA instead of QKA. There are two
attempts, that one might immediately come out.

  * •

Attempt 1: run $\mathcal{A}_{2}$ on the fake ${\sf View}_{A}^{\prime}$ using
any oracle that is compatible with ${\sf View}_{A}^{\prime}$;

  * •

Attempt 2: run $\mathcal{A}_{2}$ on the fake ${\sf View}_{A}^{\prime}$ using
the real oracle.

Unfortunately, both approaches fail. Consider the following two classical
examples for KA.

  * •

Example 1: $\mathcal{A}_{1}$ does not query and does not send messages,
$\mathcal{B}$ sends a random $m_{2}=x$ and both Alice and Bob agree on $H(x)$.

It is easy to see that, even if Eve does not query, $I({\sf View}_{A}:{\sf
View}_{B}|m_{2})=0$ as ${\sf View}_{A}$ is empty. Thus, any oracle
$H^{\prime}$ is consistent with a fake ${\sf View}_{A}^{\prime}$ but with
overwhelming probability, $H^{\prime}(x)\neq H(x)$.

  * •

Example 2: $\mathcal{A}_{1}$ queries $H(0)$ and stores it as $y$, but does not
send messages to $\mathcal{B}$; $\mathcal{B}$ sends a random $m_{2}=x$ that is
not equal to $0$; $\mathcal{A}_{2}$ queries $H(0)$ again and aborts if $y\neq
H(0)$, otherwise the key will be $H(x)$.

In an honest execution, Alice and Bob will always agree on a key $H(x)$ for
some $x\neq 0$ as $y$ is always equal to $H(0)$.

We claim that $I({\sf View}_{A}:{\sf View}_{B}|m_{2})=0$ as ${\sf View}_{A}$
and ${\sf View}_{B}$ have no intersection queries. Let ${\sf
View}^{\prime}_{A}$ be the fake view that consists of some $y^{\prime}$. A
real oracle with overwhelming probability has $H(x)\neq y^{\prime}$, which
fails the second attempt.

Our solution is to combine both Attempt 1 and Attempt 2.

#### Solution for Simulating $\mathcal{A}_{2}$ in the Classical Case.

Our solution provides an alternative proof for the classical impossibility
"PKE is not in Minicrypt" using our CMI-based framework and our solution for
simulating $\mathcal{A}_{2}$ below.

When $\mathcal{A}_{1}$, $\mathcal{A}_{2}$, and $\mathcal{B}$ are all
classical-query algorithms, we propose the following method to execute a fake
${\sf View}_{A}^{\prime}=(s_{A}^{\prime},R_{A}^{\prime})$. Here,
$s_{A}^{\prime}$ represents Alice’s random coins, and $R_{A}^{\prime}$
represents the query list (a list of input-output pairs).

  * •

Run $\mathcal{A}_{2}$ on the fake ${\sf View}_{A}^{\prime}$ using the real
oracle, except for every $x\in R_{A}^{\prime}$, respond with the corresponding
image $y\in R_{A}^{\prime}$.

In other words, we adjust the real oracle such that it is consistent with
$R_{A}^{\prime}$; let’s denote this modified oracle as $H^{\prime}$.

Why it works? Assume we sample ${\sf View}_{A}^{\prime}$ such that ${\sf
View}_{A}^{\prime}{\sf View}_{B}$ has the same distribution as the real views
for Alice and Bob. The fake view ${\sf View}_{A}^{\prime}$ together with the
real ${\sf View}_{B}$ must be reachable under some oracle (not necessarily the
real oracle). Therefore, $R_{A}^{\prime}$ and $R_{B}$ must be consistent. We
also know that, since ${\sf View}_{B}$ is the real view of Bob under the real
oracle $H$, $R_{B}$ and $H$ must also be consistent.

Thus, changing the oracle to be consistent with $R_{A}^{\prime}$ will only
alter its behavior on those $x\notin R_{B}$. That means, under oracle
$H^{\prime}$, this KA will still have a strictly positive probability to end
up with ${\sf View}^{\prime}_{A},{\sf View}_{B},m_{1},m_{2}$. By perfect
completeness, when running $\mathcal{A}_{2}$ on ${\sf View}^{\prime}_{A}$ with
oracle $H^{\prime}$, we must obtain the key held by Bob.

#### Extending to QPKE with Classical-Query Key Generation.

For QKA with $\mathcal{A}_{1}$ making only classical queries (or QPKE with the
key generation making classical queries), we can still run our Eve algorithm
such that $I({\sf View}_{A}:{\sf View}_{B}|(m_{0},m_{1},E))<\epsilon$.
However, since $\mathcal{B}$ is now quantum, ${\sf View}_{B}$ is some quantum
state $\rho_{B}$ and its query list $R_{B}$ is no longer defined.

We repeat our strategy again: sample ${\sf View}_{A}^{\prime}$ and run
$\mathcal{A}_{2}$ on ${\sf View}_{A}^{\prime}$ with oracle $H^{\prime}$ as
defined above (mostly the real oracle, but made consistent with
$R_{A}^{\prime}$). If Bob has low query weights on $R_{A}^{\prime}$, then our
attack still works. If the total query weight of Bob on $R_{A}^{\prime}$ is
$0$, changing the real oracle to $H^{\prime}$ will not change ${\sf View}_{B}$
at all. Similarly, if the weight is small, changing the real oracle to
$H^{\prime}$ will only change ${\sf View}_{B}$ by a small amount [BBBV97].
Thus, we can still argue that ${\sf View}_{A}^{\prime},{\sf
View}_{B},m_{1},m_{2}$ are reachable under $H^{\prime}$ and with perfect
completeness, we must recover the key.

What if Bob has a large query weight on some $x\in R_{A}^{\prime}$? We imagine
a hypothetical Bob, who will first produce ${\sf View}_{B}$, but then keep
running itself from the beginning multiple times and randomly measure one of
its queries. By doing so, the hypothetical Bob’s functionality does not
change; the advantage is now the hypothetical Bob has a _classical list_
$L_{B}$ that consists of all its queries with high weights, with a high
probability.

If we run our Eve with this hypothetical Bob, ${\sf View}_{A}^{\prime}$ must
have $R_{A}^{\prime}$ consistent with $L_{B}$. Thus, changing the oracle to be
consistent with $R_{A}^{\prime}$ will only change its behavior on those
$x\not\in L_{B}$, or in other words, those $x$ that do not have a large query
weight! Then we can use the argument in the previous paragraphs and claim that
${\sf View}_{A}^{\prime},{\sf View}_{B}:=(\rho_{B},L_{B}),m_{1},m_{2}$ are
reachable under $H^{\prime}$ and with perfect completeness, we can get the
key.

#### Handling Quantum Public Keys

Quantum public keys (or quantum $m_{1}$) are handled without additional
efforts using our CMI-based Eve. This further demonstrates the versatility and
power of our new framework; previous approaches based on classical-query Eve
do not extend to this case.

When $m_{1}$ is quantum, the challenge arises in how Eve can effectively run
multiple copies of Bob on quantum input $m_{1}$. In the context of QPKE, the
attacker needs access to multiple copies of the quantum $m_{1}$. If $m_{1}$ is
a pure state, it becomes evident that running the same Bob on the same pure
state $m_{1}$ is feasible, allowing us to minimize the CMI accordingly.
Alternatively, if a query-efficient perfect cloner for $m_{1}$ exists,
multiple runs of the same Bob become possible.

Given that the subsequent analysis relies solely on the capability to run Bob
multiple times on input $m_{1}$, we can extend our conclusion to rule out
perfect complete QPKE with quantum public keys and classical-query key
generation under the condition that the quantum public keys are either pure or
query-efficiently clonable.

##  3 Preliminaries

We refer reader to [NC10] for more details about quantum computing and quantum
information. Below, we mention some backgrounds that are heavily used in this
work.

###  3.1 Distance measures

Let us recall the definition of total variation distance and trace distance.

######  Definition 3.1 (Total variation distance).

For two probabilistic distributions $D_{X},D_{Y}$ over the same finite domain
$\mathcal{X}$, we define its total variation distance as

$\displaystyle
TV(D_{X},D_{Y})=\frac{1}{2}\sum_{x\in\mathcal{X}}|D_{X}(x)-D_{Y}(x)|.$

######  Definition 3.2 (Trace distance).

For two quantum states $\rho,\sigma$, the trace distance between the two
states is

$\displaystyle
TD(\rho,\sigma)=\frac{1}{2}\operatorname{Tr}\left[\sqrt{(\rho-\sigma)^{\dagger}(\rho-\sigma)}\right]=\sup_{0\leq\Lambda\leq
I}\operatorname{Tr}[\Lambda(\rho-\sigma)].$

###  3.2 Quantum Oracle Model and Random Oracle

A quantum oracle algorithm equipped with access to
$H\colon[2^{n_{\lambda}}]\to[2^{m_{\lambda}}]$ is expressed as a series of
unitaries: $U_{1}$, $U_{H}$, $U_{2}$, $U_{H}$, $\cdots$, $U_{T}$, $U_{H}$,
$U_{T+1}$. Here, $U_{i}$ denotes a local unitary acting on the algorithm’s
internal register. Oracle access to $H$ is defined by a unitary transformation
$U_{H}$, where $\ket{x,y}$ is transformed to $\ket{x,y+H(x)}$. For an oracle
algorithm $\mathcal{A}$, we would use $\mathcal{A}^{H}$ to denote the
algorithm $\mathcal{A}$ has classical access to the oracle $H$, and
$\mathcal{A}^{\ket{H}}$ to denote $\mathcal{A}$ has quantum access to the
oracle.

We would also consider the case when the oracle
$H\colon[2^{n_{\lambda}}]\to\\{0,1\\}$ is sampled from some distribution of
oracles $\mathcal{H}_{\lambda}$. We would call some primitive in the quantum
random oracle model(QROM) if the distribution $\mathcal{H}_{\lambda}$ is
uniformly random over all possible oracles.

###  3.3 Entropy

######  Definition 3.3 (Von Neumann Entropy).

Let $\rho\in\mathbb{C}^{2^{n}}$ be a quantum state describing a system
$\mathsf{A}$. Let $\ket{\phi_{1}},\ket{\phi_{2}},\cdots,\ket{\phi_{2^{n}}}$ be
the eigenbasis of $\rho$; $\rho$ is written in this eigenbasis as
$\sum_{i}\eta_{i}\ket{\phi_{i}}\bra{\phi_{i}}$.

Then its Von Neumann Entropy is denoted by $S(\rho)$ (or
$S(\mathsf{A})_{\rho}$),

$\displaystyle S(\mathsf{A})_{\rho}=S(\rho)=-\sum_{i}\eta_{i}\log(\eta_{i}).$

Given a composite quantum system $\mathsf{A}\mathsf{B}$ having joint state
$\rho_{\mathsf{A}\mathsf{B}}$, we define the conditional Von Neumann Entropy
as $S(\mathsf{A}|\mathsf{B})_{\rho}$,

$\displaystyle
S(\mathsf{A}|\mathsf{B})_{\rho}=S(\mathsf{A}\mathsf{B})_{\rho}-S(\mathsf{B})_{\rho}.$

Below, we often omit $\rho$ in the definition when the quantum state is clear
in the context. For example, $S(\mathsf{A})$ and $I(\mathsf{A}:\mathsf{B})$
instead of $S(\mathsf{A})_{\rho}$ and $I(\mathsf{A}:\mathsf{B})_{\rho}$.

######  Fact 3.4 ([NC10]).

Suppose $p_{k}$ are probabilities, $\ket{k}$ are orthogonal basis of a system
$\mathsf{A}$ and $\rho_{k}$ are quantum states for another system
$\mathsf{B}$. Then

$S\left(\sum_{k}p_{k}\ket{k}\bra{k}\otimes\rho_{k}\right)=H(p_{k})+\sum_{k}p_{k}S(\rho_{k})$

where $H(p_{k})$ is the Shannon entropy of distribution $p_{k}$.

######  Fact 3.5 ([Wil11]).

If $\rho_{\mathsf{A}\mathsf{B}}$ is a separable state, then
$S(\mathsf{A}|\mathsf{B})\geq 0$.

######  Definition 3.6 (Mutual Information).

Let $\rho$ be a quantum state describing two joint systems $\mathsf{A}$ and
$\mathsf{B}$. Then the mutual information between the system $A$ and $B$ is
denoted by $I(\mathsf{A}:\mathsf{B})$,

$\displaystyle
I(\mathsf{A}:\mathsf{B})=S(\mathsf{A})+S(\mathsf{B})-S(\mathsf{A}\mathsf{B}).$

######  Definition 3.7 (Conditional Mutual Information).

Let $\rho$ be a quantum state describing three joint systems $\mathsf{A}$,
$\mathsf{B}$ and $\mathsf{C}$. Then the conditional mutual information
$I(\mathsf{A}:\mathsf{B}|\mathsf{C})$,

$\displaystyle I(\mathsf{A}:\mathsf{B}|\mathsf{C})$
$\displaystyle=S(\mathsf{A}\mathsf{C})+S(\mathsf{B}\mathsf{C})-S(\mathsf{A}\mathsf{B}\mathsf{C})-S(\mathsf{C}).$

######  Fact 3.8 (Chain rule).

$I(\mathsf{A}_{1},\mathsf{A}_{2},\cdots,\mathsf{A}_{t}:\mathsf{B}\mid\mathsf{C})=\sum_{i=1}^{t}I(\mathsf{A}_{i}:\mathsf{B}\mid\mathsf{C},\mathsf{A}_{1},\cdots,\mathsf{A}_{i-1})$.

######  Fact 3.9.

Let $\mathsf{A}\mathsf{B}\mathsf{C}$ be a composite quantum system. When a
unitary is applied on $\mathsf{A}$, it will not change $S(\mathsf{A})$.
Similarly, the local unitary on $\mathsf{A}$ will not change
$I(\mathsf{A}:\mathsf{B})$ or $I(\mathsf{A}:\mathsf{B}|\mathsf{C})$.

###### Proof.

This directly follows from the definition of $S(\mathsf{A})$ and applying any
unitary will not change the spectrum of a density matrix. ∎

The strong subadditivity for (conditional) mutual information concludes that
both mutual information and conditional mutual information are always non-
negative.

######  Lemma 3.10 (Strong Subadditivity, [AL70]).

Given Hilbert spaces $\mathsf{A},\mathsf{B},\mathsf{C}$,

$\displaystyle S(\mathsf{A}\mathsf{C})+S(\mathsf{A}\mathsf{B})\geq
S(\mathsf{A}\mathsf{B}\mathsf{C})+S(\mathsf{C}).$

(The conditional form) Given Hilbert spaces
$\mathsf{A},\mathsf{B},\mathsf{C},\mathsf{D}$,

$\displaystyle
S(\mathsf{A}\mathsf{C}|\mathsf{D})+S(\mathsf{A}\mathsf{B}|\mathsf{D})\geq
S(\mathsf{A}\mathsf{B}\mathsf{C}|\mathsf{D})+S(\mathsf{C}|\mathsf{D}).$

###  3.4 Operational Meaning of Conditional Mutual Information: Approximate
Quantum Markov Chain

Fawzi and Renner [FR15] provided a nice characterization of quantum states for
which the conditional mutual information is approximately zero. Intuitively,
if $I(\mathsf{A}:\mathsf{B}\mid\mathsf{E})$ is small, then $\mathsf{B}$ can be
approximately reconstructed from $\mathsf{E}$.

######  Theorem 3.11 ([FR15], restate of Lemma 2.3).

For any state $\rho_{{\sf AEB}}$ over systems
$\mathsf{A}\mathsf{E}\mathsf{B}$, there exists a channel ${\cal T}:{\sf
E}\to{\sf E}\otimes{\sf B}^{\prime}$ such that the trace distance between the
reconstructed state $\sigma_{\sf A^{\prime}E^{\prime}B^{\prime}}={\cal
T}(\rho_{\mathsf{A}\mathsf{E}})$ and the original state $\rho_{\sf AEB}$ is at
most

$\displaystyle\sqrt{\ln 2\cdot I(\mathsf{A}:\mathsf{B}|\mathsf{E})_{\rho}}.$

###  3.5 Quantum Key Agreement and Quantum Public Key Encryption

In the following, we provide formal definitions of quantum key agreement (QKA)
and quantum public key encryption (QPKE) in the oracle model.

######  Definition 3.12 (Quantum Key Agreement in the Oracle Model).

Let $\lambda\in\mathbb{Z}_{+}$ be the security parameter and
$\mathcal{H}_{\lambda}$ be a distribution of oracles. Let
$H\leftarrow\mathcal{H}_{\lambda}$ be a classical oracle, drawn according to
$\mathcal{H}_{\lambda}$.

A key agreement protocol consists of two parties Alice and Bob, who start with
all-zero states and have the ability to apply any quantum operator, get
quantum access to $H$, and send classical messages to each other.

Both Alice and Bob can make at most ${\sf poly}(\lambda)$ number of quantum
queries to $H$. Finally, Alice and Bob output classical strings
$k_{A},k_{B}$101010$k_{A},k_{B}$ can be of any length (even exponential in
$\lambda$). Our impossibility results apply to protocols with any output key
length.. We would call the set of classical messages between Alice and Bob,
denoted by $\Pi$, the transcript of the key exchange protocol.

A key agreement protocol should satisfy both correctness and security.

######  Definition 3.13 (Correctness).

Let $k_{A},k_{B}$ be the keys outputted in the protocol. Then
$\Pr[k_{A}=k_{B}]\geq 1/q(\lambda)$ for some polynomial $q(\cdot)$, where the
probability is taken over the randomness of Alice and Bob’s channels, and the
random choice of oracle $H$.

######  Definition 3.14 (Security).

For any eavesdropper Eve that makes at most ${\sf poly}(\lambda)$ number of
quantum queries to $H\leftarrow\mathcal{H}_{\lambda}$, eavesdrops classical
communication between Alice and Bob and outputs $k_{E}$, the probability that
$\Pr[k_{A}=k_{E}]$ is negligible in $\lambda$.

We are interested in whether there exists a protocol that satisfies both
correctness and security in the QROM. It is worth noting that the ability of
making quantum queries is essential in our setting; when Alice and Bob can
only make polynomially many classical queries, secure key agreement does not
exist; i.e., there always exists an eavesdropper making polynomially many
classical queries and breaking it [IR89, BM09].

We also focus on breaking quantum public key encryption schemes in the oracle
model.

######  Definition 3.15 (Quantum Public Key Encryption in the Oracle Model).

Let $\lambda\in\mathbb{Z}_{+}$ be the security parameter and
$\mathcal{H}_{\lambda}$ be a distribution over oracles
$H\colon[2^{n_{\lambda}}]\to\\{0,1\\}$. Let $H\leftarrow\mathcal{H}_{\lambda}$
be a classical oracle, a QPKE scheme in the oracle model consists of three
algorithms (${\sf Gen},{\sf Enc},{\sf Dec}$), each of which is allowed to make
at most $d(\lambda)={\sf poly}(\lambda)$ quantum queries to $H$:

  * •

${\sf Gen}^{\ket{H}}(1^{\lambda})\to({\sf pk},{\sf sk})$: The quantum key
generation algorithm that generates a pair of classical public key ${\sf pk}$
and secret key ${\sf sk}$.

  * •

${\sf Enc}^{\ket{H}}({\sf pk},m)\to{\sf ct}$: the quantum encryption algorithm
that takes a public key ${\sf pk}$, the plaintext $m$, produces the ciphertext
${\sf ct}$.

  * •

${\sf Dec}^{\ket{H}}({\sf sk},{\sf ct})\to m^{\prime}$: the quantum decryption
algorithm that takes secret key ${\sf sk}$ and ciphertext ${\sf ct}$ and
outputs the plaintext $m^{\prime}$.

The algorithms should satisfy the following requirements:

Completeness

$\Pr\left[{\sf Dec}^{\ket{H}}\left({\sf sk},{\sf Enc}^{\ket{H}}({\sf
pk},m)\right)=m\colon{\sf Gen}^{\ket{H}}(1^{\lambda})\to({\sf pk},{\sf
sk})\right]\geq 1-{\sf negl}(\lambda)$.

IND-CPA Security

For any adversary $\mathcal{E}^{\ket{H}}$ that makes ${\sf poly}(\lambda)$
queries, for every two plaintexts $m_{0}\neq m_{1}$ chosen by
$\mathcal{E}^{\ket{H}}({\sf pk})$, we have

$\displaystyle\Pr\left[\mathcal{E}^{\ket{H}}\left({\sf pk},{\sf
Enc}^{\ket{H}}({\sf pk},m_{b})\right)=b\right]\leq\frac{1}{2}+{\sf
negl}(\lambda).$

Especially in Section 6, we will focus on when the key generation algorithm
${\sf Gen}^{H}$ is an algorithm with classical access to the oracle $H$.

It is a folklore result that we can construct a two-round key agreement
protocol from a public key encryption scheme as follows:

  1. 1.

Alice runs ${\sf Gen}^{\ket{H}}$ to produce a public key ${\sf pk}$ and a
secret ${\sf sk}$, and sends the public key ${\sf pk}$ as the first message
$m_{1}$ to Bob. We call Alice’s algorithm at this stage $\mathcal{A}_{1}$.

  2. 2.

Bob upon receiving ${\sf pk}$, it samples a uniformly random classical string
$k$ as the key. It computes the ciphertext ${\sf ct}\leftarrow{\sf
Enc}^{\ket{H}}({\sf pk},k)$ and sends $m_{2}:={\sf ct}$ to Alice. We call
Bob’s algorithm at this stage $\mathcal{B}$.

  3. 3.

Alice will then run ${\sf Dec}^{\ket{H}}({\sf sk},{\sf ct})$ to output
$k^{\prime}$, which is her guess of $k$. We call Alice’s algorithm at this
stage $\mathcal{A}_{2}$.

We further notice that the only information required by $\mathcal{A}_{2}$ from
$\mathcal{A}_{1}$ is the secret key ${\sf sk}$. Thus if ${\sf sk}$ is
classical, we can assume without loss of generality that the internal state of
$\mathcal{A}_{1}$ at its termination is a mixed state in the computational
basis.

We would also consider the recently proposed QPKE with quantum public key
[BGH+23, KMNY23, Col23] in Section 6. We would only focus on the variant where
the protocol is perfect complete, and key generation algorithms can only make
classical queries.

######  Definition 3.16 (QPKE with quantum public key).

Let $\lambda\in\mathbb{Z}_{+}$ be the security parameter and
$\mathcal{H}_{\lambda}$ be a distribution over oracles
$H\colon[2^{n_{\lambda}}]\to\\{0,1\\}$. Let $H\leftarrow\mathcal{H}_{\lambda}$
be a classical oracle, a QPKE scheme in the oracle model consists of four
algorithms (${\sf SKGen},{\sf PKGen},{\sf Enc},{\sf Dec}$), each of which is
allowed to make at most $d(\lambda)={\sf poly}(\lambda)$ queries to $H$:

  * •

${\sf SKGen}^{{H}}(1^{\lambda})\to{\sf sk}$: The secret key generation
algorithm that generates a classical secret key ${\sf sk}$.

  * •

${\sf PKGen}^{{H}}({\sf sk})\to\rho_{{\sf pk}}$: The public key generation
algorithm that takes the secret key ${\sf sk}$ and generates a quantum public
key $\rho_{{\sf pk}}$.

  * •

${\sf Enc}^{\ket{H}}(\rho_{{\sf pk}},m)\to{\sf ct}$: the quantum encryption
algorithm that takes a public key ${\sf pk}$, the plaintext $m$, produces the
(possibly quantum) ciphertext $\rho_{{\sf ct}}$.

  * •

${\sf Dec}^{\ket{H}}({\sf sk},\rho_{{\sf ct}})\to m^{\prime}$: the quantum
decryption algorithm that takes secret key ${\sf sk}$ and ciphertext ${\sf
ct}$ and outputs the plaintext $m^{\prime}$.

The algorithms should satisfy the following requirements:

Perfect Completeness

$\Pr\left[{\sf Dec}^{\ket{H}}\left({\sf sk},{\sf Enc}^{\ket{H}}(\rho_{{\sf
pk}},m)\right)=m\colon{\sf SKGen}^{{H}}(1^{\lambda})\to{\sf sk},{\sf
PKGen}^{H}({\sf sk})\to\rho_{{\sf pk}}\right]=1.$

IND-CPA Security

For any adversary $\mathcal{E}^{\ket{H}}$ that makes ${\sf poly}(\lambda)$
queries, given any polynomial copies of public key $\rho_{{\sf pk}}^{\otimes
t(\lambda)}$, for every two plaintexts $m_{0}\neq m_{1}$ chosen by
$\mathcal{E}(\rho_{{\sf pk}}^{\otimes t(\lambda)})$, we have

$\displaystyle\Pr\left[\mathcal{E}^{\ket{H}}\left(\rho_{{\sf pk}}^{\otimes
t(\lambda)},{\sf Enc}^{\ket{H}}(\rho_{{\sf
pk}},m_{b})\right)=b\right]\leq\frac{1}{2}+{\sf negl}(\lambda).$

We call the public key pure if given ${\sf sk}$, $\rho_{{\sf
pk}}\leftarrow{\sf PKGen}({\sf sk})$ is a pure state, and call the public key
clonable if there is some polynomial query algorithm $\mathcal{D}^{\ket{H}}$
that takes $\rho_{{\sf pk}}=\sum p_{i}\ket{\psi_{i}}\bra{\psi_{i}}$ in its
eigenvector decomposition, and generates the state $\rho^{\prime}=\sum
p_{i}\ket{\psi_{i}}\bra{\psi_{i}}^{\otimes{t(\lambda)}}$ for some polynomial
$t(\cdot)$.

######  Remark 3.17.

The definition of clonable here might seem odd at first glance, we would give
some examples here for further explanations. The public key generation
algorithm from [KMNY23, MW23] ${\sf PKGen}({\sf sk})$ generates a $\rho_{{\sf
pk}}=({\sf pk}_{r},\ket{\psi_{r}})$ according to some private coin $r$ of
${\sf PKGen}({\sf sk})$, where ${\sf pk}_{r}$ is a classical string,
$\ket{\psi_{r}}$ is a pure quantum state. Thus our cloning algorithm
$\mathcal{D}$ can be seen as given a sample $({\sf pk}_{r},\ket{\psi_{r}})$,
it can generate multiple copies of state $\ket{\psi_{r}}$.

##  4 Helper Lemmas

In this section, we introduce three helper lemmas. Lemma 4.2 tells how to
decrease CMI. Lemma 4.3 and Lemma 4.4 claim that classical communication does
not increase CMI. Lemma 4.6 will be used in Section 6.

###  4.1 Repetition Decreases CMI

######  Definition 4.1 (Permutation Invariance).

Let
$\mathsf{A}_{1},\mathsf{A}_{2},\mathsf{A}_{3},\ldots,\mathsf{A}_{t},\mathsf{B}$
be $(t+1)$-partite quantum system. Given the joint state
$\rho_{\mathsf{B}\mathsf{A}_{1}\mathsf{A}_{2}\cdots\mathsf{A}_{t}}$, we say
$A_{1},\ldots,A_{t}$ are permutation invariant, if for any permutation $\pi$
on $[t]$, we have

$\rho_{\mathsf{B}\mathsf{A}_{1}\mathsf{A}_{2}\cdots\mathsf{A}_{t}}=\rho_{\mathsf{B}\mathsf{A}_{\pi(1)}\mathsf{A}_{\pi(2)}\cdots\mathsf{A}_{\pi(t)}}.$

######  Lemma 4.2.

Let
$\mathsf{A}_{1},\mathsf{A}_{2},\mathsf{A}_{3},\ldots,\mathsf{A}_{t},\mathsf{B},\mathsf{C}$
be $(t+2)$-partite quantum system. Suppose the state of the composite system
$\rho_{\mathsf{B}\mathsf{C}\mathsf{A}_{1}\mathsf{A}_{2}\cdots\mathsf{A}_{t}}$
is fully separable. If
$\mathsf{A}_{1},\mathsf{A}_{2},\mathsf{A}_{3},\ldots,\mathsf{A}_{t}$ are
permutation invariant, then there is a $0\leq i\leq t-1$ such that

$I(\mathsf{A}_{t}:\mathsf{B}\mid\mathsf{C},\mathsf{A}_{1},\ldots,\mathsf{A}_{i})_{\rho}\leq
S(\mathsf{B})/t.$

###### Proof.

By the chain rule of conditional mutual information (see Fact 3.8), we have

$\sum_{i=1}^{t}I(\mathsf{A}_{i}:\mathsf{B}\mid\mathsf{C},\mathsf{A}_{1},\ldots,\mathsf{A}_{i-1})=I(\mathsf{A}_{1},\ldots,\mathsf{A}_{t}:\mathsf{B}\mid\mathsf{C})$
(1)

Besides,

$I(\mathsf{A}_{1},\ldots,\mathsf{A}_{t}:\mathsf{B}\mid\mathsf{C})=S(\mathsf{B}\mid\mathsf{C})-S(\mathsf{B}\mid\mathsf{C},\mathsf{A}_{1},\ldots,\mathsf{A}_{t})\leq
S(\mathsf{B}\mid\mathsf{C})\leq S(\mathsf{B}),$ (2)

where the inequalities are by 3.5 and that
$I(\mathsf{B}:\mathsf{C})=S(\mathsf{B})-S(\mathsf{B}\mid\mathsf{C})$ is always
non-negative. By (1) and (2), there must exist $i\in[t]$ such that
$I(\mathsf{A}_{i}:\mathsf{B}\mid\mathsf{C},\mathsf{A}_{1},\ldots,\mathsf{A}_{i-1})\leq
S(\mathsf{B})/t$. Finally, by the permutation invariance, we have
$I(\mathsf{A}_{i}:\mathsf{B}\mid\mathsf{C},\mathsf{A}_{1},\ldots,\mathsf{A}_{i-1})=I(\mathsf{A}_{t}:\mathsf{B}\mid\mathsf{C},\mathsf{A}_{1},\ldots,\mathsf{A}_{i-1})$.
Now we finish the proof. ∎

###  4.2 Classical Communication does not Increase CMI

######  Lemma 4.3 (Local quantum operation does not increase CMI).

Let $\mathsf{A}\mathsf{B}\mathsf{C}$ be a composite quantum system. After
performing a quantum operation $M$ on $\mathsf{A}$, the state of the system
becomes $\mathsf{A}^{\prime}\mathsf{B}^{\prime}\mathsf{C}^{\prime}$. Then
$I(\mathsf{A}^{\prime}:\mathsf{B}^{\prime}|\mathsf{C}^{\prime})\leq
I(\mathsf{A}:\mathsf{B}|\mathsf{C})$.

###### Proof.

We introduce another quantum system $\mathsf{D}$, initialized as zero. The
quantum operation $M$ can be treated as first performing a unitary
transformation $U$ on $\mathsf{A}\mathsf{D}$ and then discarding $\mathsf{D}$.

$\displaystyle I(\mathsf{A}:\mathsf{B}|\mathsf{C})$
$\displaystyle=I(\mathsf{A}\mathsf{D}:\mathsf{B}|\mathsf{C})$
$\displaystyle=I(U(\mathsf{A}\mathsf{D})U^{\dagger}:\mathsf{B}|\mathsf{C})$
$\displaystyle=I(\mathsf{A}^{\prime}\mathsf{D}^{\prime}:\mathsf{B}^{\prime}|\mathsf{C}^{\prime})$
$\displaystyle=S(\mathsf{A}^{\prime}\mathsf{D}^{\prime}|\mathsf{C}^{\prime})-S(\mathsf{A}^{\prime}\mathsf{D}^{\prime}\mathsf{B}^{\prime}|\mathsf{C}^{\prime})+S(\mathsf{B}^{\prime}|\mathsf{C}^{\prime}).$

By the conditional form of strong sub-additivity (see the condition form of
Lemma 3.10),
$S(\mathsf{A}^{\prime}\mathsf{D}^{\prime}|\mathsf{C}^{\prime})-S(\mathsf{A}^{\prime}\mathsf{D}^{\prime}\mathsf{B}^{\prime}|\mathsf{C}^{\prime})\geq
S(\mathsf{A}^{\prime}|\mathsf{C}^{\prime})-S(\mathsf{A}^{\prime}\mathsf{B}^{\prime}|\mathsf{C}^{\prime})$.
Then

$\displaystyle I(\mathsf{A}:\mathsf{B}|\mathsf{C})$ $\displaystyle\geq
S(\mathsf{A}^{\prime}|\mathsf{C}^{\prime})-S(\mathsf{A}^{\prime}\mathsf{B}^{\prime}|\mathsf{C}^{\prime})+S(\mathsf{B}^{\prime}|\mathsf{C}^{\prime})$
$\displaystyle=I(\mathsf{A}^{\prime}:\mathsf{B}^{\prime}|\mathsf{C}^{\prime}).\qed$

######  Lemma 4.4 (Sending classical message does not increase CMI).

Let $\mathsf{A}\mathsf{B}\mathsf{C}$ be a composite quantum system and
$\mathsf{A}=(\mathsf{W}_{\mathsf{A}},\mathsf{M}_{\mathsf{A}})$ where
$\mathsf{W}_{\mathsf{A}}$ is the working register and
$\mathsf{M}_{\mathsf{A}}$ is the message register containing a classical
state. After $\mathsf{B}$ and $\mathsf{C}$ both obtain a copy of
$\mathsf{M}_{\mathsf{A}}$, the system becomes
$\mathsf{A}^{\prime}\mathsf{B}^{\prime}\mathsf{C}^{\prime}$. Then
$I(\mathsf{A}^{\prime}:\mathsf{B}^{\prime}|\mathsf{C}^{\prime})\leq
I(\mathsf{A}:\mathsf{B}|\mathsf{C})$.

The following claim will be used.

######  Claim 4.5 (Copying classical state does not change entropy).

Given a system $\sf P\mathsf{Q}\mathsf{R}$ where $\mathsf{Q}$ and $\mathsf{R}$
contain identical classical states. Then $S(\sf P\mathsf{Q}\mathsf{R})=S(\sf
P\mathsf{R})=S(\sf P\mathsf{Q})$.

###### Proof.

The joint state of $\sf P\mathsf{Q}\mathsf{R}$ can be written as

$\sum_{k}p_{k}\rho_{\sf
P}^{(k)}\otimes\ket{k}\bra{k}_{\mathsf{Q}}\otimes\ket{k}\bra{k}_{\mathsf{R}}$

where $p_{k}$ are probabilities, $\rho_{\sf P}^{(k)}$ are quantum states in
$\sf P$, and $\ket{k}$ are computational basis of $\mathsf{Q}$ (also
$\mathsf{R}$). Then by 3.4,

$\displaystyle S(\sf P\mathsf{Q}\mathsf{R})$
$\displaystyle=S\left(\sum_{k}p_{k}\rho_{\sf
P}^{(k)}\otimes\ket{k}\bra{k}_{\mathsf{Q}}\otimes\ket{k}\bra{k}_{\mathsf{R}}\right)$
$\displaystyle=H(p_{k})+\sum_{k}p_{k}S\left(\rho_{\sf
P}^{(k)}\right)=S\left(\sum_{k}p_{k}\rho_{\sf
P}^{(k)}\otimes\ket{k}\bra{k}_{\mathsf{Q}}\right)=S(\sf P\mathsf{Q}).$

By symmetry, $S(\sf P\mathsf{Q}\mathsf{R})=S(\sf P\mathsf{R})=S(\sf
P\mathsf{Q})$. ∎

###### Proof of Lemma 4.4.

Let
$\mathsf{B}^{\prime}=(\mathsf{B},\mathsf{M}_{\mathsf{B}}),\mathsf{C}^{\prime}=(\mathsf{C},\mathsf{M}_{\mathsf{C}})$
where $\mathsf{M}_{\mathsf{B}},\mathsf{M}_{\mathsf{C}}$ are the message
registers which contain a copy of $\mathsf{M}_{\mathsf{A}}$. Then

$\displaystyle I(\mathsf{A}^{\prime}:\mathsf{B}^{\prime}|\mathsf{C}^{\prime})$
$\displaystyle=I(\mathsf{W}_{\mathsf{A}},\mathsf{M}_{\mathsf{A}}:\mathsf{B},\mathsf{M}_{\mathsf{B}}|\mathsf{C},\mathsf{M}_{\mathsf{C}})$
$\displaystyle=S(\mathsf{W}_{\mathsf{A}},\mathsf{C},\mathsf{M}_{\mathsf{A}},\mathsf{M}_{\mathsf{C}})+S(\mathsf{B},\mathsf{C},\mathsf{M}_{\mathsf{B}},\mathsf{M}_{\mathsf{C}})-S(\mathsf{W}_{\mathsf{A}},\mathsf{B},\mathsf{C},\mathsf{M}_{\mathsf{A}},\mathsf{M}_{\mathsf{B}},\mathsf{M}_{\mathsf{C}})-S(\mathsf{C},\mathsf{M}_{\mathsf{C}}).$

Since
$\mathsf{M}_{\mathsf{A}},\mathsf{M}_{\mathsf{B}},\mathsf{M}_{\mathsf{C}}$
contain identical classical states, by 4.5, we can remove
$\mathsf{M}_{\mathsf{A}},\mathsf{M}_{\mathsf{B}}$ from above equation while
keeping each term unchanged. Then

$\displaystyle I(\mathsf{A}^{\prime}:\mathsf{B}^{\prime}|\mathsf{C}^{\prime})$
$\displaystyle=S(\mathsf{W}_{\mathsf{A}},\mathsf{C},\mathsf{M}_{\mathsf{C}})+S(\mathsf{B},\mathsf{C},\mathsf{M}_{\mathsf{C}})-S(\mathsf{W}_{\mathsf{A}},\mathsf{B},\mathsf{C},\mathsf{M}_{\mathsf{C}})-S(\mathsf{C},\mathsf{M}_{\mathsf{C}})$
$\displaystyle=I(\mathsf{W}_{\mathsf{A}}:\mathsf{B}|\mathsf{C},\mathsf{M}_{\mathsf{C}})$
$\displaystyle=I(\mathsf{W}_{\mathsf{A}},\mathsf{M}_{\mathsf{C}}:\mathsf{B}|\mathsf{C})-I(\mathsf{M}_{\mathsf{C}}:\mathsf{B}|\mathsf{C}).$

By the non-negativity of $I(\mathsf{M}_{\mathsf{C}}:\mathsf{B}|\mathsf{C})$,

$\displaystyle I(\mathsf{A}^{\prime}:\mathsf{B}^{\prime}|\mathsf{C}^{\prime})$
$\displaystyle\leq
I(\mathsf{W}_{\mathsf{A}},\mathsf{M}_{\mathsf{C}}:\mathsf{B}|\mathsf{C})$
$\displaystyle=S(\mathsf{W}_{\mathsf{A}},\mathsf{C},\mathsf{M}_{\mathsf{C}})+S(\mathsf{B},\mathsf{C})-S(\mathsf{W}_{\mathsf{A}},\mathsf{B},\mathsf{C},\mathsf{M}_{\mathsf{C}})-S(\mathsf{C}).$

Since $\mathsf{M}_{\mathsf{A}}$ and $\mathsf{M}_{\mathsf{C}}$ are identical
classical states, $\mathsf{M}_{\mathsf{C}}$ can be replaced with
$\mathsf{M}_{\mathsf{A}}$ by 4.5. Then

$\displaystyle I(\mathsf{A}^{\prime}:\mathsf{B}^{\prime}|\mathsf{C}^{\prime})$
$\displaystyle\leq
S(\mathsf{W}_{\mathsf{A}},\mathsf{C},\mathsf{M}_{\mathsf{A}})+S(\mathsf{B},\mathsf{C})-S(\mathsf{W}_{\mathsf{A}},\mathsf{B},\mathsf{C},\mathsf{M}_{\mathsf{A}})-S(\mathsf{C})$
$\displaystyle=I(\mathsf{W}_{\mathsf{A}},\mathsf{M}_{\mathsf{A}}:\mathsf{B}|\mathsf{C})=I(\mathsf{A}:\mathsf{B}|\mathsf{C}).\qed$

###  4.3 Other Useful Lemmas

We would also need the following lemma.

######  Lemma 4.6.

For two classical probabilistic distributions $D_{X}$ and $D_{Y}$ over the
same domain, if
$TV(D_{X},D_{Y})\leq\epsilon$, we have that

$\displaystyle\Pr_{x\leftarrow D_{X}}[x\notin\mathsf{SUPP}(D_{Y})]\leq
2\epsilon.$

###### Proof.

We use $p_{x}^{X},p_{x}^{Y}$ to denote the probability of $x$ drawn from
$D_{X},D_{Y}$ respectively.

$\displaystyle\sum_{x\notin\mathsf{SUPP}(D_{Y})}p_{x}^{X}\leq\sum_{x}|p_{x}^{X}-p_{x}^{Y}|=2TV(D_{X},D_{Y})\leq
2\epsilon.\quad\quad\qed$

##  5 Non-Interactive Quantum Key Agreement

We say a QKA is _non-interactive_ if all queries are made before
communication. Formally,

######  Definition 5.1 (Non-interactive Quantum Key Agreement).

A non-interactive key agreement protocol between Alice and Bob consists of the
following steps:

  1. 1.

Let $\lambda>0$ be a security parameter and
$H\leftarrow\mathcal{H}_{\lambda}$.

  2. 2.

Alice and Bob each makes $d_{\lambda}={\sf poly}(\lambda)$ queries to $H$.

  3. 3.

Alice and Bob continue an arbitrary number of rounds of classical
communication and local quantum operations, but will never make queries to
$H$.

  4. 4.

Eventually, Alice and Bob will output $k_{A},k_{B}$.

######  Theorem 5.2.

Non-interactive QKA does not exist in any oracle model.

###### Proof.

Let $e_{\lambda}$ denote the number of qubits on which the quantum query
unitary $U_{H}$ acts, i.e., the total length of the input register and the
output register. For example, if $H:[2^{n_{\lambda}}]\rightarrow\\{0,1\\}$ is
a random function, then $e_{\lambda}=n_{\lambda}+1$. Let
$\rho_{\mathsf{A}}^{0}$ and $\rho_{\mathsf{B}}^{0}$ denote the states of Alice
and Bob respectively right after the query algorithm but before any
communication.

First, Eve repeatedly runs the same Alice’s query algorithm
$t=Cd_{\lambda}e_{\lambda}$ times ($C$ is some polynomial determined
afterwards) and prepares the state $\rho_{\mathsf{E}}^{0}$, which consists of
$t$ registers $\mathsf{A}_{1}^{0},\ldots,\mathsf{A}_{t}^{0}$ of
$\rho_{\mathsf{A}}^{0}$’s copies. Observing that
$\mathsf{A}^{0},\mathsf{A}_{1}^{0},\ldots,\mathsf{A}_{t}^{0}$ are permutation
invariant, by Lemma 4.2, we have

$I(\mathsf{A}^{0}:\mathsf{B}^{0}\mid\mathsf{E}^{0})\leq\frac{S(\mathsf{B}^{0})}{t+1}\leq\frac{2d_{\lambda}e_{\lambda}}{t+1}\leq\frac{1}{2C}.$

The second inequality is because we can implement the query unitary $U_{H}$ by
a quantum communication process: suppose there are two parties, namely Bob and
Oracle; if Bob wants to apply the unitary $U_{H}$, then

  1. 1.

Bob sends its input register and output register, $e_{\lambda}$ qubits in
total, to Oracle;

  2. 2.

Oracle applies $U_{H}$ on these $e_{\lambda}$ qubits and then sends them back
to Bob.

By subadditivity of entropy, the entropy of Bob can increase by at most
$2e_{\lambda}$ bits through the above quantum communication process. Since
$\mathsf{B}^{0}$ is prepared from a pure state by making $d$ quantum queries,
we have that $S(\mathsf{B}^{0})\leq 2d_{\lambda}e_{\lambda}$.

Let $\rho_{A}^{f}$ and $\rho_{B}^{f}$ denote the states of Alice and Bob
respectively right after finishing the communication but before outputting the
key. Since classical communication does not increase CMI (see Lemma 4.4), we
have

$I(\mathsf{A}:\mathsf{B}\mid\mathsf{E},\Pi)_{\rho_{ABE}^{f}}\leq
I(\mathsf{A}:\mathsf{B}\mid\mathsf{E})_{\rho_{ABE}^{0}}\leq\frac{1}{2C}.$

Finally, Eve applies the channel in Lemma 2.3 and obtains a fake view
$\hat{\mathsf{A}}^{f}$ of $\mathsf{A}^{f}$ such that the joint state of
$\rho_{\hat{A}B}^{f}$ is $O(1/\sqrt{C})$-close to $\rho_{{A}B}^{f}$. By
letting $C=O(1/\epsilon^{2})$ , Eve can use $\hat{\mathsf{A}}^{f}$ to generate
$k_{E}$ such that $\Pr[k_{B}=k_{E}]$ is $\epsilon$-close to
$\Pr[k_{A}=k_{E}]$. ∎

######  Remark 5.3.

(a). Theorem 5.2 directly implies the separation of pseudorandom quantum
states (PRS) and QKA. This is because PRS can be prepared by random queries,
and without loss of generality, we can assume all random queries are made at
the very beginning before any communication.

(b). In the proof of Theorem 5.2, Eve makes $O(d_{\lambda}^{2}e_{\lambda})$
quantum queries. This bound can be improved to
$\widetilde{O}(d_{\lambda}^{2})$ if Alice and Bob are restricted to making
non-adaptive queries (i.e., queries can depend on neither any previous queries
nor classical communication) to a random function. The famous Merkle Puzzles
and PRS-based protocols are both examples of this non-adaptive case. We refer
interested readers to Appendix B for details.

(c). By almost the same proof, Theorem 5.2 can be extended to include quantum
oracles, e.g., Haar random oracles, where the query unitary operator is chosen
from some Haar measure.

We can further notice that the non-interactive requirement can be relaxed to
one-sided if we are considering two-round key agreement protocols. That is,
Bob can make queries after receiving the first message from Alice, while Alice
can only make queries before communication. Viewing the protocol in the model
of QPKE, we have the following theorem:

######  Theorem 5.4 (Restate of Theorem 1.3).

For any QPKE scheme with a classical public key and a classical/quantum
ciphertext in any oracle model, if it satisfies the following conditions:

  1. 1.

The key generation algorithm makes at most $d$ quantum queries;

  2. 2.

The encryption algorithm makes at most $d$ quantum queries;

  3. 3.

The decryption algorithm makes no queries.

There exists an adversary Eve that could break the public key encryption
scheme with probability $1-O(\epsilon)$ by making $O(d^{2}e/\epsilon^{2})$
number of oracle queries.

###### Proof.

In this case, if Eve generates $O(de/\epsilon^{2})$ copies of message $m_{1}$
and runs Bob $\mathcal{B}(m_{1})$ according to the first message $m_{1}$, we
can see that the permutation invariant condition still holds. Consider the
stage before Bob sends the second message, similar to Theorem 5.2, we have
that

$\displaystyle I(\mathsf{A}:\mathsf{B}\mid\mathsf{E})\leq\frac{1}{2C}\leq
O(\epsilon^{2}).$

Thus by applying the channel in Theorem 3.11 to $\mathsf{E}$, we can obtain a
state $\rho_{A^{\prime}B}$ that is $O(\epsilon)$ close to the state
$\rho_{AB}$. Now Eve receives the message register from Bob and runs the
decryption algorithm on $\mathsf{A}^{\prime}$, by the completeness of the
protocol we can obtain that

$\Pr[k_{B}=k_{E}]\geq\Pr[k_{A}=k_{B}]-O(\epsilon)\geq 1-O(\epsilon)-{\sf
negl}(\lambda).$

∎

Note that our impossibility result can be extended to the Classical
Communication One Quantum Message Key Agreement (CC1QM-KA) model from
[BGVV23]. In their security definition, the quantum message channel is
unauthenticated, thus it can be modified by the adversary $\mathcal{E}$. As
long as the completeness of the original key agreement protocol is $1-{\sf
negl}(\lambda)$, we can apply the gentle measurement lemma to ensure that
$\Pr[k_{A}=k_{B}=k_{E}]\geq 1-O(\sqrt{\epsilon})$.

##  6 Public Key Encryption with a Classical Key Generation

In this section, we devote ourselves to proving black-box separation results
for public key encryption schemes with a classical key generation process and
one-way functions.

Recall the definitions of QPKE schemes from Section 3.5. We will focus on the
specific public encryption schemes defined as follows:

######  Definition 6.1.

A public key encryption scheme with a classical key generation process,
relative to a random oracle $H\leftarrow\mathcal{H}_{\lambda}$ consists of the
following three bounded-query quantum algorithms:

  * •

${\sf Gen}^{H}(1^{\lambda})\to({\sf pk},{\sf sk})$: The key generation
algorithm that generates a pair of public key ${\sf pk}$ and secret key ${\sf
sk}$.

  * •

${\sf Enc}^{\ket{H}}({\sf pk},m)\to{\sf ct}$: the encryption algorithm that
takes a public key ${\sf pk}$, the plaintext $m$, and the randomness $r$,
produces the ciphertext ${\sf ct}$.

  * •

${\sf Dec}^{\ket{H}}({\sf sk},{\sf ct})\to m^{\prime}$: the decryption
algorithm that takes secret key ${\sf sk}$ and ciphertext ${\sf ct}$ and
outputs the plaintext $m^{\prime}$.

Here we use $H$ to denote the algorithm has classical access to the oracle,
and $\ket{H}$ to denote quantum access to the oracle.

The algorithms should satisfy the following requirements:

Perfect Completeness

$\Pr\left[{\sf Dec}^{\ket{H}}\left({\sf sk},{\sf Enc}^{\ket{H}}({\sf
pk},m)\right)=m\colon{\sf Gen}^{H}(1^{\lambda})\to({\sf pk},{\sf
sk})\right]=1$.

IND-CPA Security

For any QPT adversary $\mathcal{E}^{\ket{H}}$, for every two plaintexts
$m_{0}\neq m_{1}$ chosen by $\mathcal{E}^{\ket{H}}({\sf pk})$ we have

$\displaystyle\Pr\left[\mathcal{E}^{\ket{H}}\left({\sf pk},{\sf
Enc}^{\ket{H}}({\sf pk},m_{b})\right)=b\right]\leq\frac{1}{2}+{\sf
negl}(\lambda).$

To prove a black box separation, we would view the public key encryption
scheme as a two-round key agreement protocol as described before, and utilize
the previous tools from information theory. From the perspective of a key
agreement protocol, it could be viewed as a two-stage Alice: before sending
the first message, Alice would first make classical queries to the oracle $H$;
And after receiving the message from Bob, it would make quantum queries to the
oracle, and output the key they agree on. We denote the first stage as
$\mathcal{A}_{1}$ and the second stage as $\mathcal{A}_{2}$.

We would use the following lemma from [BBBV97].

######  Lemma 6.2.

Consider a quantum algorithm $\mathcal{B}$ that makes $d$ queries to an oracle
$H$. Denote the quantum state immediately after $t$ queries to the oracle as

$\displaystyle\ket{\psi_{t}}=\sum_{x,w}\alpha_{x,w,t}\ket{x,w},$

where $w$ is the content of the workspace register. Denote the query weight
$q_{x}$ of input $x$ as

$\displaystyle q_{x}=\sum_{t=1}^{d}\sum_{w}|\alpha_{x,w,t}|^{2}.$

For any oracle $\tilde{H}$, denote $\ket{\phi_{d}}$ as the final state before
measurement obtained by running $\mathcal{B}$ with oracle $\tilde{H}$, we have
that

$\displaystyle\lVert\ket{\psi_{d}}-\ket{\phi_{d}}\rVert\leq
2\sqrt{d}\sqrt{\sum_{x\colon\tilde{H}(x)\neq H(x)}q_{x}}.$

To define Eve’s algorithm, we would first introduce the following algorithm
$\mathcal{B}^{\prime}$ as the modified algorithm of $\mathcal{B}$:

  1. 1.

On receiving message $m_{1}$, first run $\mathcal{B}(m_{1})$, and stop before
the final output measurement.

  2. 2.

Repeat the following process $3d^{2}(\log d+\log(1/\epsilon))$ times: randomly
choose $i\leftarrow[d]$, simulate $\mathcal{B}(m_{1})$ to its $i$th query to
the oracle, and measure the input register, obtaining output $x\in[2^{n}]$,
and classically query the oracle to obtain $H(x)$.

  3. 3.

Measure the output register of the first $\mathcal{B}(m_{1})$, and obtain key
$k_{B}$ and the second message $m_{2}$.

The first part of the the adversary algorithm $\mathcal{E}$ would be
generating $O(dn/\epsilon^{2})$ copies of $m_{1}$, and repeating the
$\mathcal{B}^{\prime}$ algorithm on each of these copies without performing
step 3. It records all the query input-output pairs
$R_{E}=\\{(x_{E},H(x_{E}))\\}$ obtained from step 2 of $\mathcal{B}$.

We denote the heavy weight set $W_{B}$ of $\mathcal{B}^{\ket{H}}(m_{1})$ as
$W_{B}=\\{x\colon q_{x}\geq\epsilon^{2}/d^{2}\\}$. We have the following
lemma:

######  Lemma 6.3.

Let $In_{E}$ be the set of input that is recorded in $R_{E}$, we have that

$\displaystyle\Pr[W_{B}\not\subseteq In_{E}]\leq\epsilon.$

###### Proof.

For each $x\in W_{B}$, it would be measured w.p. at least $\epsilon^{2}/d^{3}$
at each step 2 $\mathcal{B}^{\prime}$ performed by $\mathcal{E}$. Thus the
probability it is not measured is bounded by

$\displaystyle\Pr[x\notin
In_{E}]\leq\left(1-\frac{\epsilon^{2}}{d^{3}}\right)^{3d^{3}n(\log
d+\log(1/\epsilon))/\epsilon^{2}}\leq\epsilon^{3}/d^{3}.$

Since $\sum_{x}q_{x}=d$, we have $|W_{B}|\leq d^{3}/\epsilon^{2}$, thus by a
union bound we obtain the desired result. ∎

Since step 2 of $\mathcal{B}^{\prime}$ would not affect the output of the
algorithm, we can equivalently think as the key agreement protocol consists of
$\mathcal{A}$ and $\mathcal{B}^{\prime}$. Note that in this case,
$\mathcal{E}$ holds $O(dn/\epsilon^{2})$ copies of registers that suffice the
permutation invariant condition. Consider the joint state $\rho_{ABE}$ at the
stage before $\mathcal{B}^{\prime}$ performing step 3, by Lemma 4.2 we have
that $I(\mathsf{A}:\mathsf{B}\mid\mathsf{E})\leq\epsilon^{2}$. Moreover,
applying the channel
$\mathcal{T}\colon\mathsf{E}\to\mathsf{E}\otimes\mathsf{A}^{\prime}$ from
Theorem 3.11, we can generate a state $\rho_{A^{\prime}BE}$ such that
$TD(\rho_{ABE},\rho_{A^{\prime}BE})\leq\epsilon$.

For the rest of this section, we are only interested in the following
registers of $\mathsf{A},\mathsf{B},\mathsf{E}$:

  * •

The classical internal state $st_{A}$ and oracle query input-output pairs
$R_{A}=\\{(x_{A},H(x_{A}))\\}$. This assumption can be made since the secret
key ${\sf sk}$ is classical.

  * •

The output register consists of the key $k_{B}$ and the message $m_{2}$ of
$\mathcal{B}$.

  * •

The input-output pairs recorded by Eve $R_{E}=\\{(x_{E},H(x_{E}))\\}$.

Without specification, we reuse $\mathsf{A},\mathsf{B},\mathsf{E}$ for the
beyond registers respectively. We denote the measurement in computational
basis on these registers as $\Pi_{ABE}$, and the measurement outcome
distribution as $D_{ABE}$. Similarly we can define $\Pi_{A^{\prime}BE}$ and
$D_{A^{\prime}BE}$.

By perfect completeness, any sample ${\sf
View}_{ABE}=(st_{A},R_{A},k_{B},m_{2},R_{E})\leftarrow D_{ABE}$ would be a
valid execution. That is to say, there is some oracle $H^{\prime}$ that is
consistent with $R_{A}$ and $R_{E}$, and running $\mathcal{A}_{2}$ on
$H^{\prime}$ would always output $k_{A}=k_{B}$. It also implies for any $x\in
In_{A}\cap In_{E}$, the corresponding input-output pair should also be
consistent for $R_{A}$ and $R_{E}$.

Since $TD(\rho_{ABE},\rho_{A^{\prime}BE})\leq\epsilon$, we have that
$TV(D_{ABE},D_{A^{\prime}BE})\leq\epsilon$ by the operational meaning of trace
distance. By Lemma 4.6, we have that

$\displaystyle\Pr_{{\sf View}_{A^{\prime}BE}\leftarrow D_{A^{\prime}BE}}[{\sf
View}_{A^{\prime}BE}\notin\mathsf{SUPP}(D_{ABE})]\leq 2\epsilon.$

Now we show that if we reprogram the oracle $H$ to make it consistent with
$R_{A^{\prime}}=\\{(x_{A},H^{\prime}(x_{A}))\\}$ from the new sample ${\sf
View}_{A^{\prime}BE}$, with high probability the algorithm $\mathcal{B}$ is
consistent with $\tilde{H}$ and output $(k_{B},m_{2})$. We define the
reprogrammed oracle $\tilde{H}$ as follows:

$\displaystyle\tilde{H}(x)=\begin{cases}H^{\prime}(x),&x\in In_{A};\\\
H(x),&\text{else.}\end{cases}.$

We have the following theorem,

######  Theorem 6.4.

For the reprogrammed oracle $\tilde{H}$ defined as beyond, for any quantum
algorithm $\mathcal{B}$ making $d$ queries to the oracle

$\displaystyle\Pr_{(k_{B},m_{2})\leftarrow\mathcal{B}^{\ket{H}}(m_{1})}\left[(k_{B},m_{2})\in\mathsf{SUPP}\left(\mathcal{B}^{\ket{\tilde{H}}}(m_{1})\right)\middle|{\sf
View}_{A^{\prime}BE}\in\mathsf{SUPP}(D_{ABE})\right]\geq 1-O(\epsilon),$

here we slightly abuse the notation $\mathcal{B}^{\ket{H}}(m_{1})$ for the
classical output distribution of $\mathcal{B}$.

###### Proof.

Combining Theorem 3.11 and Lemma 6.3 we have that

$\Pr[{\sf View}_{A^{\prime}BE}\in\mathsf{SUPP}(D_{ABE})\land W_{B}\subseteq
In_{E}]\geq 1-\Pr[{\sf
View}_{A^{\prime}BE}\notin\mathsf{SUPP}(D_{ABE})]-\Pr[W_{B}\not\subseteq
In_{E}]\geq 1-O(\epsilon).$

Given ${\sf View}_{A^{\prime}BE}\in\mathsf{SUPP}(D_{ABE})$ and
$W_{\mathsf{B}}\subseteq In_{E}$, we apply Lemma 6.2 and obtain that

$\displaystyle
TV\left(\mathcal{B}^{\ket{\tilde{H}}}(m_{1}),\mathcal{B}^{\ket{H}}(m_{1})\right)$
$\displaystyle\leq 4||\ket{\psi_{d}}-\ket{\phi_{d}}||$ $\displaystyle\leq
8\sqrt{d}\sqrt{\sum_{x\colon\tilde{H}(x)\neq H(x)}q_{x}}$ $\displaystyle\leq
8\sqrt{d}\sqrt{d\cdot\frac{\epsilon^{2}}{d^{2}}}=O\left(\epsilon\right),$

where the first inequality comes from [BBBV97, Theorem 3.1], the second
inequality is Lemma 6.2, and the third inequality is by that
$|\\{x\colon\tilde{H}(x)\neq H(x)\\}|\leq|In_{A}|\leq d$. By Lemma 4.6, we
have that

$\displaystyle\Pr_{(k_{B},m_{2})\leftarrow\mathcal{B}^{\ket{H}}(m_{1})}\left[(k_{B},m_{2})\in\mathsf{SUPP}\left(\mathcal{B}^{\ket{\tilde{H}}}(m_{1})\right)\middle|{\sf
View}_{A^{\prime}BE}\in\mathsf{SUPP}(D_{ABE})\land W_{B}\subseteq
In_{E}\right]\geq 1-O\left(\epsilon\right).$

The final statement can be obtained by a conditional probability formula. ∎

Now we will prove the first main theorem of the section.

######  Theorem 6.5.

For any public key encryption scheme in the random oracle model, if it
satisfies the following conditions:

  1. 1.

Perfect completeness;

  2. 2.

The key generation algorithm makes at most $d$ classical queries to the
oracle;

  3. 3.

The encryption algorithm makes at most $d$ quantum queries to the oracle;

  4. 4.

The decryption algorithm makes at most $D$ quantum queries to the oracle.

There exists an adversary Eve that could break the public key encryption
scheme w.p. $1-O(\epsilon)$ by making $O(d^{4}n(\log
d+\log(1/\epsilon))/\epsilon^{2}+D)$ queries to the oracle.

###### Proof.

We have already described most of the adversary algorithm $\mathcal{E}$ as we
prove the beyond lemmata and theorems. We summarize the algorithm
$\mathcal{E}$ as follows: it first generates $O(dn/\epsilon^{2})$ copies of
$m_{1}$, and repeats the $\mathcal{B}^{\prime}$ algorithm on each of these
copies without performing step 3. It applies the channel $\mathcal{T}$ to the
register $\mathsf{E}$(including the full workspace) and generates a state
$\rho_{A^{\prime}BE}$. Applying $\Pi_{A^{\prime}BE}$ to $\rho_{A^{\prime}BE}$
to obtain a sample ${\sf
View}_{A^{\prime}BE}=(st_{A^{\prime}},R_{A^{\prime}},k_{B},m_{2},R_{E})$. It
runs the algorithm $\mathcal{A}_{2}(m_{2})$ on register $\mathsf{A}^{\prime}$
with the reprogrammed oracle $\tilde{H}$, and obtaining the final output
$k_{E}=k_{A^{\prime}}$.

Now we argue the correctness of the algorithm. Assume that before performing
$\Pi_{A^{\prime}BE}$, we first perform $\Pi_{ABE}$ on the state $\rho_{ABE}$.
This assumption can be made since $\Pi_{A^{\prime}BE}$ and $\Pi_{ABE}$
commute. By perfect completeness of the protocol, we can see that the result
${\sf View}_{ABE}$ is a valid internal state, compatible with oracle $H$. Now
we discuss the measurement result of $\Pi_{A^{\prime}BE}$. Note that in this
case, the $(k_{B},m_{2},R_{E})$ in ${\sf View}_{A^{\prime}BE}$ is the same as
in ${\sf View}_{ABE}$.

Consider the case that ${\sf View}_{A^{\prime}BE}\in\mathsf{SUPP}(D_{ABE})$,
i.e. ${\sf View}_{A^{\prime}BE}$ is a valid execution for some oracle
$H^{\prime}$, we now argue that actually ${\sf View}_{A^{\prime}BE}$ is also a
valid execution for oracle $\tilde{H}$ with high probability. From the
perspective of $\mathsf{A}^{\prime}$, the result
$st_{A^{\prime}},R_{A^{\prime}}$ is compatible with $\tilde{H}$, and will
output message ${m_{1}}$. From the perspective of
$\mathcal{B}^{\ket{H}}(m_{1})$, before the measurement on the output register,
it can be viewed as a distribution of key-message pairs $\\{(k_{B},m_{2})\\}$.
Now we imagine we are running the algorithm
$\mathcal{B}^{\ket{\tilde{H}}}(m_{1})$ instead. By Theorem 6.4, we can see
that with probability $1-O(\epsilon)$,
$(k_{B},m_{2})\leftarrow\mathcal{B}^{\ket{H}}(m_{1})$ would also be in the
support of $\mathcal{B}^{\ket{\tilde{H}}}(m_{1})$.

Together they imply that ${\sf View}_{A^{\prime}BE}$ would be a valid
execution for $\mathcal{A},\mathcal{B}$ under oracle $\tilde{H}$ when
$\mathcal{B}$ outputs key $k_{B}$. Thus if we run $\mathcal{A}_{2}(m_{2})$
with the reprogrammed oracle $\tilde{H}$, by perfect completeness, it would
also output $k_{A}^{\prime}=k_{B}$.

For each run of $\mathcal{B}^{\prime}$, it would simulate $\mathcal{B}$ for
$O(d^{2}(\log(d)+\log(1/\epsilon)))$ times, and each time it makes at most $d$
queries. For the adversary algorithm $\mathcal{E}$, it would run
$\mathcal{B}^{\prime}$ for $O(dn/\epsilon^{2})$ times, giving us the query
complexity beyond. ∎

Reviewing our proof beyond, we notice that $m_{1}$ may not necessarily be a
classical message. As long as $\ket{m_{1}}$ is a pure state, and we can obtain
any polynomial copies of $\ket{m_{1}}$, the analysis in our proof exactly
applies. Recall the IND-CPA Security from Definition 3.16, if the public key
is pure, the adversary algorithm $\mathcal{E}$ can obtain polynomial many
copies of $\ket{{\sf pk}}$. For any message $m_{0}\neq m_{1}$, we can
construct a key agreement for one bit by setting the second message as the
ciphertext ${\sf ct}_{0}/{\sf ct}_{1}$ respectively. Thus by running our
$\mathcal{E}$ beyond, we can break the IND-CPA security game with advantage
$1-O(\epsilon)$.

Now we show that our attack would still apply when the ciphertext is also
quantum. The proof would be similar to the proof beyond. By running the same
algorithm $\mathcal{E}$ we obtained the state $\rho_{A^{\prime}BE}$, we would
perform the measurement $\Pi_{A^{\prime}BE}$, but for the $B$ part we do not
include the ciphertext $\rho_{m_{2}}$ register. We can define $\tilde{H}$ as
beyond, and prove the following statements given ${\sf View}_{A^{\prime}BE}$
is a valid execution:

  1. 1.

From the perspective of $\mathsf{A}^{\prime}$, the result
$st_{A^{\prime}},R_{A^{\prime}}$ is compatible with $\tilde{H}$, and will
output message $\ket{m_{1}}$. By definition, $R_{A^{\prime}}$ is compatible
with $\tilde{H}$. Since $\mathsf{B}$ is not affected by channel $\mathcal{T}$,
by uncomputing $\mathcal{B}$ on state $\rho_{A^{\prime}B}$, we can see that
$\mathcal{B}$ would also receive $\ket{m_{1}}$ from $\mathsf{A}^{\prime}$.
From the observation, we can see that after performing the uncomputation,
$TD(\rho_{A},\rho_{A^{\prime}})=TD(\rho_{A^{\prime}B},\rho_{AB})\leq\epsilon$,
thus $st_{A^{\prime}},R_{A^{\prime}}$ is compatible with output $\ket{m_{1}}$
under oracle $\tilde{H}$ w.p. $1-\epsilon$.

  2. 2.

From the perspective of $\mathcal{B}^{\ket{H}}(\ket{m_{1}})$, the state before
the measurement $\Pi_{A^{\prime}BE}$ can be written as
$\rho_{B}=\sum_{k_{B}}p_{k_{B}}\ket{k_{B}}\bra{k_{B}}\otimes\rho_{k_{B}}$.
Similarly, we denote the state of $\mathcal{B}^{\ket{\tilde{H}}}(\ket{m_{1}})$
as
$\sigma_{B}=\sum_{k_{B}}p^{\prime}_{k_{B}}\ket{k_{B}}\bra{k_{B}}\otimes\sigma_{k_{B}}$.
In the proof of Theorem 6.4, when we apply Lemma 6.2, we can obtain that
$TD(\rho_{B},\sigma_{B})\leq O(\epsilon)$. Now we consider the classical part
of $\rho_{B}$ and $\sigma_{B}$. Since partial trace will not increase the
trace distance, we have for distribution $D_{B}=\\{p_{k_{B}}\\}$ and
$D_{B}^{\prime}=\\{p^{\prime}_{k_{B}}\\}$,
$TV(D_{B},D_{B}^{\prime})\leq\epsilon$. Thus for state
$\rho^{\prime}_{AB}=\sum_{k_{B}}p^{\prime}_{k_{B}}\ket{k_{B}}\bra{k_{B}}\otimes\rho_{k_{B}}$,
$TD(\rho_{B},\rho^{\prime}_{B})\leq\epsilon$, and by triangular inequality,
$TD(\rho^{\prime}_{B},\sigma_{B})\leq 2\epsilon$. Since
$TD(\rho^{\prime}_{B},\sigma_{B})=\mathbb{E}[TD(\rho_{k_{B}},\sigma_{k_{B}})]$,
using Markov inequality, we can see that

$\displaystyle\Pr_{({\sf sk},k_{B})\leftarrow
D_{A^{\prime}B}}[TD(\rho_{k_{B}},\sigma_{k_{B}})\leq C\epsilon]\geq
1-\frac{2}{C}.$

If we take $C={1}/{\sqrt{\epsilon}}$, we can obtain that w.p.
$1-O(\sqrt{\epsilon})$, $TD(\rho_{k_{B}},\sigma_{k_{B}})\leq\sqrt{\epsilon}$.

We can see that $\ket{m_{1}},\sigma_{k_{B}}$ would be a valid transcript for
$\mathcal{A},\mathcal{B}$ under oracle $\tilde{H}$. Thus when $\rho_{k_{B}}$
and $\sigma_{k_{B}}$ is $O(\sqrt{\epsilon})$ close,
$\mathcal{A}^{\tilde{H}}({\sf sk},\rho_{k_{B}})$ will output
$k_{A^{\prime}}=k_{B}$ with probability $1-O(\sqrt{\epsilon})$. Thus we obtain
the following theorem:

For the clonable public key case
$\rho_{m_{1}}=\sum_{i}p_{i}\ket{\psi_{i}}\bra{\psi_{i}}$, we observe that the
output of $\mathcal{B}(\rho_{m_{1}})$ would be the convex combination of
$\mathcal{B}(\ket{\psi_{i}})$. Thus by the perfect completeness property of
the protocol, each $\ket{\psi_{i}}$ would also be a valid public key. Further
observing that the clonable case is a convex combination of pure public keys,
we have the following theorem:

######  Theorem 6.6.

For any QPKE scheme with quantum public key in the random oracle model, if it
satisfies the following conditions:

  1. 1.

Perfect completeness;

  2. 2.

The public key $\rho_{{\sf pk}}$ is pure or clonable.

  3. 3.

The key generation algorithm makes at most $d$ classical queries to the
oracle;

  4. 4.

The encryption algorithm makes at most $d$ quantum queries to the oracle;

  5. 5.

The decryption algorithm makes at most $D$ quantum queries to the oracle.

There exists an adversary Eve that could break the public key encryption
scheme w.p. $1-O(\sqrt{\epsilon})$ by making $O(d^{4}n(\log
d+\log(1/\epsilon))/\epsilon^{2}+D)$ queries to the oracle.

This theorem gives a tight characterization of multiple existing QPKE schemes.
In [BGH+23] and [Col23], they both provided a QPKE scheme with a pure quantum
public key, but their public key generation algorithms need to make quantum
queries. Our result shows that the quantum query is necessary for their key
agreement scheme. In [KMNY23, MW23], they provided another QPKE scheme where
the quantum public key is mixed, but the key generation algorithm can only
make classical queries. Our result shows that their key must be mixed and
unclonable in a strong sense.

## References

  * [AA09] Scott Aaronson and Andris Ambainis  “The need for structure in quantum speedups”  In _arXiv preprint arXiv:0911.0996_ , 2009
  * [Aar09] Scott Aaronson  “Quantum copy-protection and quantum money”  In _2009 24th Annual IEEE Conference on Computational Complexity_ , 2009, pp. 229–242  IEEE
  * [ACC+22] Per Austrin et al.  “On the impossibility of key agreements from quantum random oracles”  In _Annual International Cryptology Conference_ , 2022, pp. 165–194  Springer
  * [AL70] Huzihiro Araki and Elliott H Lieb  “Entropy inequalities”  In _Communications in Mathematical Physics_ 18.2 Springer, 1970, pp. 160–170
  * [ALL+21] Scott Aaronson et al.  “New approaches for quantum copy-protection”  In _Annual International Cryptology Conference_ , 2021, pp. 526–555  Springer
  * [AQY22] Prabhanjan Ananth, Luowen Qian and Henry Yuen  “Cryptography from pseudorandom quantum states”  In _Annual International Cryptology Conference_ , 2022, pp. 208–236  Springer
  * [BB14] Charles H. Bennett and Gilles Brassard  “Quantum cryptography: Public key distribution and coin tossing”  In _Theoretical Computer Science_ 560 Elsevier BV, 2014, pp. 7–11  DOI: 10.1016/j.tcs.2014.05.025
  * [BBBV97] Charles H. Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani  “Strengths and Weaknesses of Quantum Computing”  In _SIAM J. Comput._ 26.5 Philadelphia, PA, USA: Society for IndustrialApplied Mathematics, 1997, pp. 1510–1523
  * [BCKM21] James Bartusek, Andrea Coladangelo, Dakshita Khurana and Fermi Ma  “On the round complexity of secure quantum computation”  In _Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part I 41_ , 2021, pp. 406–435  Springer
  * [BGH+23] Khashayar Barooti et al.  “Public-Key Encryption with Quantum Keys”, 2023  arXiv:2306.07698 [quant-ph]
  * [BGVV23] Samuel Bouaziz–Ermann, Alex B Grilo, Damien Vergnaud and Quoc-Huy Vu  “Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions”  In _arXiv preprint arXiv:2311.03512_ , 2023
  * [BKSY11] Zvika Brakerski, Jonathan Katz, Gil Segev and Arkady Yerukhimovich  “Limits on the power of zero-knowledge proofs in cryptographic constructions”  In _Theory of Cryptography: 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011. Proceedings 8_ , 2011, pp. 559–578  Springer
  * [BM09] Boaz Barak and Mohammad Mahmoody-Ghidary  “Merkle puzzles are optimal—an O (n 2)-query attack on any key exchange from a random oracle”  In _Annual International Cryptology Conference_ , 2009, pp. 374–390  Springer
  * [Col23] Andrea Coladangelo  “Quantum trapdoor functions from classical one-way functions”  In _arXiv preprint arXiv:2302.12821_ , 2023
  * [FR15] Omar Fawzi and Renato Renner  “Quantum conditional mutual information and approximate Markov chains”  In _Communications in Mathematical Physics_ 340.2 Springer, 2015, pp. 575–611
  * [GLSV21] Alex B Grilo, Huijia Lin, Fang Song and Vinod Vaikuntanathan  “Oblivious transfer is in MiniQCrypt”  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , 2021, pp. 531–561  Springer
  * [HJPW04] Patrick Hayden, Richard Jozsa, Denes Petz and Andreas Winter  “Structure of states which satisfy strong subadditivity of quantum entropy with equality”  In _Communications in mathematical physics_ 246 Springer, 2004, pp. 359–374
  * [Imp95] Russell Impagliazzo  “A personal view of average-case complexity”  In _Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference_ , 1995, pp. 134–147  IEEE
  * [IR89] Russell Impagliazzo and Steven Rudich  “Limits on the provable consequences of one-way permutations”  In _Proceedings of the twenty-first annual ACM symposium on Theory of computing_ , 1989, pp. 44–61
  * [KMNY23] Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki and Takashi Yamakawa  “Quantum public-key encryption with tamper-resilient public keys from one-way functions”  In _arXiv preprint arXiv:2304.01800_ , 2023
  * [Maz23] Noam Mazor  “Key-agreement with perfect completeness from random oracles”  In _Cryptology ePrint Archive_ , 2023
  * [Mül92] JW Müller  “Parity moments for a Poisson variable”  In _BIPM WPN-235_ , 1992
  * [MW23] Giulio Malavolta and Michael Walter  “Robust Quantum Public-Key Encryption with Applications to Quantum Key Distribution” https://eprint.iacr.org/2023/500, Cryptology ePrint Archive, Paper 2023/500, 2023  URL: https://eprint.iacr.org/2023/500
  * [MY22] Tomoyuki Morimae and Takashi Yamakawa  “One-wayness in quantum cryptography”  In _arXiv preprint arXiv:2210.03394_ , 2022
  * [MY22a] Tomoyuki Morimae and Takashi Yamakawa  “Quantum commitments and signatures without one-way functions”  In _Annual International Cryptology Conference_ , 2022, pp. 269–295  Springer
  * [NC10] Michael A. Nielsen and Isaac L. Chuang  “Quantum Computation and Quantum Information: 10th Anniversary Edition”  Cambridge University Press, 2010  DOI: 10.1017/CBO9780511976667
  * [Sho99] Peter W Shor  “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”  In _SIAM review_ 41.2 SIAM, 1999, pp. 303–332
  * [Wie83] Stephen Wiesner  “Conjugate coding”  In _ACM Sigact News_ 15.1 ACM New York, NY, USA, 1983, pp. 78–88
  * [Wil11] Mark M Wilde  “From classical to quantum Shannon theory”  In _arXiv preprint arXiv:1106.1445_ , 2011
  * [YZ22] Takashi Yamakawa and Mark Zhandry  “Verifiable Quantum Advantage without Structure”  In _arXiv preprint arXiv:2204.02063_ , 2022
  * [Zha19] Mark Zhandry  “How to record quantum queries, and applications to quantum indifferentiability”  In _Annual International Cryptology Conference_ , 2019, pp. 239–268  Springer

##  Appendix A Additional Preliminaries

###  A.1 Compressed Oracle

The analysis of Appendix B relies on the compressed oracle techinque of
Zhandry [Zha19]. Here, We briefly introduce the ideas we needed. Zhandry shows
that the standard quantum random oracle is perfectly indistinguishable from
the purified random oracle by any unbound quantum adversary. For a standard
random oracle $H:[2^{n}]\to\\{0,1\\}$, the initial state of the purified
random oracle is $\sum_{H\in\\{0,1\\}^{2^{n}}}\ket{H}$. The oracle access to
$\ket{H}$ is defined by a unitary transformation $U_{H}$ where

$U_{H}\ket{x,y}\ket{H}:=(-1)^{y\cdot H(x)}\ket{x,y}\ket{H}.$

Given a vector $S\in\\{0,1\\}^{2^{n}}$, define
$\ket{\hat{D}}:=\sum_{H\in\\{0,1\\}^{2^{n}}}(-1)^{\langle H,D\rangle}\ket{H}$
where $\langle\cdot,\cdot\rangle$ denotes inner product. We call
$\left\\{\ket{\hat{D}}\right\\}$ the Fourier basis of the oracle space. Then
we have following lemma.

######  Lemma A.1.

Let $\mathcal{A}$ be a quantum algorithm that makes $d$ queries to the random
oracle, the final state of $\mathcal{A}$ can be written as $\sum_{|D|\leq
d}\alpha_{D}\ket{\psi_{D}}\ket{\hat{D}}$ where $|D|$ denotes the number of
non-zero entries in $D$.

###### Proof.

Prove by induction on $d$. When $d=0$, the initial joint state of working
register $\mathsf{A}$, the query register $\mathsf{Q}$ and oracle register
$\mathsf{H}$ can be written as
$\ket{\psi}_{\mathsf{A}\mathsf{Q}}\sum_{H\in\\{0,1\\}^{2^{n}}}\ket{H}_{\mathsf{H}}=\ket{\psi}_{\mathsf{A}\mathsf{Q}}\ket{\hat{\textbf{0}}}_{\mathsf{H}}$.
Supposing the statement holds for $d$, then the current state can be written
as $\sum_{u,x,y,|D|\leq
d}\alpha_{u,x,y,D}\ket{u}_{\mathsf{A}}\ket{x,y}_{\mathsf{Q}}\ket{\hat{D}}_{\mathsf{H}}$.
After making one more query, the state becomes

$\displaystyle\sum_{u,x,y,|D|\leq
d}\alpha_{u,x,y,D}\ket{u}_{\mathsf{A}}U_{H}\ket{x,y}_{\mathsf{Q}}\ket{\hat{D}}_{\mathsf{H}}$
$\displaystyle=\sum_{u,x,y,|D|\leq
d}\alpha_{u,x,y,D}\ket{u}_{\mathsf{A}}U_{H}\ket{x,y}_{\mathsf{Q}}\sum_{H}(-1)^{\langle
H,D\rangle}\ket{H}_{\mathsf{H}}$ $\displaystyle=\sum_{u,x,y,|D|\leq
d}\alpha_{u,x,y,D}\ket{u}_{\mathsf{A}}\ket{x,y}_{\mathsf{Q}}\sum_{H}(-1)^{\langle
H,D\rangle+y\cdot H(x)}\ket{H}_{\mathsf{H}}$
$\displaystyle=\sum_{u,x,y,|D|\leq
d}\alpha_{u,x,y,D}\ket{u}_{\mathsf{A}}\ket{x,y}_{\mathsf{Q}}\sum_{H}(-1)^{\langle
H,D\oplus(x,y)\rangle}\ket{H}_{\mathsf{H}}$ $\displaystyle=\sum_{u,x,y,|D|\leq
d}\alpha_{u,x,y,D}\ket{u}_{\mathsf{A}}U_{H}\ket{x,y}_{\mathsf{Q}}\ket{\widehat{D\oplus(x,y)}}_{\mathsf{H}}$

where $|D\oplus(x,y)|\leq d+1$. ∎

##  Appendix B Non-Adaptive Quantum Key Agreement

Non-adaptive key agreement protocol is a special case of non-interactive
protocol in Section 5. It restricts Alice and Bob by only allowing them to
make non-adaptive queries, i.e., queries can depend on neither any previous
queries nor classical communication. The famous Merkle Puzzles and PRS-based
protocols are both examples of this non-adaptive case. Formally,

######  Definition B.1 (Non-adaptive Quantum Key Agreement).

A QKA protocol between Alice and Bob with access to a random oracle $H$ is
called non-adaptive if (i) the protocol is non-interactive (see Definition
5.1), (ii) Alice’s (Bob’s) query algorithm consists of the following steps:

  1. 1.

Prepare a quantum state
$\sigma_{1}\otimes\sigma_{2}\otimes\cdots\otimes\sigma_{d}$ where $\sigma_{i}$
is the state of the input and output registers of the $i$-th query.

  2. 2.

Make the $d$ queries to $H$ in parallel.

We show that for this special case, the number of queries Eve needed can be
improved from $O(d^{2}e)$ to $\widetilde{O}(d^{2})$, which is independent of
the input size of the random oracle. We remark that unlike Theorem 5.2, this
result only works for random oracle.

######  Theorem B.2.

Given a non-adaptive QKA protocol between Alice and Bob with access to a
random oracle $H$, let $k_{A},k_{B}$ be key of Alice and Bob respectively. If
$\Pr[k_{A}=k_{B}]\geq\delta$, then there exists an eavesdropper Eve who
outputs her key $k_{E}$ with
$O\left(\frac{d^{2}}{\epsilon^{2}}\log^{2}\frac{d}{\epsilon}\right)$ queries
such that $\Pr[k_{E}=k_{A}]\geq\delta-\epsilon$.

The rest of this section is a proof of Theorem B.2. Similar to non-interactive
case, our goal is to show that Eve can somehow repeat Alice’s query algorithm
to make CMI sufficiently small so that she can recover the key.

###  B.1 Recasting It as a Classical Random Walk Problem

Since queries are non-adaptive, we assume Alice and Bob use the same query
algorithm denoted by $\mathcal{Q}$ without loss of generality. Let
$H:[2^{n}]\rightarrow\\{0,1\\}$ be the random oracle. By Lemma A.1, the state
after applying $\mathcal{Q}$ once can be written as

$\sum_{D\in\\{0,1\\}^{2^{n}}:|D|\leq d}\alpha_{D}\ket{\psi_{D}}\ket{\hat{D}}$

where $\ket{\psi_{D}}$ are states in the working register and $\ket{\hat{D}}$
are the Fourier basis states in the oracle register (see Section A.1). The
following lemma describes properties of the states $\ket{\psi_{D}}$, which
follows directly from Lemma A.1.

######  Lemma B.3.

  1. (a)

If the query is non-adaptive, then $\ket{\psi_{D}}$ and
$\ket{\psi_{D^{\prime}}}$ are orthogonal if $D\neq D^{\prime}$.

  2. (b)

If we repeat $\mathcal{Q}$ for $t$ times, then the joint state of working
register and oracle register is

$\sum_{D_{1},D_{2},\ldots,D_{t}}\alpha_{D_{1}}\alpha_{D_{2}}\cdots\alpha_{D_{t}}\ket{\psi_{D_{1}}}\ket{\psi_{D_{2}}}\cdots\ket{\psi_{D_{t}}}\ket{\widehat{\oplus_{i=1}^{t}D_{i}}}.$

Let $\mathcal{D}$ denote the distribution on $\\{0,1\\}^{2^{n}}$ where
$\Pr_{D\sim\mathcal{D}}[D=x]=|\alpha_{x}|^{2}$. Define random variable
$D^{t}:=D_{1}\oplus\cdots\oplus D_{t}$ where $D_{1},D_{2},\ldots,D_{t}$ are
i.i.d. samples drawn from $\mathcal{D}$. We remark that $D^{t}$ can be viewed
as a random walk with $t$ steps in the hypercube $\\{0,1\\}^{2^{n}}$ where
each step is sampled by distribution $\mathcal{D}$.

We first consider the same attack strategy as in Section 5 where Eve repeats
$\mathcal{Q}$ for sufficient large times. We have the following lemma.

######  Lemma B.4.

Let $\mathsf{A}^{0}$ and $\mathsf{B}^{0}$ denote the state of Alice and Bob
right after applying $\mathcal{Q}$ respectively, $\mathsf{E}^{0}$ be the state
of Eve repeating $\mathcal{Q}$ for $t$ times. Then
$I\left(\mathsf{A}^{0}:\mathsf{B}^{0}\mid\mathsf{E}^{0}\right)=2S\left(D^{t+1}\right)-S\left(D^{t}\right)-S\left(D^{t+2}\right)$.

###### Proof.

By the definition of CMI, we have

$I\left(\mathsf{A}^{0}:\mathsf{B}^{0}\mid\mathsf{E}^{0}\right)=S(\mathsf{A}^{0}\mathsf{E}^{0})+S(\mathsf{B}^{0}\mathsf{E}^{0})-S(\mathsf{E}^{0})-S(\mathsf{A}^{0}\mathsf{B}^{0}\mathsf{E}^{0}).$

Then we compute each term separately. Since Alice and Eve together run
$\mathcal{Q}$ for $t+1$ times, by Lemma B.3(b) the joint state of Alice
$\mathsf{A}$, Eve $\mathsf{E}$ and Oracle $\mathsf{H}$ can be viewed as pure
state

$\ket{\phi}_{\mathsf{A}\mathsf{E}\mathsf{H}}=\sum_{D_{1},D_{2},\ldots,D_{t+1}}\alpha_{D_{1}}\alpha_{D_{2}}\cdots\alpha_{D_{t+1}}\ket{\psi_{D_{1}}}_{\mathsf{A}}\left(\ket{\psi_{D_{2}}}\cdots\ket{\psi_{D_{t+1}}}\right)_{\mathsf{E}}\ket{\widehat{\oplus_{i=1}^{t+1}D_{i}}}_{\mathsf{H}}.$

Let
$\sigma_{\mathsf{A}\mathsf{E}\mathsf{H}}=\ket{\phi}_{\mathsf{A}\mathsf{E}\mathsf{H}}\bra{\phi}_{\mathsf{A}\mathsf{E}\mathsf{H}},\sigma_{\mathsf{A}\mathsf{E}}=\operatorname{Tr}_{\mathsf{H}}(\sigma_{\mathsf{A}\mathsf{E}\mathsf{H}}),\sigma_{\mathsf{H}}=\operatorname{Tr}_{\mathsf{A}\mathsf{E}}(\sigma_{\mathsf{A}\mathsf{E}\mathsf{H}})$.
By Lemma B.3(a), $\ket{\psi_{D}}$ are orthogonal states. Then we have

$\sigma_{\mathsf{H}}=\operatorname{Tr}_{\mathsf{A}\mathsf{E}}(\sigma_{\mathsf{A}\mathsf{E}\mathsf{H}})=\sum_{D_{1},D_{2},\ldots,D_{t+1}}\left|\alpha_{D_{1}}\alpha_{D_{2}}\cdots\alpha_{D_{t+1}}\right|^{2}\ket{\widehat{\oplus_{i=1}^{t+1}D_{i}}}\bra{\widehat{\oplus_{i=1}^{t+1}D_{i}}}.$

Since $\sigma_{\mathsf{A}\mathsf{E}\mathsf{H}}$ is a pure state, we have
$S(\sigma_{\mathsf{A}\mathsf{E}})=S(\sigma_{\mathsf{H}})$. Then
$S(\mathsf{A}^{0}\mathsf{E}^{0})=S(\sigma_{\mathsf{A}\mathsf{E}})=S(\sigma_{\mathsf{H}})=S(D^{t+1})$.
Similarly, we have $S(\mathsf{B}^{0}\mathsf{E}^{0})=S(D^{t+1})$ and
$S(\mathsf{E}^{0})=S(D^{t})$ and
$S(\mathsf{A}^{0}\mathsf{B}^{0}\mathsf{E}^{0})=S(D^{t+2})$. Thus
$I\left(\mathsf{A}^{0}:\mathsf{B}^{0}\mid\mathsf{E}^{0}\right)=2S\left(D^{t+1}\right)-S\left(D^{t}\right)-S\left(D^{t+2}\right)$.
∎

Thus the quantum CMI can be expressed using the entropy of classical variable
$D^{t}$. If we can show that
$2S\left(D^{t+1}\right)-S\left(D^{t}\right)-S\left(D^{t+2}\right)$ is small,
then we can conclude Theorem B.2. Unfortunately, $S\left(D^{t}\right)$ is
difficult to compute, so we slightly modify Eve’s strategy using
Poissonization trick. We first define Poissonized version of Alice:

  1. 1.

For each $i\in[d]$, Alice samples an independent Poisson variable $P_{i}$ with
parameter $\log\mu d$ where $\mu\geq 2$, and then repeats the $i$-th query for
$P_{i}$ times.

  2. 2.

If Alice repeats each query at least once, then she will execute the original
protocol and output the key as before. Otherwise, she aborts and output key
$0$.

Poissonized version of Bob is defined similarly. We remark that Poissonized
Alice and Bob will make expected $O(d\log d)$ queries. W.p.
$\left(1-e^{-\log\mu d}\right)^{2d}\geq 1-1/\mu$, Poissionized Alice and Bob
will repeat each query at least once and then agree on the same key as before.
Thus if Eve can recover Poissonized Alice and Bob’s key, she can also recover
the real key w.p. at least $1-1/\mu$. We have the following theorem.

######  Theorem B.5.

Given a positive integer $t$, let $\widetilde{\mathsf{A}}^{0}$ and
$\widetilde{\mathsf{B}}^{0}$ be the state of Poissonized Alice and Bob right
after querying, $\widetilde{\mathsf{E}}^{0}$ be $t$ copies of
$\widetilde{\mathsf{A}}^{0}$. Then
$I\left(\widetilde{\mathsf{A}}^{0}:\widetilde{\mathsf{B}}^{0}\mid\widetilde{\mathsf{E}}^{0}\right)=O\left(d\log\mu
d/t\right)$.

Before proving the above theorem, we first use it to conclude Theorem B.2.

###### Proof of Theorem B.2.

Let $\widetilde{\mathsf{A}}^{0}$ and $\widetilde{\mathsf{B}}^{0}$ be the state
of Poissonized Alice and Bob right after querying,
$\widetilde{\mathsf{A}}^{f}$ and $\widetilde{\mathsf{B}}^{f}$ be the states of
Poissonized Alice and Bob respectively right after finishing the communication
but before outputting the key, $\Pi$ denote the communications. Let Eve’s
attack strategy be as follows:

  1. 1.

Eve repeats $\widetilde{\mathsf{A}}^{0}$ for $O\left(\frac{d\log\mu
d}{\epsilon^{2}}\right)$ times and obtains state $\widetilde{\mathsf{E}}^{0}$.

  2. 2.

Eve applies the channel in Lemma 2.3 w.r.t. system
$\widetilde{\mathsf{A}}^{f}\widetilde{\mathsf{E}}^{0}\widetilde{\mathsf{B}}^{f}$
and obtains a fake view $\widetilde{\mathsf{A}}^{f^{\prime}}$ of
$\widetilde{\mathsf{A}}^{f}$. Then use $\widetilde{\mathsf{A}}^{f^{\prime}}$
to output key $k_{E}$.

By Theorem B.5, we have
$I\left(\widetilde{\mathsf{A}}^{0}:\widetilde{\mathsf{B}}^{0}\mid\widetilde{\mathsf{E}}^{0}\right)=O(\epsilon^{2})$.
Since classical communication does not increase CMI by Lemma 4.4 and Lemma
4.3, we have
$I\left(\widetilde{\mathsf{A}}^{f}:\widetilde{\mathsf{B}}^{f}\mid\widetilde{\mathsf{E}}^{0},\Pi\right)\leq
I\left(\widetilde{\mathsf{A}}^{0}:\widetilde{\mathsf{B}}^{0}\mid\widetilde{\mathsf{E}}^{0}\right)=O(\epsilon^{2})$.
Then by Theorem 3.11,
$\widetilde{\mathsf{A}}^{f^{\prime}}\widetilde{\mathsf{B}}^{f}$ is
$O(\epsilon)$-close to $\widetilde{\mathsf{A}}^{f}\widetilde{\mathsf{B}}^{f}$.
Let $\widetilde{k}_{A}$ be the key of Poissonized Alice. Then
$\Pr\left[k_{E}=\widetilde{k}_{A}\right]\geq\delta-O(\epsilon)$. Since w.p.
$1-1/\mu$ the Poissonized Alice and Bob will be the same as real Alice and
Bob, we have $\Pr\left[k_{E}=k_{A}\right]\geq\delta-O(\epsilon)-1/\mu$. By
setting $\mu=2/\epsilon$ and adjusting constants, we have
$\Pr\left[k_{E}=k_{A}\right]\geq\delta-\epsilon$ and Eve needs
$O\left(d\log\mu d\cdot\frac{d\log\mu
d}{\epsilon^{2}}\right)=O(\frac{d^{2}}{\epsilon^{2}}\log^{2}\frac{d}{\epsilon})$
queries. ∎

###  B.2 Proof of Theorem B.5

First observe that because non-adaptive queries do not depend on each other,
the distribution $\mathcal{D}$ can be viewed as the sum of $d$ _independent_
distributions $\mathcal{D}[1],\mathcal{D}[2],\ldots,\mathcal{D}[d]$, all of
which are on $\\{0,1\\}^{2^{n}}$ with Hamming weight $1$. That is,
$\mathcal{D}=\mathcal{D}[1]\oplus\mathcal{D}[2]\oplus\cdots\oplus\mathcal{D}[d]$.
Given a positive integer $t$, define a random variable $\widetilde{D}^{t}$ as
follows:

  1. 1.

For each $\ell\in[d]$, first sample $\widetilde{t}_{\ell}$ from
$\mathrm{Pois}(t\log\mu d)$ independently and then draw i.i.d. samples
$D_{1}[\ell],D_{2}[\ell],\ldots,D_{\widetilde{t}_{\ell}}[\ell]$ from
$\mathcal{D}[\ell]$.

  2. 2.

Let
$\widetilde{D}^{t}=\bigoplus_{\ell=1}^{d}\bigoplus_{i=1}^{\widetilde{t}_{\ell}}D_{i}[\ell]$.

Then we have the following lemma, which can be proved similarly as Lemma B.4.

######  Lemma B.6.

Given a positive integer $t$, let $\widetilde{\mathsf{E}}^{0}$ be $t$ copies
of $\widetilde{\mathsf{A}}^{0}$. Then

$I\left(\widetilde{\mathsf{A}}^{0}:\widetilde{\mathsf{B}}^{0}\mid\widetilde{\mathsf{E}}^{0}\right)=2S\left(\widetilde{D}^{t+1}\right)-S\left(\widetilde{D}^{t}\right)-S\left(\widetilde{D}^{t+2}\right).$

Thus Theorem B.5 follows directly from the following theorem.

######  Theorem B.7.

Given an integer $t>1$,
$2S\left(\widetilde{D}^{t}\right)-S\left(\widetilde{D}^{t-1}\right)-S\left(\widetilde{D}^{t+1}\right)=O\left(d\log\mu
d/t\right)$.

###### Proof.

Let $p_{\ell,i}=\Pr\left(D[\ell]={\bf e}_{i}\right)$ an
$p_{\ell,0}=\Pr\left(D[\ell]=0^{2^{n}}\right)$ for $\ell\in[d]$ where ${\bf
e}_{i}$ denotes the $i$-th standard basis vector in $\\{0,1\\}^{2^{n}}$. The
crucial observation is that $\widetilde{D}^{t}$ can also be generated by the
following process:

  * •

For each $\ell\in[d]$ and $i\in[2^{n}]$, sample $\widetilde{t}_{\ell,i}$ from
$\text{Pois}(p_{\ell,i}t\log\mu d)$ independently.

  * •

Let
$\widetilde{D}^{t}=\sum_{l\in[d]}\sum_{i\in[2^{n}]}\widetilde{t}_{\ell,i}{\bf
e}_{i}\bmod{2}$.

Note that
$\left\\{\widetilde{t}_{1,1},\ldots,\widetilde{t}_{d,2^{n}}\right\\}$ are
mutually independent. Then all of the $2^{n}$ bits of $\widetilde{D}^{t}$ are
mutually independent, so

$S\left(\widetilde{D}^{t}\right)=\sum_{i=1}^{2^{n}}S\left(\text{the $i$-th bit
of
}\widetilde{D}^{t}\right)=\sum_{i=1}^{2^{n}}S\left(\mathrm{parity}\left(\sum_{\ell\in[d]}\widetilde{t}_{\ell,i}\right)\right).$

Note that
$\sum_{\ell\in[d]}\widetilde{t}_{\ell,i}\sim\text{Pois}\left(t\log\mu
d\cdot\sum_{\ell\in[d]}p_{\ell,i}\right)$. According to Formula (6) in
[Mül92],

$\Pr\left[\mathrm{parity}\left(\sum_{\ell\in[d]}\widetilde{t}_{\ell,i}\right)=1\right]=\frac{1-e^{-2\mathbb{E}\left[\sum_{\ell\in[d]}\widetilde{t}_{\ell,i}\right]}}{2}=\frac{1-e^{-2t\log\mu
d\cdot\sum_{\ell\in[d]}p_{\ell,i}}}{2}.$

Then we have

$2S\left(\widetilde{D}^{t}\right)-S\left(\widetilde{D}^{t-1}\right)-S\left(\widetilde{D}^{t+1}\right)=\sum_{i=1}^{2^{n}}f\left(\log\mu
d\cdot\sum_{\ell\in[d]}p_{\ell,i}\right)$

where

$\displaystyle f(p)$
$\displaystyle:=2H\left(\frac{1-e^{-2tp}}{2}\right)-H\left(\frac{1-e^{-2(t-1)p}}{2}\right)-H\left(\frac{1-e^{-2(t+1)p}}{2}\right),$
$\displaystyle H(p)$ $\displaystyle:=-p\log p-(1-p)\log(1-p).$

By Lemma B.8 and the fact that $\sum_{\ell,i}p_{\ell,i}\leq d$, we conclude
that

$\displaystyle
2S\left(\widetilde{D}^{t}\right)-S\left(\widetilde{D}^{t-1}\right)-S\left(\widetilde{D}^{t+1}\right)=O\left(\left(e^{-t}d+\sum_{\ell,i}p_{\ell,i}/t\right)\log\mu
d\right)=O(d\log\mu d/t).$

∎

######  Lemma B.8.

For $p\in[0,1]$, $f(p)=O(p/t)$. For $p>1$, $f(p)=O(e^{-t})$.

###### Proof.

$f(p)=0$ when $p=0$. When $p\in(0,1]$, since $H(p)$ is concave,

$\displaystyle f(p)$
$\displaystyle=\left[H\left(\frac{1}{2}-\frac{e^{-2tp}}{2}\right)-H\left(\frac{1}{2}-\frac{e^{-2(t-1)p}}{2}\right)\right]-\left[H\left(\frac{1}{2}-\frac{e^{-2(t+1)p}}{2}\right)-H\left(\frac{1}{2}-\frac{e^{-2tp}}{2}\right)\right]$
$\displaystyle\leq
H^{\prime}\left(\frac{1}{2}-\frac{e^{-2(t-1)p}}{2}\right)\left(\frac{e^{-2(t-1)p}}{2}-\frac{e^{-2tp}}{2}\right)-H^{\prime}\left(\frac{1}{2}-\frac{e^{-2(t+1)p}}{2}\right)\left(\frac{e^{-2tp}}{2}-\frac{e^{-2(t+1)p}}{2}\right)$
$\displaystyle=\frac{1}{\ln
2}\left(e^{2p}-1\right)e^{-2p(t+1)}\left(e^{2p}\tanh^{-1}\left(e^{-2p(t-1)}\right)-\tanh^{-1}\left(e^{-2p(t+1)}\right)\right).$

For $p\in(0,1]$, $\left(e^{2p}-1\right)\leq e^{2}p=O(p)$. Then
$f(p)\leq\frac{e^{2}p}{\ln 2}\cdot
q^{t+1}\left(\frac{1}{q}\tanh^{-1}\left(q^{t-1}\right)-\tanh^{-1}\left(q^{t+1}\right)\right)$
where $q=e^{-2p}\in[e^{-2},1)$. By Lemma B.9, $f(p)=O(p/t)$.

Note that $H(1/2+x)=1+O(x^{2})$ when $x$ is small. Then for $p>1$,

$\displaystyle f(p)$
$\displaystyle=H\left(\frac{1-e^{-2tp}}{2}\right)-H\left(\frac{1-e^{-2(t-1)p}}{2}\right)-H\left(\frac{1-e^{-2(t+1)p}}{2}\right)$
$\displaystyle=\left[2+O\left(e^{-4pt}\right)\right]-\left[1+O\left(e^{-4p(t-1)}\right)\right]-\left[1+O\left(e^{-4p(t+1)}\right)\right]=O(e^{-t}).$

∎

######  Lemma B.9.

Given $t>1,q\in[0,1)$, then
$q^{t+1}\left(\frac{1}{q}\tanh^{-1}\left(q^{t-1}\right)-\tanh^{-1}\left(q^{t+1}\right)\right)=O(1/t).$

###### Proof.

Split the left-hand side of the equation into two parts:

$\left[q^{t}\left(\tanh^{-1}\left(q^{t-1}\right)-\tanh^{-1}\left(q^{t+1}\right)\right)\right]+\left[(1-q)q^{t}\tanh^{-1}\left(q^{t+1}\right)\right].$

By the fact that $\tanh^{-1}(x)$ is convex for $x\in[0,1)$, the first part

$\displaystyle
q^{t}\left(\tanh^{-1}\left(q^{t-1}\right)-\tanh^{-1}\left(q^{t+1}\right)\right)$
$\displaystyle\leq
q^{t}\left(q^{t-1}-q^{t+1}\right)\tanh^{-1^{\prime}}\left(q^{t-1}\right)$
$\displaystyle=q^{2t-1}\frac{1-q^{2}}{1-q^{2(t-1)}}$
$\displaystyle=\frac{q^{2t-1}}{1+q^{2}+q^{4}+\cdots+q^{2(t-2)}}$
$\displaystyle\leq\frac{q^{2t-1}}{(t-1)q^{2(t-2)}}=\frac{q^{3}}{t-1}\leq\frac{1}{t-1}.$

By the inequality $\tanh^{-1}(x)\leq\frac{1}{2}\left(\frac{1+x}{1-x}-1\right)$
for $x\in[0,1)$, the second part

$\displaystyle(1-q)q^{t}\tanh^{-1}\left(q^{t+1}\right)$
$\displaystyle\leq(1-q)q^{t}\cdot\frac{1}{2}\left(\frac{1+q^{t+1}}{1-q^{t+1}}-1\right)$
$\displaystyle=q^{2t+1}\frac{1-q}{1-q^{t+1}}$
$\displaystyle=\frac{q^{2t+1}}{1+q+q^{2}+\cdots+q^{t}}$
$\displaystyle\leq\frac{q^{2t+1}}{(t+1)q^{t}}=\frac{q^{t+1}}{t+1}\leq\frac{1}{t+1}.$

Thus
$q^{t+1}\left(\frac{1}{q}\tanh^{-1}\left(q^{t-1}\right)-\tanh^{-1}\left(q^{t+1}\right)\right)\leq\frac{1}{t-1}+\frac{1}{t+1}=O(1/t)$
for $q\in[0,1)$. ∎

##  Appendix C Public Key Encryption with a Short Classical Secret Key

In this section, we consider a special case of QPKE where the secret key is
classical string of logarithmic length. We show that such kind of QPKE does
not exist in any classical oracle model. In the following, we use the same
notations as in Definition 6.1 except that the key generation ${\sf
Gen}^{\ket{H}}$ is also quantum. Formally,

######  Theorem C.1.

Given a QPKE scheme $({\sf Gen}^{\ket{H}},{\sf Enc}^{\ket{H}},{\sf
Dec}^{\ket{H}})$ with classical keys in the oracle model where
$H\leftarrow\mathcal{O}_{\lambda}$ is any oracle whose quantum query unitary
$U_{H}$ acts on $e_{\lambda}$ qubits, if the scheme satisfies the following
conditions:

  1. 1.

the secret key ${\sf sk}$ is classical string of $O(\log\lambda)$ length;

  2. 2.

it is $\delta$-complete i.e., $\Pr_{r,H}[{\sf Dec}^{\ket{H}}({\sf sk},{\sf
Enc}^{\ket{H}}({\sf pk},m))=m\colon{\sf Gen}^{\ket{H}}(1^{\lambda})\to({\sf
pk},{\sf sk})]\geq\delta$;

  3. 3.

it makes at most $d_{\lambda}$ queries to $H$ at each stage,

then there exists an adversary Eve who outputs her guess $m_{E}$ of $m$ such
that $\Pr[m_{E}=m]\geq\delta-\epsilon$ by making
$O\left(d_{\lambda}^{2}e_{\lambda}{\sf poly}(\lambda)/\epsilon^{2}\right)$
queries.

###### Proof.

Eve only needs to break the two-round QKA between Alice and Bob consisting of
the following steps:

  1. 1.

Alice runs ${\sf Gen}^{\ket{H}}$ to produce ${\sf pk},{\sf sk}$ where ${\sf
sk}$ is a classical string of $O(\log\lambda)$ length, and then sends ${\sf
pk}$ as the first message $\pi_{A}$ to Bob. We call Alice’s algorithm at this
stage $\mathcal{A}_{1}$.

  2. 2.

Upon receiving $\pi_{A}:={\sf pk}$, Bob samples a uniformly random key
$k_{B}$, computes ${\sf ct}\leftarrow{\sf Enc}^{\ket{H}}({\sf pk},k_{B})$ and
sends $\pi_{B}:={\sf ct}$ to Alice. We call Bob’s algorithm at this stage
$\mathcal{B}$.

  3. 3.

Upon receiving $\pi_{B}:={\sf ct}$, Alice outputs her key $k_{A}:={\sf
Dec}^{\ket{H}}({\sf sk},{\sf ct})$. We call Alice’s algorithm at this stage
$\mathcal{A}_{2}$.

Let $\mathsf{B}$ denote the state of Bob aftering running $\mathcal{B}$,
$\mathsf{A}$ denote the state of Alice after runing $\mathcal{A}_{2}$, and
$\pi$ denote $(\pi_{A},\pi_{B})$. Eve’s strategy is as follows:

  1. 1.

Run $\mathcal{B}$ for $t$ times and obtain state
$\mathsf{B}_{1},\mathsf{B}_{2},\ldots,\mathsf{B}_{t}$.

  2. 2.

For each $i\in\\{0,1\\}^{O(\log\lambda)}$, Run $\mathcal{A}_{2}$ with ${\sf
sk}=i$ for $t$ times and obtain state
$\mathsf{A}_{1}^{(i)},\mathsf{A}_{2}^{(i)},\ldots,\mathsf{A}_{t}^{(i)}$.

  3. 3.

Finally, apply the recovery channel in Theorem 3.11 to generate a fake view
$\hat{\mathsf{B}}$ of Bob $\mathsf{B}$ and then use $\hat{\mathsf{B}}$ to
compute key $k_{E}$.

By setting $t=2\ln 2\cdot e_{\lambda}d_{\lambda}/\epsilon^{2}$, we have
$\mathsf{A}\hat{\mathsf{B}}$ is $O(\epsilon)$-close to $\mathsf{A}\mathsf{B}$
by Lemma C.3 and Lemma 2.3. Thus we have $\Pr[k_{E}=k]\geq\delta-\epsilon$ and
Eve needs to make $t\cdot O(d_{\lambda}{\sf
poly}(\lambda))=O(d_{\lambda}^{2}e_{\lambda}{\sf poly}(\lambda)/\epsilon^{2})$
queries. ∎

######  Remark C.2.

Similar to the generalization from Theorem 1.1 to Theorem 1.2, Theorem C.1 can
be generalized to the case where the public key ${\sf pk}$ is quantum, but
${\sf pk}$ needs to be either pure or “efficiently clonable”.

######  Lemma C.3.

There exists $q,q_{1},q_{2},\ldots,q_{{\sf poly}(\lambda)}\in[t]$ such that

$I\left({\sf sk},\mathsf{A}:\mathsf{B}|\mathsf{E},\pi\right)\leq
2e_{\lambda}d_{\lambda}/t$

where
$\mathsf{E}=\left(\mathsf{B}_{1},\mathsf{B}_{2},\ldots,\mathsf{B}_{q},\mathsf{A}_{1}^{(1)},\mathsf{A}_{2}^{(1)},\ldots,\mathsf{A}_{q_{1}}^{(1)},\mathsf{A}_{1}^{(2)},\mathsf{A}_{2}^{(2)},\ldots,\mathsf{A}_{q_{2}}^{(2)},\ldots,\mathsf{A}_{1}^{({\sf
poly}(\lambda))},\ldots,\mathsf{A}_{q_{{\sf poly}(\lambda)}}^{({\sf
poly}(\lambda))}\right)$.

###### Proof.

By chain rule and the fact that ${\sf sk}$ is classical,

$\displaystyle I({\sf sk},\mathsf{A}:\mathsf{B}|\mathsf{E},\pi)$
$\displaystyle=I({\sf
sk}:\mathsf{B}|\mathsf{E},\pi)+I(\mathsf{A}:\mathsf{B}|\mathsf{E},\pi,{\sf
sk})$ $\displaystyle=I({\sf
sk}:\mathsf{B}|\mathsf{E},\pi)+\mathbb{E}_{s}I(\mathsf{A}:\mathsf{B}|\mathsf{E},\pi,{\sf
sk}=s).$

For the first part, observe that states
$\mathsf{B},\mathsf{B}_{1},\ldots,\mathsf{B}_{t}$ are permutation invariant
w.r.t. ${\sf sk},\pi$ and the rest of Eve. Then by Lemma 4.2, there exists
$q\in[t]$ such that $I({\sf
sk}:\mathsf{B}|\pi,\ldots,\mathsf{B}_{1},\mathsf{B}_{2}\ldots,\mathsf{B}_{q})\leq
S(\mathsf{B})/(t+1)\leq 2e_{\lambda}d_{\lambda}/t$. For the second part,
observe that conditioned on ${\sf sk}=s$, states
$\mathsf{A},\mathsf{A}_{1}^{(s)},\ldots,\mathsf{A}_{t}^{(s)}$ are permutation
invariant w.r.t. $\pi$ and the rest of Eve. Then by Lemma 4.2, there exists
$q_{s}\in[t]$ such that $I(\mathsf{A}:\mathsf{B}|{\sf
sk}=s,\pi,\ldots,\mathsf{A}_{1}^{(s)},\mathsf{A}_{2}^{(s)},\ldots,\mathsf{A}_{q_{s}}^{(s)})\leq
S(\mathsf{A}|{\sf sk}=s)/(t+1)\leq 2e_{\lambda}d_{\lambda}/t$. Thus we have
$I({\sf sk},\mathsf{A}:\mathsf{B}|\mathsf{E},\pi)\leq
2e_{\lambda}d_{\lambda}/t$. ∎