We present a new toolkit to understand the relationship between different
cloning games. We first define a notion of non-local classical reductions.
Roughly speaking, a classical non-local reduction transforms a non-local
classical algorithm242424Refer to Section 3 for the definition of a non-local
algorithm., solving a problem $P$ to a non-local classical algorithm solving a
problem $Q$. The reason we consider non-local classical reductions is that it
turns out to be simpler to come up with non-local reductions in the classical
setting. We then show how to generically upgrade some classes of classical
non-local reductions to quantum non-local reductions, the analogous notion for
quantum non-local algorithms. The resulting quantum non-local reductions are
useful in analyzing the relationship between different cloning games.

###  5.1 Definitions

In this section, we borrow definitions from Section 3 of [BBK22] and adapt
them to the non-local setting252525For simplicity, we omit explicit
purification of quantum solvers (see Definition 3.5), as we will make nearly
black-box use of the results of [BBK22]..

##### Extension.

Similar to Definition 13, we define the notion of an extension over random
coins in this context.

######  Definition 22 ($d$-extension).

We say that a distribution $\widetilde{\mathcal{D}}$ over
$\left\\{0,1\right\\}^{d}\times\left\\{0,1\right\\}^{d}$ is a _$d$ -extension_
if for $(r_{\mathcal{B}},r_{\mathcal{C}})\leftarrow\widetilde{\mathcal{D}}$,
the marginal distributions of both $r_{\mathcal{B}}$ and $r_{\mathcal{C}}$ are
$\mathcal{U}_{\left\\{0,1\right\\}^{d}}$.

####  5.1.1 Classical Assumptions

The first two definitions below are commonly used in the cryptography
literature. Note that we use $\mathsf{GenC},\mathsf{Ver}$ to denote the
algorithms in order to point out the connection between a non-interactive
assumption and the challenge phase of a cloning game (see Definitions 2 and
6).

######  Definition 23 (Non-Interactive Assumption).

A non-interactive assumption
$\mathfrak{A}=(d,n,m,\mathsf{GenC},\mathsf{Ver},c)$ is associated with
polynomials $d(\lambda),n(\lambda),m(\lambda)$ and a tuple
$P=(\mathsf{GenC},\allowbreak\mathsf{Ver},\allowbreak c)$ with the following
syntax. Here, $\mathsf{GenC}$ and $\mathsf{Ver}$ are classical algorithms, and
$c:\mathbb{N}\to\mathbb{R}^{+}\cup\\{0\\}$ is the assumption’s threshold.

  * •

Challenge generator, $\mathsf{GenC}(1^{\lambda};r)$: on input security
parameter $\lambda$ and random coins $r\in\\{0,1\\}^{d}$, outputs a challenge
$x\in\\{0,1\\}^{n}$.

  * •

Verifier, $\mathsf{Ver}(1^{\lambda},r,y)$: on input security parameter
$\lambda$, random coins $r\in\\{0,1\\}^{d}$, and answer $y\in\\{0,1\\}^{m}$,
outputs $1$ (accept) or $0$ (reject).

We will sometimes use $P$ and $\mathfrak{A}$ interchangeably, with the
understanding that the polynomials $d,n,m$ are implicit. We say that $P$ is
_evasive_ if $c$ is a negligible function.

Another important property is called _verifiably polynomial image_ , and
informally it requires that it is possible to verify if a solution lies in a
polynomial-size superset of valid solutions without the random coins $r$ of
$\mathsf{GenC}$.

######  Definition 24 (Verifiably Polynomial Image).

A non-interactive assumption
$\mathfrak{A}=(d,n,m,\mathsf{GenC},\mathsf{Ver},c)$ has a _verifiably
polynomial image_ if there exists a polynomial $k(\lambda)$ and an efficient
verifier $K$ such that for every $x\in\left\\{0,1\right\\}^{n}$, the set
$Y_{x}:=|\\{y\ :\ K(1^{\lambda},x,y)=1\\}|$ has size at most $k$ and for any
valid challenge $x=G(1^{\lambda};r)$ and answer
$\mathsf{Ver}(1^{\lambda},r,y)=1$, it holds that $y\in Y_{x}$.

######  Remark 4.

At a high level, the above definition states that a non-interactive assumption
with verifiably polynomial range has a public verification algorithm $K$ that
accepts all the solutions also accepted by $\mathsf{Ver}$ (and possibly, more)
such that for any $x$, the set of strings accepted by $K$ should be of
polynomial size.

####  5.1.2 Solvers

##### Local Solvers.

A local solver for a non-interactive assumption $P$, which we call a _$P$
-solver_, is a pair $\mathcal{A}=(\widetilde{alice},{\sf state}_{0})$, where
$\widetilde{\mathcal{A}}$ is an algorithm which takes as input a challenge
$x\in\left\\{0,1\right\\}^{n}$ and outputs an answer
$y\in\left\\{0,1\right\\}^{m}$, whereas ${\sf state}_{0}$ is an initial state.
We define the value and advantage of a local solver below:

######  Definition 25 (Value and Advantage of a Local Solver (Definition 3.3
in [BBK22])).

Let $\mathfrak{A}=(d,n,m,\mathsf{GenC},\mathsf{Ver},c)$ be a non-interactive
assumption, with $P=(\mathsf{GenC},\mathsf{Ver},c)$, and let
$\mathcal{A}=(\widetilde{\mathcal{A}},{\sf state}_{0})$ be a $P$-solver. We
define the (one-shot) value and advantage of $\mathcal{A}$, parameterized by
the security parameter $\lambda$, as

$\displaystyle\mathsf{val}_{P}[\mathcal{A}]=\Pr\left[\mathsf{Ver}(1^{\lambda},r,y)=1\;\Bigg{|}\;\begin{subarray}{c}r\xleftarrow{\$}\left\\{0,1\right\\}^{d}\\\
x=\mathsf{GenC}(1^{\lambda};r)\\\
y\leftarrow\widetilde{\mathcal{A}}(1^{\lambda},x,{\sf
state}_{0})\end{subarray}\right],\quad\mathsf{adv}_{P}[\mathcal{A}]=\left|\mathsf{val}_{P}[\mathcal{A}]-c\right|.$

##### Non-Local Solvers.

Below, we adapt Definition 25 to the non-local setting. A non-local adversary
consists of two (possibly inefficient) algorithms $(\mathcal{B},\mathcal{C})$,
where both $\mathcal{B}$ and $\mathcal{C}$ are given (possibly correlated)
instances from a non-interactive assumption. Each adversary is expected to
solve the instance they get. Note that both $\mathcal{B}$ and $\mathcal{C}$
are not allowed to communicate with each other. In the end, the adversary wins
if both $\mathcal{B}$ and $\mathcal{C}$ win. In general, for algorithms
$\mathcal{B}$ and $\mathcal{C}$ acting on separate registers, we call the
algorithm $\mathcal{B}\otimes\mathcal{C}$ a non-local algorithm262626A non-
local algorithm can be implemented by two spatially separated and non-
communicating parties, hence the name.. We consider the non-uniform setting,
where both $\mathcal{B}$ and $\mathcal{C}$ could share some auxiliary
information (either a string or a quantum state, depending on whether the
adversary is classical or quantum) in the very beginning.

In order to define reductions, we need to define stateful solvers. Suppose in
a reduction, we use the solver for a problem $P$ to design a solver for
problem $Q$. Suppose the $Q$ solver runs the $P$ solver multiple times. In the
classical setting, the $P$ solver could be stateless, whereas in the quantum
setting the $P$ solver is inherently stateful and thus, we need to define
stateful solvers appropriately below. Formally, we adapt Definition 3.4 from
[BBK22] to the non-local setting.

######  Definition 26 (Non-Local Stateful Solvers: Syntax).

Let $P$ be a non-interactive assumption with $d$-bit random coins.

Let
$\ell=\ell(\lambda),\ell_{\mathcal{B}}=\ell_{\mathcal{B}}(\lambda),\ell_{\mathcal{C}}=\ell_{\mathcal{C}}(\lambda)$
be functions such that
$\ell_{\mathcal{B}}(\lambda)+\ell_{\mathcal{C}}(\lambda)=\ell(\lambda)$ and
let $\widetilde{\mathcal{D}}$ be a $d$-extension. An
$(\ell,\ell_{\mathcal{B}},\ell_{\mathcal{C}})$-stateful non-local
$(P,\widetilde{\mathcal{D}})$-solver ${\cal A}=(\mathcal{B},\mathcal{C},{\sf
state}_{0}=\\{{\sf state}_{0,\lambda}\\}_{\lambda})$ is defined as follows.

  * •

${\sf state}_{0}=\\{{\sf state}_{0,\lambda}\\}_{\lambda}$ is a sequence of
bipartite $\ell$-qubit states (with the partitions being
$\ell_{\mathcal{B}}$-qubit register ${\bf B}$ and $\ell_{\mathcal{C}}$-qubit
register ${\bf C}$).

  * •

${\cal A}$ is a quantum algorithm that takes as input a security parameter
$1^{\lambda}$, a step $1^{t}$, a pair of challenges
$x_{\mathcal{B}},x_{\mathcal{C}}\in\\{0,1\\}^{n}$, and ${\sf state}=({\sf
state}_{\mathcal{B}},{\sf state}_{\mathcal{C}})$, which is an $\ell$-qubit
bipartite state. It runs
$(\mathcal{B}(1^{\lambda},x_{\mathcal{B}},\cdot)\otimes\mathcal{C}(1^{\lambda},x_{\mathcal{C}},\cdot))({\sf
state})$, with $\mathcal{B}$ getting as input register ${\bf B}$ and
$\mathcal{C}$ getting as input ${\bf C}$, to obtain
$(y_{\mathcal{B}},y_{\mathcal{C}},{\sf state}^{\prime})$, where
$y_{\mathcal{B}}\in\\{0,1\\}^{m}$ is $\mathcal{B}$’s output,
$y_{\mathcal{C}}\in\\{0,1\\}^{m}$ is $\mathcal{C}$’s output and ${\sf
state}^{\prime}=({\sf state}^{\prime}_{\mathcal{B}},{\sf
state}^{\prime}_{\mathcal{C}})$ is a bipartite $\ell$-qubit state on
$\ell_{\mathcal{B}}$-qubit register ${\bf B}$ and $\ell_{\mathcal{C}}$-qubit
register ${\bf C}$ with ${\bf B}$ (resp., ${\bf C}$) being the output of
$\mathcal{B}$ (resp., $\mathcal{C}$). ${\cal A}$ outputs
$(y_{\mathcal{B}},y_{\mathcal{C}},{\sf state}^{\prime})$.

If the states ${\sf state}_{i,\lambda}$ are classical strings and
$(\mathcal{B},\mathcal{C})$ are classical algorithms, then $\mathcal{A}$ is
called a classical non-local stateful solver, otherwise it is called a quantum
non-local stateful solver. If
$\widetilde{\mathcal{D}}=\mathcal{U}_{\left\\{0,1\right\\}^{d}\times\left\\{0,1\right\\}^{d}}$,
then $\mathcal{A}$ is called an _independent-challenge_ $P$-solver.

######  Remark 5.

Even though the definition above of a non-local
$(P,\widetilde{\mathcal{D}})$-solver does not depend on
$\widetilde{\mathcal{D}}$, it will be used to define the value and advantage
of the solver below.

##### Examples of Non-Local Solvers:

For instance, if $P$ is inverting a one-way function $f$, then $\mathcal{B}$
and $\mathcal{C}$ respectively get $x_{\mathcal{B}}=f(z_{\mathcal{B}})$ and
$x_{\mathcal{C}}=f(z_{\mathcal{C}})$ as challenges, where
$(z_{\mathcal{B}},z_{\mathcal{C}})$ is pair of uniform inputs arbitrarily
correlated depending on $\widetilde{\mathcal{D}}$. In order to pass
verification, $\mathcal{B}$ needs to output $y_{\mathcal{B}}=z_{\mathcal{B}}$
and $\mathcal{C}$ needs to output $y_{\mathcal{C}}=z_{\mathcal{C}}$. Another
example is when $P$ is distinguishing the output of a PRG $G$ from a random
string. In this case, $x_{\mathcal{B}}$ and $x_{\mathcal{C}}$ are each either
a uniform output of $G$ or a uniformly random string. In order to pass
verification, $\mathcal{B}$ and $\mathcal{C}$ need to correctly guess which
one. The correct answer for $\mathcal{B}$ and $\mathcal{C}$, may be
arbitrarily correlated depending on $\widetilde{\mathcal{D}}$. Furthermore,
$x_{\mathcal{B}},x_{\mathcal{C}}$ could be correlated still conditioned on the
answers.

We formalize the interaction between a non-local solver and a non-local
algorithm below. Formally, we adapt Definition 3.6 from [BBK22].

######  Definition 27 (Non-Local Solver Interaction).

Let $P=(\mathsf{GenC},\mathsf{Ver},c)$ be a non-interactive assumption. For
any stateful $(P,\widetilde{\mathcal{D}})$-solver ${\cal
A}=(\mathcal{B}_{{\cal A}},\mathcal{C}_{{\cal A}},{\sf state}_{0})$, and
${\cal S}=(\mathcal{B}_{\cal S},\mathcal{C}_{\cal S})$, where
$\mathcal{B}_{\cal S}$ and non-local algorithm $\mathcal{C}_{\cal S}$ are a
pair of algorithms, with input
$z=(z_{\mathcal{B}},z_{\mathcal{C}})\in\\{0,1\\}^{*}$, we consider the process
${\cal S}^{{\cal A}}_{z}(1^{\lambda})$ of the algorithm interacting with the
solver. We define this process below.

  * •

${\cal S}$ is invoked on the input
$(1^{\lambda},z_{\mathcal{B}},z_{\mathcal{C}},{\sf state}_{0})$, where
$\mathcal{B}_{\cal S}$ receives as input $z_{\mathcal{B}}$ and
$\mathcal{C}_{\cal S}$ receives as input $z_{\mathcal{C}}$. Moreover, ${\sf
state}_{0}$ is defined on two registers ${\bf B}$ and ${\bf C}$, with
${\mathcal{B}}_{\cal S}$ receiving the register ${\bf B}$ and
${\mathcal{C}}_{\cal S}$ receiving the register ${\bf C}$. Initialize
$\tau_{\mathcal{B}}$ to contain $z_{\mathcal{B}}$ and $\tau_{\mathcal{C}}$ to
contain $z_{\mathcal{C}}$. At every step $i\geq 1$:

    1. 1.

${\mathcal{B}}_{\cal S}(1^{\lambda},\tau_{\mathcal{B}})$ makes a query
$x_{\mathcal{B}}^{(i)}$ and ${\mathcal{C}}_{\cal
S}(1^{\lambda},\tau_{\mathcal{B}})$ makes a query $x_{\mathcal{C}}^{(i)}$,

    2. 2.

Run $(y_{\mathcal{B}}^{(i)},y_{\mathcal{C}}^{(i)},{\sf
state}_{i})\leftarrow(\mathcal{B}_{{\cal
A}}(1^{\lambda},1^{i},x_{\mathcal{B}}^{(i)},\cdot)\otimes\mathcal{C}_{{\cal
A}}(1^{\lambda},1^{i},x_{\mathcal{C}}^{(i)},\cdot))({\sf state}_{i-1})$, where
$y_{\mathcal{B}}^{(i)}$ is $\mathcal{B}_{\mathcal{A}}$’s output,
$y_{\mathcal{C}}^{(i)}$ is $\mathcal{C}_{\mathcal{A}}$’s output and ${\sf
state}_{i}$ is the joint output of $\mathcal{B}_{\mathcal{A}}$ and
$\mathcal{C}_{\mathcal{A}}$.

    3. 3.

Add $(x_{\mathcal{B}}^{(i)},y_{\mathcal{B}}^{(i)})$ to $\tau_{\mathcal{B}}$
and $(x_{\mathcal{C}}^{(i)},y_{\mathcal{C}}^{(i)})$ to $\tau_{\mathcal{C}}$.

  * •

At the end of the interaction, ${\cal S}$ may produce the output
$(w_{\mathcal{B}},w_{\mathcal{C}})$, where $w_{\mathcal{B}}$ is output by
${\mathcal{B}}_{\cal S}$ and $w_{\mathcal{C}}$ is output by
${\mathcal{C}}_{\cal S}$.

We will sometimes refer to $S$ as a solver-aided non-local algorithm.

##### Non-Local Solver Value, Advantage, and Persistence.

For stateful solvers, we explicitly define their value after interacting with
the assumption many times.

######  Definition 28 (Non-local Stateful Value and Advantage).

Let $P=(\mathsf{GenC},\mathsf{Ver},c)$ be a non-interactive assumption and let
$\mathcal{A}=(\mathcal{B}_{\mathcal{A}},\mathcal{C}_{\mathcal{A}},{\sf
state}_{0})$ be a stateful $(P,\widetilde{\mathcal{D}})$-non-local solver. Let
$\mathcal{S}$ be a solver-aided non-local algorithm with input
$z=(z_{\mathcal{B}},z_{\mathcal{C}})$. Let ${\sf state}_{i}$ be defined as in
Definition 27 for the interaction
$\mathcal{S}^{\mathcal{A}}_{z}(1^{\lambda})$. Then, we define the (many-shot)
value of $\mathcal{S}^{\mathcal{A}}_{z}$ as

$\displaystyle\mathsf{val}_{P}^{\widetilde{\mathcal{D}}}\left[i,\mathcal{S}_{z}^{\mathcal{A}}\right]:=\Pr\left[\begin{subarray}{c}\mathsf{Ver}(1^{\lambda},y_{\mathcal{B}};r_{\mathcal{B}})=1\\\
\land\\\
\mathsf{Ver}(1^{\lambda},y_{\mathcal{C}};r_{\mathcal{C}})=1\end{subarray}\
{\Bigg{|}}\
\begin{subarray}{c}(r_{\mathcal{B}},r_{\mathcal{C}})\leftarrow\widetilde{\mathcal{D}}\\\
x_{\mathcal{B}}=\mathsf{GenC}(1^{\lambda};r_{\mathcal{B}})\\\
x_{\mathcal{C}}=\mathsf{GenC}(1^{\lambda};r_{\mathcal{C}})\\\
(y_{\mathcal{B}},y_{\mathcal{C}},{\sf
state}_{{i+1}})\leftarrow(\mathcal{B}_{{\cal
A}}(1^{\lambda},1^{i+1},x_{\mathcal{B}},\cdot)\otimes\mathcal{C}_{{\cal
A}}(1^{\lambda},1^{i+1},x_{\mathcal{C}},\cdot))({\sf
state}_{i})\end{subarray}\right],$

and for any threshold $c^{*}:\mathbb{N}\to\mathbb{R}^{+}\cup\\{0\\}$, we
define the (many-shot) advantage of $\mathcal{S}^{\mathcal{A}}_{z}$ as

$\displaystyle\mathsf{adv}_{P}^{(\widetilde{\mathcal{D}},c^{*})}\left[i,{\mathcal{A}}\right]:=\left|\mathsf{val}_{P}^{\widetilde{\mathcal{D}}}\left[i,\mathcal{S}_{z}^{\mathcal{A}}\right]-c^{*}(\lambda)\right|$

We define the one-shot value of the solver interaction
$\mathcal{S}^{\mathcal{A}}_{z}$ as
$\mathsf{val}_{P}^{\widetilde{\mathcal{D}}}\left[\mathcal{A}\right]:=\mathsf{val}_{P}^{\widetilde{\mathcal{D}}}\left[0,\mathcal{S}_{z}^{\mathcal{A}}\right]$
and the one-shot advantage of $\mathcal{A}$ with respect to threshold $c^{*}$
as
$\mathsf{adv}_{P}^{(\widetilde{\mathcal{D}},c^{*})}\left[\mathcal{A}\right]:=\mathsf{adv}_{P}^{(\widetilde{\mathcal{D}},c^{*})}\left[0,\mathcal{S}_{z}^{\mathcal{A}}\right]$.
Note that neither value depends on $(\mathcal{S},z)$.

######  Remark 6 (Non-Local vs. Local Threshold).

Above, the non-local threshold $c^{*}$, which is a parameter of the advantage
$\mathsf{adv}_{P}^{(\widetilde{\mathcal{D}},c^{*})}$ of the adversary
$\mathcal{A}$, can depend on the local threshold $c$ as well as the
$d$-extension $\widetilde{\mathcal{D}}$.

######  Definition 29 (Non-Local Persistence).

Let $P$ be a non-interactive assumption. A distribution $\mathbb{B}$ on
$(P,\widetilde{\mathcal{D}})$-non-local solvers
$\left\\{\mathcal{A}^{\alpha}=(\mathcal{B}^{\alpha}_{\mathcal{A}},\mathcal{C}^{\alpha}_{\mathcal{A}},{\sf
state}_{0}^{\alpha})\right\\}_{\alpha}$ is called $(p,\eta)$-persistent if for
any solver-aided non-local algorithm
$\mathcal{S}=(\mathcal{B}_{\mathcal{S}},\mathcal{C}_{\mathcal{S}})$ with input
$z=(z_{\mathcal{B}},z_{\mathcal{C}})$, we have

$\displaystyle\Pr\left[\sup_{i}\left|\mathsf{val}_{P}^{\widetilde{\mathcal{D}}}\left[i,\mathcal{S}_{z}^{\mathcal{A}^{\alpha}}\right]-p\right|\leq\eta\right]\geq
1-\eta,$

where the probability is taken over the randomness of $\alpha$ and the solver
interaction $\mathcal{S}_{z}^{\mathcal{A}^{\alpha}}$.

####  5.1.3 Reductions

A reduction is a transformation that converts a solver for one problem to a
solver for another (possibly different) problem. More precisely, suppose $P$
and $Q$ be two assumptions. A reduction leverages the solver for $P$ to design
a solver for $Q$. We consider the setting when the solver for $Q$ uses the
solver for $P$ as a black-box. As in [BBK22], we consider reductions where the
solver for $Q$ runs the solver for $P$ multiple times. We define analogous
notions of one-shot advantage and persistent advantage below.

We first define the traditional notion of reduction before defining non-local
reductions.

######  Definition 30 (Reduction; Definition 3.12 in [BBK22]).

A classical (resp., quantum) reduction from solving a non-interactive
assumption $Q$ to solving a non-interactive assumption $P$ is an efficient
classical (resp., quantum) uniform algorithm ${\cal R}$ with the following
guarantee.

For any classical (resp., quantum) $P$-solver ${\cal A}_{P}=(A_{P},{\sf
state}_{0})$ with one-shot advantage $\varepsilon$ and runtime $T$, let ${\sf
state}^{\prime}_{0}=({\sf state}_{0},A_{P},1^{1/\varepsilon},1^{T})$. Then,
${\cal A}_{Q}=({\cal R},{\sf state}^{\prime}_{0})$ is a classical (resp.,
quantum) $Q$-solver with one-shot advantage
$\varepsilon^{\prime}=\mathsf{poly}(\varepsilon,\allowbreak
T^{-1},\allowbreak\lambda^{-1})$ and runtime
$\mathsf{poly}(T,\varepsilon^{-1},\allowbreak\lambda)$. An _inefficient_
reduction is defined the same way without the runtime requirement and the
dependency on $T$.

##### Non-Local Reductions.

We now generalize the above definition to the non-local setting.

######  Definition 31 (Non-Local Reduction).

A non-local classical (resp., quantum)
$(\widetilde{\mathcal{D}}_{P},c_{P}^{*},\widetilde{\mathcal{D}}_{Q},c_{Q}^{*})$-reduction
from solving a non-interactive assumption $Q$ to solving a non-interactive
assumption $P$ is an efficient classical (resp., quantum) uniform non-local
algorithm ${\cal R}=(\mathcal{R}_{1},\mathcal{R}_{2})$ with the following
guarantee.

Given any non-local classical (resp., quantum)
$(P,\widetilde{\mathcal{D}})$-solver ${\cal
A}_{P}=(\mathcal{B}_{P},\mathcal{C}_{P},{\sf state}_{0})$ with one-shot
advantage
$\varepsilon=\mathsf{adv}_{P}^{(\widetilde{\mathcal{D}},c_{P}^{*})}\left[\mathcal{A}_{P}\right]$
and runtime $T$, let ${\sf state}^{\prime}_{0}=({\sf
state}_{0},\mathcal{B}_{P},\mathcal{C}_{P},1^{1/\varepsilon},1^{T})$. Then,
${\cal A}_{Q}=({\cal R}_{1},{\cal R}_{2},{\sf state}^{\prime}_{0})$ is a
$(Q,\widetilde{\mathcal{D}}_{Q})$-solver with one-shot advantage
$\varepsilon^{\prime}=\mathsf{adv}_{Q}^{(\widetilde{\mathcal{D}},c_{Q}^{*})}\left[\mathcal{A}_{Q}\right]=\mathsf{poly}(\varepsilon,T^{-1},\lambda^{-1})$
and runtime $\mathsf{poly}(T,\varepsilon^{-1},\lambda)$. Here, it is
understood that description of $\mathcal{B}_{P}$ (resp., $\mathcal{C}_{P}$) is
included as part of ${\cal R}_{1}$’s (resp., ${\cal R}_{2}$’s) register. An
_inefficient_ non-local reduction is defined the same way without the runtime
requirement and the dependency of $T$.

######  Definition 32 (Non-Local Black-Box Reduction).

A non-local black-box
$(\widetilde{\mathcal{D}}_{P},c_{P}^{*},\widetilde{\mathcal{D}}_{Q},c_{Q}^{*})$-reduction
$\mathcal{R}=(\mathcal{R}_{1},\mathcal{R}_{2})$ from solving
$Q=(\mathsf{GenC}_{Q},\mathsf{Ver}_{Q},c_{Q})$ to solving
$P=(\mathsf{GenC}_{P},\mathsf{Ver}_{P},c_{P})$ is a non-local
$(\widetilde{\mathcal{D}}_{P},c_{P}^{*},\widetilde{\mathcal{D}}_{Q},c_{Q}^{*})$-reduction
such that $\mathcal{R}_{1}$ (resp., ${\cal R}_{2}$) interacts with
$\mathcal{B}_{P}$ (resp., $\mathcal{C}_{P}$) as defined in Definition 27.

We further say that ${\cal R}$ is _non-adaptive_ if $\mathcal{R}_{1}$ (resp.,
${\cal R}_{2}$) produces its queries to $\mathcal{B}_{P}$ (resp.,
$\mathcal{C}_{P}$) independent of the answers to its previous queries (or
equivalently all at once).

###  5.2 Main Theorem

In our main theorem, we show how to relate the unclonable security of two
cloning games $\mathcal{G},\mathcal{G}^{\prime}$ which satisfy a similarity
condition in the setup phase as well as some additional properties. Before we
state the formal theorem, we first describe how the notions of non-interactive
assumption and unclonable security are connected by introducing relevant
notation.

##### Assumption Induced by a Cloning Experiment.

Let $\mathcal{G}=(\mathsf{Setup},\mathsf{GenT},\mathsf{GenC},\mathsf{Ver})$ be
a stateful272727Recall that stateful cloning games (Definition 12) generalize
cloning games, so that this definition applies the same to cloning games that
are not stateful. cloning game with message space $\mathcal{M}$. For every
$m\in\mathcal{M}$, message distribution $\mathcal{D}_{\mathcal{M}}$, and
secret key $\mathsf{sk}$ in the support of $\mathsf{Setup}(1^{\lambda})$, we
consider the induced non-interactive assumption
$\mathfrak{A}^{\mathcal{G},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}}=(d,n,\ell,\mathsf{GenC}^{\mathcal{G},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}},\mathsf{Ver}^{\mathcal{G},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}},c)$.
Here $d$ is the length of the random coins used by $\mathsf{GenC}$, $n$ is the
length of the challenges output by $\mathsf{GenC}$, and $\ell$ is the length
of the answers received by $\mathsf{GenC}$. In addition,
$\mathsf{GenC}^{\mathcal{G},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}}(1^{\lambda};r):=\mathsf{GenC}(\mathsf{sk},m;r)$
and
$\mathsf{Ver}^{\mathcal{G},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}}(1^{\lambda},r,\mathsf{ans}):=\mathsf{Ver}(\mathsf{sk},m,\mathsf{ch},\mathsf{ans},r)$.282828Note
that this is well-defined since $\mathsf{ch}$ can be computed
deterministically given $\mathsf{sk},m,r$. Finally, we will set
$c:=p^{\mathsf{triv}}(\mathcal{G},\mathcal{D}_{\mathcal{M}})$ for the message
distribution $\mathcal{M}$ considered for unclonable security. As before, we
write
$P^{\mathcal{G},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}}=(\mathsf{GenC}^{\mathcal{G},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}},\mathsf{Ver}^{\mathcal{G},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}},c)$
to denote the assumption when the parameters $d,n,\ell$ are implicit.

######  Theorem 13 (Main Theorem).

Let $\mathcal{G}=(\mathsf{Setup},\mathsf{GenT},\mathsf{GenC},\mathsf{Ver})$
and
$\mathcal{G}^{\prime}=(\mathsf{Setup}^{\prime},\mathsf{GenT}^{\prime},\mathsf{GenC}^{\prime},\mathsf{Ver}^{\prime})$
be cloning games with the same message space $\mathcal{M}$. Let
$\mathcal{D}_{\mathcal{M}}$ be a message distribution, and
$\widetilde{\mathsf{GenC}}$ be an extension of $\mathsf{GenC}$. Suppose that
the following conditions are satisfied:

  1. (1)

$\mathsf{Setup}=\mathsf{Setup}^{\prime}$ and
$\mathsf{GenT}=\mathsf{GenT}^{\prime}$.

  2. (2)

$\mathcal{G}^{\prime}$ is $\mathcal{D}_{\mathcal{M}}$-evasive.

  3. (3)

Either $\mathcal{G}$ is $\mathcal{D}_{\mathcal{M}}$-evasive or
$\widetilde{\mathsf{GenC}}=\widetilde{\mathsf{GenC}}_{\mathsf{ind}}$.

For $\mathsf{sk}$ in the support of $\mathsf{Setup}$ and message
$m\in\mathcal{M}$, consider the induced non-interactive assumptions

$\displaystyle
P=P^{\mathcal{G},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}}=(\mathsf{GenC}^{\mathcal{G},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}},\mathsf{Ver}^{\mathcal{G},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}},p^{\mathsf{triv}}(\mathcal{G},\mathcal{D}_{\mathcal{M}},\widetilde{\mathsf{GenC}}))$

and

$\displaystyle
Q=Q^{\mathcal{G}^{\prime},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}}=(\mathsf{GenC}^{\mathcal{G}^{\prime},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}},\mathsf{Ver}^{\mathcal{G}^{\prime},\mathcal{D}_{\mathcal{M}}}_{{\mathsf{sk},m}},p^{\mathsf{triv}}(\mathcal{G}^{\prime},\mathcal{D}_{\mathcal{M}})).$

Suppose further that the following conditions are satisfied:

  1. (a)

For all $(\mathsf{sk},m)$, $P$ has a verifiably polynomial image.

  2. (b)

For all $(\mathsf{sk},m)$, there exists a classical non-adaptive black-box
reduction $\mathcal{R}$ from solving non-interactive assumption $Q$ to solving
non-interactive assumption $P$. Furthermore, the description of $\mathcal{R}$
does not depend on $(\mathsf{sk},m)$.

  3. (c)

$\mathcal{G}^{\prime}$ has $(\mathcal{D}_{\mathcal{M}},\mathsf{negl})$
independent-challenge unclonable security.

Then, $\mathcal{G}$ has
$(\mathcal{D}_{\mathcal{M}},\mathsf{negl},\widetilde{\mathsf{GenC}})$
unclonable security.

The proof of the main theorem consists of 3 technical steps: (1) going from
the classical reduction given in item (b) to a classical non-local reduction,
(2) going from non-local $(Q,\widetilde{\mathcal{D}}_{Q})$-solver to
independent-challenge $Q$-solver, and (3) lifting classical reduction to
quantum. We will formally discuss each step in Section 5.3. We include the
final proof below to aid the reader in reading Section 5.3.

###### Proof of Theorem 13.

Define
$c_{P}=p^{\mathsf{triv}}(\mathcal{G},\mathcal{D}_{\mathcal{M}},\widetilde{\mathsf{GenC}})$
and $c_{Q}=p^{\mathsf{triv}}(\mathcal{G}^{\prime},\mathcal{D}_{\mathcal{M}})$.
By condition (2), $Q$ is evasive, i.e. $c_{Q}$ is negligible. By conditions
(2),(b) and Lemma 16, there exists a classical non-adaptive black-box non-
local
$(\widetilde{\mathcal{D}}_{O},c_{P},\widetilde{\mathcal{D}}_{Q},c_{Q})$-reduction
from solving $Q$ to solving $P$, where
$\widetilde{\mathcal{D}}_{P},\widetilde{\mathcal{D}}_{Q}$ denote uniform
extensions.

By Theorem 22, there exists a quantum non-local
$(\widetilde{\mathcal{D}}_{O},c_{P},\widetilde{\mathcal{D}}_{Q},c_{Q})$-reduction
$\mathcal{R}^{\prime}$ from solving $Q$ to solving $P$. Combining this with
Corollary 3 if $\mathcal{G}$ is $\mathcal{D}_{\mathcal{M}}$-evasive, and
trivially if
$\widetilde{\mathsf{GenC}}=\widetilde{\mathsf{GenC}}_{\mathsf{ind}}$,
$\mathcal{R}^{\prime}$ is also a quantum non-local
$(\widetilde{\mathsf{GenC}},c_{P},\widetilde{\mathcal{D}}_{Q},c_{Q})$-reduction
from solving $Q$ to solving $P$.

Now, let $\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ be a QPT adversary
which breaks $(\mathcal{D}_{\mathcal{M}},\varepsilon)$ unclonable security of
$\mathcal{G}$ for a non-negligible function $\varepsilon$. Let
$\varepsilon_{\mathsf{sk},m}$ be the one-shot value of
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ in assumption $P$ defined
above with respect to $c_{P}$, so that
$\left|\operatorname*{\mathbb{E}}_{\mathsf{sk},m}\left[\varepsilon_{\mathsf{sk},m}-c_{P}\right]\right|>\varepsilon$.
Note that since the description of $\mathcal{R}$ does not depend on
$(\mathsf{sk},m)$, neither does the description of $\mathcal{R}^{\prime}$.

Let $(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime})$ be the
induced QPT adversary obtained by giving the solver
$(\mathcal{B}^{\prime},\mathcal{C}^{\prime},\mathcal{A}(\rho_{\mathsf{sk},m}))$
as input to $\mathcal{R}$, where
$\rho_{\mathsf{sk},m}\leftarrow\mathsf{GenT}(\mathsf{sk},m)$ is the token
received by $\mathcal{A}$ in $\mathcal{G}$. That is, $\mathcal{A}^{\prime}$ is
defined in terms of $\mathcal{A}$ and how the state
$\mathcal{A}(\rho_{\mathsf{sk},m})$ is modified by the reduction
$\mathcal{R}^{\prime}$, whereas $(\mathcal{B}^{\prime},\mathcal{C}^{\prime})$
is the non-local algorithm output by $\mathcal{R}^{\prime}$. Note that this is
well-defined since the description of $\mathcal{R}^{\prime}$ does not depend
on $(\mathsf{sk},m)$. Define $\varepsilon^{\prime}_{\mathsf{sk},m}$ as the
one-shot value of
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$
in $\mathcal{G}^{\prime}$.

By the guarantee of $\mathcal{R}^{\prime}$, we have
$\left|\varepsilon^{\prime}_{\mathsf{sk},m}-c_{Q}\right|\geq
q(\left|\varepsilon_{\mathsf{sk},m}-c_{P}\right|)$ for all $(\mathsf{sk},m)$
and some polynomial $q$. Without loss of generality, we can take
$q(x)=x^{\beta}$ for some constant $\beta>1$, so that $q$ is a monotone,
convex function. Taking the expectation and using Jensen’s Inequality, we
obtain

$\displaystyle q(\varepsilon)$
$\displaystyle<q\left(\left|\operatorname*{\mathbb{E}}_{\mathsf{sk},m}\left[\varepsilon_{\mathsf{sk},m}-c_{P}\right]\right|\right)\leq
q\left(\operatorname*{\mathbb{E}}_{\mathsf{sk},m}\left[\left|\varepsilon_{\mathsf{sk},m}-c_{P}\right|\right]\right)\leq\operatorname*{\mathbb{E}}_{\mathsf{sk},m}\left[q\left(\left|\varepsilon_{\mathsf{sk},m}-c_{P}\right|\right)\right]\leq\operatorname*{\mathbb{E}}_{\mathsf{sk},m}\left[\left|\varepsilon^{\prime}_{\mathsf{sk},m}-c_{Q}\right|\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{\mathsf{sk},m}\left[\varepsilon^{\prime}_{\mathsf{sk},m}+c_{Q}\right]\leq
2c_{Q}+\left|\operatorname*{\mathbb{E}}_{\mathsf{sk},m}\left[\varepsilon^{\prime}_{\mathsf{sk},m}-c_{Q}\right]\right|,$

hence
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$
breaks the $(\mathcal{D}_{\mathcal{M}},q(\varepsilon)-2c_{Q})$ unclonable
security of $\mathcal{G}^{\prime}$, which suffices for the proof since $c_{Q}$
is negligible and $\varepsilon$ is non-negligible.

∎

##### Alternate Versions of the Main Theorem.

We give two more versions of the main theorem, which could be useful for
applications. The first one (Theorem 14) is for information theoretic
applications, including our single-decryptor encryption construction in
Section 5.4.1. The second one (Theorem 15) concerns the case when
$\mathcal{G},\mathcal{G}^{\prime}$ do not have identical setup phases, yet
they are equivalent modulo a local quantum transformation applied by
$\mathcal{A}$, hence relaxing condition (1) of Theorem 13.

######  Theorem 14 (Main Theorem - Inefficient Version).

Let
$P,Q,\mathcal{G},\mathcal{G}^{\prime},\mathcal{D}_{\mathcal{M}},\widetilde{\mathsf{GenC}}$
be defined as in Theorem 13. Suppose that the conditions in items (1), (2) and
(3) and item (b) are satisfied. If $\mathcal{G}^{\prime}$ has information
theoretic $(\mathcal{D}_{\mathcal{M}},\mathsf{negl})$ independent-challenge
unclonable security, then $\mathcal{G}$ has information theoretic
$(\mathcal{D}_{\mathcal{M}},\mathsf{negl},\widetilde{\mathsf{GenC}})$
unclonable security.

###### Proof.

The proof follows the same as that of Theorem 13. The only difference is that
since $P$ has no verifiably polynomial image, the non-local reduction is
inefficient as per Theorem 22. ∎

######  Theorem 15 (Main Theorem - General Version).

Theorem 13 holds true if condition (1) is replaced with the following: There
exists a quantum channel $\Gamma$ such that,

$\mathsf{TD}\left(\rho_{\mathsf{sk},m},\Gamma\left(\rho^{\prime}_{\mathsf{sk},m}\right)\right)\leq\mathsf{negl}(\lambda)$

for all key-message pairs $(\mathsf{sk},m)$, where
$\rho_{\mathsf{sk},m}\leftarrow\mathsf{GenT}(\mathsf{sk},m)$ and
$\rho^{\prime}_{\mathsf{sk},m}\leftarrow\mathsf{GenT}^{\prime}(\mathsf{sk},m)$.

###### Proof (sketch).

Follows by modifying the proof of Theorem 13 so that the non-local reduction
first applies $\Gamma$. ∎

We note that the same generalization can be applied to Theorem 14 in the
information theoretic setting.

###  5.3 Proof of the Main Theorem.

In this section, we give the technical details of the 3 steps of the proof of
the main theorem.

##### Step 1: Lifting Classical Local Reduction to Non-Local Reduction.

In Section 5.3.1, we show that any classical reduction from solving $Q$ to
solving $P$ implies a classical non-local reduction, where the assumption $Q$
is assigned the independent-challenge distribution.

##### Step 2: Converting Non-Local Solver to Independent-Challenge Solver.

In Section 5.3.2, we show that any non-local solver with negligible non-local
threshold is an independent-challenge solver. This step is needed because the
third step below requires independent-challenge mode to lift a classical non-
local reduction to quantum.

##### Step 3: Lifting Classical Non-Local Reductions to Quantum Reductions.

In Sections 5.3.3, 5.3.4 and 5.3.5, we adapt the work of [BBK22], which shows
how to lift local non-adaptive black-box reductions to quantum, to the non-
local setting. The main technical contribution occurs in Section 5.3.3, where
we do non black-box analysis of the state-repair procedure of [CMSZ21] to show
that it can be used in the non-local setting.

####  5.3.1 Upgrading Classical Local Reductions to Classical Non-Local
Reductions

Most classical reductions known are for local assumptions, and we will show
below how to obtain a non-local reduction from a local reduction. The non-
local reduction simply runs the local reduction in each register.

######  Lemma 16.

Suppose there exists a classical reduction $\mathcal{R}$ from solving non-
interactive evasive assumption $Q=(\mathsf{GenC}_{Q},\mathsf{Ver}_{Q},c_{Q})$
to solving non-interactive assumption
$P=(\mathsf{GenC}_{P},\mathsf{Ver}_{P},c_{P})$. Let
$\widetilde{\mathcal{D}}_{Q}=\mathcal{U}_{\left\\{0,1\right\\}^{d_{Q}}\times\left\\{0,1\right\\}^{d_{Q}}}$
be the uniform extension. Then, there exists a classical non-local
$(\widetilde{\mathcal{D}}_{P},c_{P},\widetilde{\mathcal{D}}_{Q},c_{Q})$-reduction
$\mathcal{R}^{\prime}=(\mathcal{R}^{\prime}_{1},\mathcal{R}^{\prime}_{2})$
from solving $Q$ to solving $P$ for any $d_{P}$-extension
$\widetilde{\mathcal{D}}_{P}$. Furthermore, $\mathcal{R}^{\prime}$ is non-
adaptive (resp., black-box) if $\mathcal{R}$ is non-adaptive (resp., black-
box).

###### Proof.

The non-local reduction locally runs the classical reduction, i.e.
$\mathcal{R}^{\prime}_{1}=\mathcal{R}^{\prime}_{2}=\mathcal{R}$. Let
$\mathcal{A}=(\mathcal{B},\mathcal{C})$ be a
$(P,\widetilde{\mathcal{D}}_{P})$-solver with one-shot advantage
$\varepsilon=\mathsf{adv}_{P}^{(\widetilde{\mathcal{D}}_{P},c_{P})}\left[\mathcal{A}\right]$.
Let $\mathcal{A}^{\prime}=(\mathcal{B}^{\prime},\mathcal{C}^{\prime})$ be the
non-local adversary output by $\mathcal{R}^{\prime}$. Assume that
$\mathcal{A},\mathcal{A}^{\prime}$ are both stateless. Since
$\varepsilon+c_{P}$ is the probability of $(\mathcal{B},\mathcal{C})$
simultaneously passing verification, it follows that $\mathcal{B}$ and
$\mathcal{C}$ are both $P$-solvers with advantage $\varepsilon$. Thus, by
assumption $\mathcal{B}^{\prime}$ and $\mathcal{C}^{\prime}$ are both
$Q$-solvers with advantage
$\varepsilon^{\prime}=\mathsf{poly}(\varepsilon,T^{-1},\lambda)$, where $T$ is
the runtime of $\mathcal{A}$. Therefore, since $\mathcal{A}^{\prime}$ is an
independent-challenge non-local $Q$-solver, it follows that the advantage of
$\mathcal{A}^{\prime}$ is at least
$(\varepsilon^{\prime}+c_{Q})^{2}-c_{Q}\geq(\varepsilon^{\prime})^{2}-\mathsf{negl}(\lambda)$
as desired.

The argument can be generalized to stateful non-local solvers by convexity. ∎

####  5.3.2 From Non-Local Solvers to Independent-Challenge Solvers

For the second step of the proof of the main theorem, we will show that any
non-local solver is an independent-challenge solver, up to polynomial loss.

######  Theorem 17.

Let $P$ be a non-interactive assumption and let
$c:\mathbb{N}\to\mathbb{R}^{+}\cup\\{0\\}$ be a negligible non-local
threshold. Then, any non-local quantum $(P,\widetilde{\mathcal{D}})$-solver
$\mathcal{A}=(\mathcal{B},\mathcal{C},{\sf state}_{0})$ with one-shot
advantage
$\varepsilon=\mathsf{adv}_{P}^{(\widetilde{\mathcal{D}},c)}\left[\mathcal{A}\right]$
is a quantum independent-challenge $P$-solver with advantage
$\varepsilon^{\prime}=\mathsf{adv}_{P}^{(\widetilde{\mathcal{D}}_{\mathsf{ind}},c)}\left[\mathcal{A}\right]=\mathsf{poly}(\varepsilon)-\mathsf{negl}(\lambda)$,
where $\widetilde{\mathcal{D}}_{\mathsf{ind}}$ is the uniform extension.

###### Proof.

Since $c$ is negligible, it suffices to show
$\mathsf{val}_{P}^{(\widetilde{\mathcal{D}}_{\mathsf{ind}},c)}\left[\mathcal{A}\right]=\mathsf{poly}\left(\mathsf{val}_{P}^{(\widetilde{\mathcal{D}},c)}\left[\mathcal{A}\right]\right)$.
Since the success of a non-local solver can be implemented as a product
measurement, this follows from Lemma 18 below, with the polynomial above given
by $q(x)=x^{3}/216.$ ∎

######  Lemma 18.

Let $\mathcal{R}$ be a finite set of random coins, $\widetilde{\mathcal{D}}$
be a distribution over $\mathcal{R}\times\mathcal{R}$ with marginals
$(\mathcal{D},\mathcal{D})$, and $\rho$ be a mixed bipartite state. Define the
following quantities:

$\displaystyle
p_{cor}=\operatorname*{\mathbb{E}}_{(r,r^{\prime})\leftarrow\widetilde{\mathcal{D}}}\mathsf{Tr}\left[\left(B_{r}\otimes
C_{r^{\prime}}\right)\rho\right],\quad
p_{ind}=\operatorname*{\mathbb{E}}_{r,r^{\prime}\leftarrow\mathcal{D}}\mathsf{Tr}\left[\left(B_{r}\otimes
C_{r^{\prime}}\right)\rho\right],$

where for each $r\in\mathcal{R}$, we have $0\leq B_{r}\leq I$ and $0\leq
C_{r}\leq I$. Then,

$\displaystyle p_{id}\leq 6\sqrt[3]{p_{ind}}$

###### Proof.

We can interpret $B_{r}$ and $C_{r}$ as POVM elements. Thus, by Naimark
Dilation theorem, without loss of generality we can assume that $B_{r}$ and
$C_{r}$ are projections. We can also assume that
$\rho=\ket{\psi}\\!\\!\bra{\psi}$ is a pure state, and the mixed state case
follows by convexity, since $f(x)=6\sqrt[3]{x}$ is a concave function.

Define PSD operators

$\displaystyle
P_{B}:=\operatorname*{\mathbb{E}}_{r\leftarrow\mathcal{D}}B_{r},\quad
P_{C}:=\operatorname*{\mathbb{E}}_{r\leftarrow\mathcal{D}}C_{r},$

and let

$\displaystyle\ket{\psi}=\sum_{i,j}\alpha_{i,j}\ket{\phi_{i}}\ket{\sigma_{j}}$

be the spectral decomposition of $\ket{\psi}$ with respect to $P_{B}\otimes
P_{C}$, where $\ket{\phi_{i}}$ is an eigenvector of $P_{B}$ with eigenvalue
$\lambda_{i}$ and $\ket{\sigma_{j}}$ is an eigenvector of $P_{C}$ with
eigenvalue $\gamma_{j}$. Set $\eta=\sqrt[3]{p_{ind}}$ and define subnormalized
states

$\displaystyle\ket{\psi_{B}}=\sum_{\begin{subarray}{c}i\;:\;\lambda_{i}\leq\eta\\\
j\;:\;\gamma_{j}>\eta\end{subarray}}\alpha_{i,j}\ket{\phi_{i}}\ket{\sigma_{j}},\quad\ket{\psi_{B}}=\sum_{\begin{subarray}{c}i\\\
j\;:\;\gamma_{j}\leq\eta\end{subarray}}\alpha_{i,j}\ket{\phi_{i}}\ket{\sigma_{j}},\quad\ket{\psi_{BC}}=\sum_{\begin{subarray}{c}i\;:\;\lambda_{i}>\eta\\\
j\;:\;\gamma_{j}>\eta\end{subarray}}\alpha_{i,j}\ket{\phi_{i}}\ket{\sigma_{j}},$

so that $\ket{\psi}=\ket{\psi_{B}}+\ket{\psi_{C}}+\ket{\psi_{BC}}$.

We first show the following claim:

######  Claim 1.

$\left\|\psi_{BC}\right\|^{2}\leq\frac{p_{ind}}{\eta^{2}}$, where
$\left\|\cdot\right\|$ is the Euclidean Norm.

###### Proof.

$\displaystyle p_{ind}$
$\displaystyle=\operatorname*{\mathbb{E}}_{r,r^{\prime}\leftarrow\mathcal{D}}\braket{\psi}{\left(B_{r}\otimes
C_{r^{\prime}}\right)}{\psi}$ $\displaystyle=\braket{\psi}{P_{B}\otimes
P_{C}}{\psi}$
$\displaystyle=\sum_{i,j}\left|\alpha_{i,j}\right|^{2}\lambda_{i}\gamma_{j}$
$\displaystyle\geq\sum_{\begin{subarray}{c}i\;:\;\lambda_{i}>\eta\\\
j\;:\;\gamma_{j}>\eta\end{subarray}}\left|\alpha_{i,j}\right|^{2}\lambda_{i}\gamma_{j}$
$\displaystyle\geq\eta^{2}\sum_{\begin{subarray}{c}i\;:\;\lambda_{i}>\eta\\\
j\;:\;\gamma_{j}>\eta\end{subarray}}\left|\alpha_{i,j}\right|^{2}$
$\displaystyle=\eta^{2}\left\|\psi_{BC}\right\|^{2}$

∎

We have:

$\displaystyle p_{cor}$
$\displaystyle=\operatorname*{\mathbb{E}}_{(r,r^{\prime})\leftarrow\widetilde{\mathcal{D}}}\left\|\left(B_{r}\otimes
C_{r^{\prime}}\right)\left(\ket{\psi_{B}}+\ket{\psi_{C}}+\ket{\psi_{BC}}\right)\right\|^{2}$
(Cauchy-Schwartz)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{(r,r^{\prime})\leftarrow\widetilde{\mathcal{D}}}3\left(\left\|(B_{r}\otimes
C_{r^{\prime}})\ket{\psi_{B}}\right\|^{2}+\left\|(B_{r}\otimes
C_{r^{\prime}})\ket{\psi_{C}}\right\|^{2}+\left\|(B_{r}\otimes
C_{r^{\prime}})\ket{\psi_{BC}}\right\|^{2}\right)$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{(r,r^{\prime})\leftarrow\widetilde{\mathcal{D}}}3\left(\left\|(B_{r}\otimes
I)\ket{\psi_{B}}\right\|^{2}+\left\|(I\otimes
C_{r^{\prime}})\ket{\psi_{C}}\right\|^{2}+\left\|\ket{\psi_{BC}}\right\|^{2}\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{r,r^{\prime}\leftarrow\mathcal{D}}3\left(\left\|(B_{r}\otimes
I)\ket{\psi_{B}}\right\|^{2}+\left\|(I\otimes
C_{r^{\prime}})\ket{\psi_{C}}\right\|^{2}+\left\|\ket{\psi_{BC}}\right\|^{2}\right)$
$\displaystyle=3\left(\braket{\psi_{B}}{\left(P_{B}\otimes
I\right)\psi_{B}}+\braket{\psi_{C}}{\left(I\otimes
P_{C}\right)\psi_{C}}+\left\|\psi_{BC}\right\|^{2}\right)$ (1)
$\displaystyle\leq
3\left(\eta\left(\left\|\psi_{B}\right\|^{2}+\left\|\psi_{C}\right\|^{2}\right)+\frac{p_{ind}}{\eta^{2}}\right)$
$\displaystyle\leq 3\left(\eta+\frac{p_{ind}}{\eta^{2}}\right)$
$\displaystyle=6\sqrt[3]{p_{ind}}$

∎

##### Classical Case.

We list the special case when $\mathcal{A}$ in Theorem 17 is a classical
algorithm explicitly below because (1) we will need it in Section 5.4.2 for
our second application of the main theorem, and (2) we can show a quadratic
(instead of cubic) loss for this special case.

######  Corollary 3.

Let $P$ be a non-interactive assumption and let
$c:\mathbb{N}\to\mathbb{R}^{+}\cup\\{0\\}$ be a negligible non-local
threshold. Then, any non-local classical $(P,\widetilde{\mathcal{D}})$-solver
$\mathcal{A}=(\mathcal{B},\mathcal{C},{\sf state}_{0})$ with one-shot
advantage
$\varepsilon=\mathsf{adv}_{P}^{(\widetilde{\mathcal{D}},c)}\left[\mathcal{A}\right]$
is a classical independent-challenge $P$-solver with advantage
$\varepsilon^{\prime}=\mathsf{adv}_{P}^{(\widetilde{\mathcal{D}},c)}\left[\mathcal{A}\right]=\varepsilon^{2}-\mathsf{negl}(\lambda)$.

###### Proof.

Although it follows as a special (classical) case of Theorem 17, we will give
a direct proof, as the classical concrete bound trumps the quantum bound. We
will show that if the one-shot value of $\mathcal{A}$ with respect to
$\widetilde{\mathcal{D}}$ is $\delta$, then its one-shot value in the
independent-challenge setting is at least $\delta^{2}$, which suffices for the
proof. The classical state ${\sf state}_{0}$ can be modeled as a shared random
string. We assume that $\mathcal{A}$ is stateless and the general case follows
by convexity.

Let $\mathcal{R}$ be the space of random coins used by the challenge
generation algorithm $\mathsf{GenC}$ of $P$. Let $p_{r}$ and $q_{r}$ be the
probability that $\mathcal{B}$ and $\mathcal{C}$ pass verification conditioned
on the challenge being generated using randomness $r$, respectively. Since
$\mathcal{A}$ is stateless, we can write the one-shot value of $\mathcal{A}$
in the independent-challenge setting as292929This equation can be thought of
as a no-signalling condition.

$\displaystyle\delta^{\prime}=\frac{1}{|\mathcal{R}|^{2}}\sum_{r,r^{\prime}}p_{r}q_{r^{\prime}}$

On the other hand, the one-shot value of $\mathcal{A}$ with respect to the
extension $\widetilde{\mathcal{D}}$ can be written as

$\displaystyle\delta=\sum_{r,r^{\prime}}\alpha_{r,r^{\prime}}p_{r}q_{r^{\prime}},$

where $\left\\{\alpha_{r,r^{\prime}}\right\\}_{r,r^{\prime}}$ are non-negative
coefficients satisfying

$\displaystyle\sum_{r^{\prime}}\alpha_{r^{\prime},r}=\sum_{r^{\prime}}\alpha_{r,r^{\prime}}=\frac{1}{|\mathcal{R}|}$

for all $r\in\mathcal{R}$. Thus, we have

$\displaystyle\delta^{2}=\sum_{r,r^{\prime},s,s^{\prime}}\alpha_{r,r^{\prime}}\alpha_{s,s^{\prime}}p_{r}q_{r^{\prime}}p_{s}q_{s^{\prime}}$
$\displaystyle\leq\sum_{r,r^{\prime},s,s^{\prime}}\alpha_{r,r^{\prime}}\alpha_{s,s^{\prime}}p_{r}q_{s^{\prime}}$
$\displaystyle=\sum_{r,s^{\prime}}p_{r}q_{s^{\prime}}\sum_{r^{\prime},s}\alpha_{r,r^{\prime}}\alpha_{s,s^{\prime}}$
$\displaystyle=\frac{1}{|\mathcal{R}|^{2}}\sum_{r,s^{\prime}}p_{r}q_{s^{\prime}}$
$\displaystyle=\delta^{\prime}$

as desired.

∎

####  5.3.3 Main Lemma

We will extend Lemma 10 to the non-local setting.

######  Lemma 19 (Main Lemma).

Let $V$ be a classical algorithm and let ${\cal
A}=\mathcal{B}\otimes\mathcal{C}$ be a non-local algorithm, where
$\mathcal{B}$ (resp., $\mathcal{C}$) acts on register ${\bf B}$ (resp., ${\bf
C}$). Define the following algorithms $(\mathsf{NLValEst},\mathsf{NLRepair})$
using the algorithms $\mathsf{ValEst}$ and $\mathsf{Repair}$ described in
Lemma 10:

  * •

$(\rho^{*}_{{\bf B}{\bf
C}},p^{*}_{\mathcal{B}},p^{*}_{\mathcal{C}})\leftarrow\mathsf{NLValEst}_{V,{\cal
A}}(\rho,1^{1/\varepsilon})$: compute
$\left(\mathsf{ValEst}_{V,\mathcal{B}}(\cdot,1^{1/(\varepsilon/2)})\otimes\mathsf{ValEst}_{V,\mathcal{C}}(\cdot,1^{1/(\varepsilon/2)})\right)(\rho_{{\bf
B}{\bf C}})$ to obtain $(p^{*}_{\mathcal{B}})$ ($\mathcal{B}$’s output),
$p^{*}_{\mathcal{C}}$ ($\mathcal{C}$’s output) and $\rho^{*}_{{\bf B}{\bf C}}$
is the joint output of $\mathcal{B}$ and $\mathcal{C}$, where $\mathcal{B}$
(resp., $\mathcal{C}$) output the register ${\bf B}$ (resp., ${\bf C}$).

  * •

$\sigma^{*}_{{\bf B}{\bf C}}\leftarrow\mathsf{NLRepair}_{V,{\cal
A},\Pi_{\mathcal{B}},\Pi_{\mathcal{C}}}\left(\sigma_{{\bf B}{\bf
C}},y_{\mathcal{B}},p_{\mathcal{B}},y_{\mathcal{C}},p_{\mathcal{C}},1^{1/\varepsilon},1^{k}\right)$:
for k-outcome projections $\Pi_{\mathcal{B}},\Pi_{\mathcal{C}}$ on register
${\bf B},{\bf C}$, respectively, compute the following:

$\left(\mathsf{Repair}_{V,\mathcal{B},\Pi_{\mathcal{B}}}\left(\cdot,y_{\mathcal{B}},p_{\mathcal{B}},1^{1/\varepsilon},1^{k}\right)\otimes\mathsf{Repair}_{V,\mathcal{C},\Pi_{\mathcal{C}}}\left(\cdot,y_{\mathcal{C}},p_{\mathcal{C}},1^{1/\varepsilon},1^{k})\right)\right)(\sigma_{{\bf
B}{\bf C}})$

Denote the result by $\sigma^{*}_{{\bf B}{\bf C}}$.

Note that $(\mathsf{NLValEst},\mathsf{NLRepair})$ are efficient303030Here, by
efficient we mean that the runtime of $\mathsf{NLValEst}$ is polynomial in the
size of $\rho$, $1/\varepsilon$, the runtime of $V$ and the runtime of
$\mathcal{A}$. Similarly for $\mathsf{NLRepair}$. algorithms given that
$(\mathsf{ValEst},\mathsf{Repair})$ are efficient algorithms by Lemma 10. In
addition, we have the following guarantees:

  1. 1.

Value Estimation: For any $\varepsilon>0$,

$\displaystyle\operatorname*{\mathbb{E}}_{(\rho^{*}_{{\bf B}{\bf
C}},p^{*}_{\mathcal{B}},p^{*}_{\mathcal{C}})\leftarrow\mathsf{NLValEst}_{V,{\cal
A}}(\mathbf{\rho}_{{\bf B}{\bf
C}},1^{1/\varepsilon})}\left[p_{\mathcal{B}}^{*}p_{\mathcal{C}}^{*}\right]=\Pr\left[\begin{subarray}{c}V(y_{\mathcal{B}};r_{\mathcal{B}})=1\\\
\land\\\
V(y_{\mathcal{C}};r_{\mathcal{C}})=1\end{subarray}\;:\;\begin{subarray}{c}r_{\mathcal{B}},r_{\mathcal{C}}\xleftarrow{\$}\left\\{0,1\right\\}^{d}\\\
(y_{\mathcal{B}},y_{\mathcal{C}})\leftarrow\mathcal{B}(\cdot,r_{\mathcal{B}})\otimes\mathcal{C}(\cdot,r_{\mathcal{C}})(\mathbf{\rho}_{{\bf
B}{\bf C}})\end{subarray}\right].$ (5)

  2. 2.

Almost-Projective Estimation: For any $\varepsilon\geq\varepsilon^{\prime}>0$,

$\displaystyle\Pr\left[\left|p_{\mathcal{B}}^{*}-p_{\mathcal{B}}^{**}\right|\geq\varepsilon\
\lor\
\left|p_{\mathcal{C}}^{*}-p_{\mathcal{C}}^{**}\right|\geq\varepsilon\;:\;\begin{subarray}{c}(\rho^{*}_{{\bf
B}{\bf
C}},p^{*}_{\mathcal{B}},p^{*}_{\mathcal{C}})\leftarrow\mathsf{NLValEst}_{V,{\cal
A}}(\mathbf{\rho}_{{\bf B}{\bf C}},1^{1/\varepsilon})\\\ (\rho^{**}_{{\bf
B}{\bf
C}},p^{**}_{\mathcal{B}},p^{**}_{\mathcal{C}})\leftarrow\mathsf{NLValEst}_{V,{\cal
A}}(\mathbf{\rho}^{*}_{{\bf B}{\bf
C}},1^{1/\varepsilon^{\prime}})\end{subarray}\right]\leq\varepsilon.$

  3. 3.

Repairing: For any state $\mathbf{\rho}_{{\bf B}{\bf C}}$ and any
$\varepsilon>0$,

$\displaystyle\mathsf{Pr}\left[\left|p_{\mathcal{B}}^{*}-p_{\mathcal{B}}^{**}\right|\geq\varepsilon\
\lor\ \left|p_{\mathcal{C}}^{*}-p_{\mathcal{C}}^{**}\right|\geq\varepsilon\ :\
\begin{subarray}{c}(\rho^{*}_{{\bf B}{\bf
C}},p^{*}_{\mathcal{B}},p^{*}_{\mathcal{C}})\leftarrow\mathsf{NLValEst}_{V,{\cal
A}}(\mathbf{\rho}_{{\bf B}{\bf C}},1^{1/\varepsilon})\\\ \ \\\ (\sigma_{{\bf
B}{\bf
C}},y_{\mathcal{B}},y_{\mathcal{C}})\leftarrow(\Pi_{\mathcal{B}}\otimes\Pi_{\mathcal{C}})(\rho^{*}_{{\bf
B}{\bf C}})\\\ \ \\\ \sigma^{*}_{{\bf B}{\bf
C}}\leftarrow\mathsf{NLRepair}_{V,{\cal
A},\Pi_{\mathcal{B}},\Pi_{\mathcal{C}}}\left(\sigma_{{\bf B}{\bf
C}},y_{\mathcal{B}},p^{*}_{\mathcal{B}},y_{\mathcal{C}},p^{*}_{\mathcal{C}},1^{1/\varepsilon},1^{k}\right)\\\
\ \\\ (\rho^{*}_{{\bf B}{\bf
C}},p^{*}_{\mathcal{B}},p^{*}_{\mathcal{C}})\leftarrow\mathsf{NLValEst}_{V,{\cal
A}}(\mathbf{\rho}^{*}_{{\bf B}{\bf
C}},1^{1/\varepsilon})\end{subarray}\right]\leq\varepsilon.$ (6)

###### Proof.

We start with value estimation. Let
$\mathcal{M}^{\mathcal{B}}_{0}=(\Pi_{A},I-\Pi_{A})$ and
$\mathcal{M}^{\mathcal{B}}_{1}=(\Pi_{B},I-\Pi_{B})$ be the projective
measurements applied by
$\mathsf{ValEst}_{V,\mathcal{B}}(\cdot,1^{\varepsilon/2})$. Using Lemma 5, we
decompose the ${\bf B}$ register into Jordan subspaces as $\mathcal{H}_{\bf
B}=\bigoplus S_{j}$. Let
$\left\\{\ket{v^{A}_{j,1}},\ket{v^{A}_{j,0}}\right\\}$ and
$\left\\{\ket{v^{B}_{j,1}},\ket{v^{B}_{j,0}}\right\\}$ be the orthogonal
eigenbases of $S_{j}$ with respect to $\Pi_{A},\Pi_{B}$.

Similarly for $\mathsf{ValEst}_{V,\mathcal{C}}(\cdot,1^{\varepsilon/2})$, we
consider projective measurements
$\mathcal{M}^{\mathcal{C}}_{0}=(\Gamma_{A},I-\Gamma_{A})$ and
$\mathcal{M}^{\mathcal{C}}_{1}=(\Gamma_{B},I-\Gamma_{B})$, with the Jordan
decomposition $\mathcal{H}_{\bf C}=\bigoplus T_{j^{\prime}}$ and the
eigenbases
$\left\\{\ket{w^{A}_{j^{\prime},1}},\ket{w^{A}_{j^{\prime},0}}\right\\}$ and
$\left\\{\ket{w^{B}_{j^{\prime},1}},\ket{w^{B}_{j^{\prime},0}}\right\\}$. For
simplicity, we will assume $\dim S_{j}=\dim T_{j^{\prime}}=2$ for all
$j,j^{\prime}$. The degenerate cases can be handled similarly313131See
[CMSZ21] Section 4.1 to see how to handle degenerate subspaces generically. .

We will need the following claim:

######  Claim 2.

Let $\Pi^{\mathsf{Jor}}_{\bf B}=\left\\{\Pi^{\mathsf{Jor}}_{{\bf
B},j}\right\\}_{j}$ be the jordan subspace measurement, with
$\Pi^{\mathsf{Jor}}_{{\bf
B},j}=\ket{v^{A}_{j,0}}\\!\\!\bra{v^{A}_{j,0}}+\ket{v^{A}_{j,1}}\\!\\!\bra{v^{A}_{j,1}}$.
Similarly define $\Pi^{\mathsf{Jor}}_{\bf C}$. Then, $\Pi^{\mathsf{Jor}}_{\bf
B}$ commutes with $\mathsf{ValEst}_{V,\mathcal{B}}(\cdot,1^{\varepsilon/2})$.
Similarly, $\Pi^{\mathsf{Jor}}_{\bf C}$ commutes with
$\mathsf{ValEst}_{V,\mathcal{C}}(\cdot,1^{\varepsilon/2})$.

###### Proof.

We will show that $\Pi^{\mathsf{Jor}}_{\bf B}$ commutes with
$\mathsf{ValEst}_{V,\mathcal{B}}(\cdot,1^{\varepsilon/2})$. Recall that
$\Pi^{\mathsf{Jor}}_{\bf B}$ commutes with both
$\mathcal{M}^{\mathcal{B}}_{0}$ and $\mathcal{M}^{\mathcal{B}}_{1}$. We write
the register ${\bf B}$ as two registers, ${\bf P}$ and ${\bf Q}$, where ${\bf
P}$ stores the input state and ${\bf Q}$ contains all auxiliary registers used
in the computation. In particular, this means that the measurements
$\mathcal{M}^{\mathcal{B}}_{0},\mathcal{M}^{\mathcal{B}}_{0},\Pi^{\mathsf{Jor}}_{\bf
B}$ are all restricted to the ${\bf P}$ register. By Lemma 10 bullet 3, every
step of $\mathsf{ValEst}_{V,\mathcal{B}}(\cdot,1^{\varepsilon/2})$ falls into
one of the following categories:

  1. 1.

Apply $\mathcal{M}^{\mathcal{B}}_{b}$ on the ${\bf P}$ register conditioned on
a qubit located in the ${\bf Q}$ register for some $b\in\left\\{0,1\right\\}$.
This captures all steps adaptively applying a projective measurement
$\mathcal{M}^{\mathcal{B}}_{b}$.

  2. 2.

Apply a local operation on the ${\bf Q}$ register. This captures the steps
computing the database of outcomes and the functions $f,g$ described in Lemma
10.

Because $\Pi^{\mathsf{Jor}}_{\bf B}$ is a projection applied to the ${\bf P}$
register alone, it commutes with operations from both categories above. ∎

Without loss of generality assume that $\rho$ is a pure state, for the mixed
state case follows by convexity. By assumption, the bipartite state after
steps (a) and (b) described in the 2-Projection Implementation property in
Lemma 10 are performed on both registers has the form

$\displaystyle\sum_{j,j^{\prime}}\alpha_{j,j^{\prime}}\ket{v^{B}_{j,1}}\ket{w^{B}_{j^{\prime},1}}$

Let $\widetilde{\mathsf{ValEst}}$ denote the execution of $\mathsf{ValEst}$
after steps (a) and (b) mentioned above. By 2, the product Jordan subspace
measurement $\Pi^{\mathsf{Jor}}_{\bf B}\otimes\Pi^{\mathsf{Jor}}_{\bf C}$
commutes with $\mathsf{NLValEst}_{V,\mathcal{A}}(\cdot,1^{1/\varepsilon})$,
hence the values $p_{\mathcal{B}}^{*},p_{\mathcal{C}}^{*}$ are distributed as
follows:

  * •

Sample $(j,j^{\prime})$ with probability $|\alpha_{j,j^{\prime}}|^{2}$,

  * •

Compute
$p_{\mathcal{B}}^{*}\leftarrow\widetilde{\mathsf{ValEst}}_{V,\mathcal{B}}(\ket{v^{B}_{j,1}},1^{1/(\varepsilon/2)})$
and
$p_{\mathcal{C}}^{*}\leftarrow\widetilde{\mathsf{ValEst}}_{V,\mathcal{C}}(\ket{v^{B}_{j^{\prime},1}},1^{1/(\varepsilon/2)})$,

  * •

Output $(p_{\mathcal{B}}^{*},p_{\mathcal{C}}^{*})$.

Let $p_{\mathcal{B}}^{j}$ be the value of state $\ket{v^{B}_{j,1}}$ as defined
on the RHS of eq. 3. By the same equation, we know that
$\operatorname*{\mathbb{E}}\left[p_{\mathcal{B}}^{*}|j\right]=p_{\mathcal{B}}^{j}$.
Similarly define $p_{\mathcal{C}}^{j^{\prime}}$ so that
$\operatorname*{\mathbb{E}}\left[p_{\mathcal{C}}^{*}|j^{\prime}\right]=p_{\mathcal{B}}^{j^{\prime}}$.
Let $p^{j,j^{\prime}}$ denote the value of state
$\ket{v^{B}_{j,1}}\ket{v^{C}_{j^{\prime},1}}$ as defined on the RHS of eq. 5.
Because this is pure product state, we have that
$p^{j,j^{\prime}}=p_{\mathcal{B}}^{j}p_{\mathcal{C}}^{j^{\prime}}$, and also
that the variables $p_{\mathcal{B}}^{*},p_{\mathcal{C}}^{*}$ are independent
conditioned on $j,j^{\prime}$. On the other hand, since computing the value
commutes with the Jordan measurements, the value $p$ for the state $\rho$ is
distributed as follows:

  * •

Sample $(j,j^{\prime})$ with probability $|\alpha_{j,j^{\prime}}|^{2}$,

  * •

Output $p^{j,j^{\prime}}$.

Therefore, putting everything together, we have

$\displaystyle\operatorname*{\mathbb{E}}\left[p_{\mathcal{B}}^{*}p_{\mathcal{C}}^{*}\right]$
$\displaystyle=\sum_{j,j^{\prime}}\left|\alpha_{j,j^{\prime}}\right|^{2}\operatorname*{\mathbb{E}}\left[p_{\mathcal{B}}^{*}p_{\mathcal{C}}^{*}|j,j^{\prime}\right]=\sum_{j,j^{\prime}}\left|\alpha_{j,j^{\prime}}\right|^{2}\operatorname*{\mathbb{E}}\left[p_{\mathcal{B}}^{*}|j\right]\cdot\operatorname*{\mathbb{E}}\left[p_{\mathcal{C}}^{*}|j^{\prime}\right]$
$\displaystyle=\sum_{j,j^{\prime}}\left|\alpha_{j,j^{\prime}}\right|^{2}p_{\mathcal{B}}^{j}p_{\mathcal{C}}^{j^{\prime}}=\sum_{j,j^{\prime}}\left|\alpha_{j,j^{\prime}}\right|^{2}p^{j,j^{\prime}}=p$

as desired. Next, we show almost-projective estimation. Recall that
$\mathsf{NLValEst}_{V,{\cal A}}(\cdot,1^{1/\varepsilon})$ applies

$\left(\mathsf{ValEst}_{V,\mathcal{B}}(\cdot,1^{1/(\varepsilon/2)})\otimes\mathsf{ValEst}_{V,\mathcal{C}}(\cdot,1^{1/(\varepsilon/2)})\right),$

and the operations on the ${\bf B},{\bf C}$ registers commute. Therefore,
using condition (2) of Lemma 10 for the state $\mathsf{Tr}_{{\bf
C}}\left(\mathbf{\rho}_{{\bf B}{\bf C}}\right)$, we have
$\Pr\left[\left|p_{\mathcal{B}}^{*}-p_{\mathcal{B}}^{**}\right|\geq\varepsilon\right]\leq\varepsilon/2$,
and similarly
$\Pr\left[\left|p_{\mathcal{C}}^{*}-p_{\mathcal{C}}^{**}\right|\geq\varepsilon\right]\leq\varepsilon/2$.
Using a union bound, we achieve the desired property. The repairing property
follows by a similar argument, after observing that the procedure in eq. 6
involves two parallel executions of eq. 4 on registers ${\bf B}$ and ${\bf
C}$. ∎

####  5.3.4 Achieving Non-Local Persistence

In Theorem 4.1 of [BBK22], the output $p^{*}$ of the value estimation
$\mathsf{ValEst}$ estimates the value of the solver in expectation, and can be
used to achieve a distribution over $(p^{*},\eta)$-persistent solvers. We
observe that the estimation $p^{*}$ could be stored non-locally
$(p_{\mathcal{B}}^{*},p_{\mathcal{C}}^{*})$ such that
$p_{\mathcal{B}}^{*}p_{\mathcal{C}}^{*}=p^{*}$. These local values are enough
for non-local state repair by Lemma 19, and using this the proof of [BBK22]
can be straightforwardly applied to the non-local setting. We state the formal
theorem statement below.

######  Theorem 20 (Non-Local Persistence Theorem).

Let $P$ be a non-interactive falsifiable assumption with a verifiably
polynomial image. Let $\eta=\frac{1}{\mathsf{poly}}$. There exist efficient
non-local quantum algorithms $S=S_{1}\otimes S_{2},R=R_{1}\otimes R_{2}$ with
the following syntax and guarantee:

  * •

$S^{\mathcal{A}}({\sf state}_{0})=\left(S_{1}^{\mathcal{B}}\otimes
S_{2}^{\mathcal{C}}\right)({\sf state}_{0})$ takes as input a non-local
algorithm $\mathcal{A}=(\mathcal{B},\mathcal{C})$ and a bipartite state ${\sf
state}_{0}$. It outputs a state ${\sf state}_{0}^{*}$ and values
$(p_{\mathcal{B}}^{*},p_{\mathcal{C}}^{*})$, where $p_{\mathcal{B}}^{*}$ is
output by $S_{1}^{\mathcal{B}}$ and $p_{\mathcal{C}}^{*}$ is output by
$S_{2}^{\mathcal{C}}$.

  * •

$R^{\mathcal{A}}(1^{\lambda},1^{i},x_{\mathcal{B}},x_{\mathcal{C}},{\sf
state}_{i-1}^{*})=\left(R_{1}^{\mathcal{B}}(1^{\lambda},1^{i},x_{\mathcal{B}},\cdot)\otimes
R_{2}^{\mathcal{C}}(1^{\lambda},1^{i},x_{\mathcal{C}},\cdot)\right)({\sf
state}_{i-1}^{*})$ takes as input a non-local algorithm $\mathcal{A}$, a
security parameter $\lambda$, a step $i$, a pair of inputs
$(x_{\mathcal{B}},x_{\mathcal{C}})$, and a bipartite state ${\sf
state}_{i-1}^{*}$. It outputs a pair of solutions
$(y_{\mathcal{B}},y_{\mathcal{C}})$, where $y_{\mathcal{B}}$ is output by
$R_{2}^{\mathcal{B}}$ and $y_{\mathcal{C}}$ is output by
$R_{2}^{\mathcal{C}}$, and a bipartite state ${\sf state}_{i}^{*}$.

For any non-local independent-challenge $P$-solver
$\mathcal{A}=(\mathcal{B},\mathcal{C},{\sf state}_{0})$ with one-shot value
$p=\mathsf{val}_{P}^{\widetilde{\mathcal{D}}}\left[\mathcal{A}\right]$, with
$\widetilde{\mathcal{D}}=\mathcal{U}_{\left\\{0,1\right\\}^{d}\times\left\\{0,1\right\\}^{d}}$,
considering the random variable $({\sf
state}_{0}^{*},p_{\mathcal{B}}^{*},p_{\mathcal{C}}^{*})\leftarrow
S^{\mathcal{A}}({\sf state}_{0})$, we have:

  1. 1.

$\operatorname*{\mathbb{E}}\left[p_{\mathcal{B}}^{*}p_{\mathcal{C}}^{*}\right]=p$

  2. 2.

$\mathcal{R}^{*}=(R^{\mathcal{A}},{\sf state}_{0}^{*})$ sampled in this
process is a distribution over efficient stateful non-local solvers that is
$(p_{B}^{*}p_{C}^{*},\eta)$-persistent.

Moreover, if $P$ does not have a verifiably polynomial image, the same holds,
but $S$ is not efficient.

###### Proof.

The proof will closely follow the proof of Theorem 4.1 in [BBK22]. Let
$P=(\mathsf{GenC},\mathsf{Ver},c)$ with polynomial-image verifier $K$ and
polynomial-image bound $k$. Let $\eta=1/\mathsf{poly}(\cdot)$. We will denote
by ${\bf B},{\bf C}$ the two registers for the non-local algorithms
$S,R,\mathcal{A}$. For $x\in\left\\{0,1\right\\}^{n}$, we define the
$(k+1)$-outcome projective measurement $\Pi^{\mathcal{B}}_{x}$ as follows:

  * •

Coherently run $\mathcal{B}$ with input $x$.

  * •

First, measure if the output of $\mathcal{B}$ is in the polynomial image
specified by $K$.

    * –

If not, output $\bot$

    * –

If yes, measure the output of $\mathcal{B}$ and output the answer
$y\in\left\\{0,1\right\\}^{m}$.

  * •

Uncompute.

We similarly define the projective measurement $\Pi^{\mathcal{C}}_{x}$. We
also define the wrapper non-local solver
$\widetilde{\mathcal{A}}=\widetilde{\mathcal{B}}\otimes\widetilde{\mathcal{C}}$,
where $\widetilde{\mathcal{B}}$ (resp., $\widetilde{\mathcal{C}}$) takes as
input $r\in\left\\{0,1\right\\}^{d}$, computes
$x=\mathsf{GenC}(1^{\lambda};r)$ and runs $\mathcal{B}$ (resp.,
${\mathcal{C}}$) on input $x$, outputting the result
$y\in\left\\{0,1\right\\}^{m}$. Next, we move on to describe $S^{\mathcal{A}}$
and $R^{\mathcal{A}}$ next.

##### Description of $S^{\mathcal{A}}$:

On input ${\sf state}_{0}$, compute $({\sf
state}_{0}^{*},p_{\mathcal{B}}^{*},p_{\mathcal{C}}^{*})\leftarrow\mathsf{NLValEst}_{\mathsf{Ver},\widetilde{\mathcal{A}}}({\sf
state}_{0},1^{10/\eta})$. That is, $S_{1}^{\mathcal{B}}$ runs
$\mathsf{ValEst}_{\mathsf{Ver},\widetilde{\mathcal{B}}}(\cdot,1^{20/\eta})$
and $S_{2}^{\mathcal{C}}$ runs
$\mathsf{ValEst}_{\mathsf{Ver},\widetilde{\mathcal{C}}}(\cdot,1^{20/\eta})$.
Output $({\sf state}_{0}^{*},p_{\mathcal{B}}^{*},p_{\mathcal{C}}^{*})$.

##### Description of $R^{\mathcal{A}}$:

On input $(1^{\lambda},1^{i},x_{\mathcal{B}},x_{\mathcal{C}},{\sf
state}_{i-1}^{*})$, where $R_{1}$ receives $1^{\lambda},1^{i},x_{\mathcal{B}}$
and the register ${\bf B}$ while $R_{2}$ receives
$1^{\lambda},1^{i},x_{\mathcal{C}}$ and ${\bf C}$, do the following:

  * •

Define $\varepsilon_{i}=\eta/32i^{2}$, so that $(\varepsilon_{i})_{i}$ is
monotonically decreasing and $\sum_{i=1}^{\infty}\varepsilon_{i}<\eta/16$.

  * •

Compute
$(\sigma_{i-1},q_{\mathcal{B}}^{i-1},q_{\mathcal{C}}^{i-1})\leftarrow\mathsf{NLValEst}_{\mathsf{Ver},\widetilde{\mathcal{A}}}({\sf
state}_{i-1}^{*},1^{1/\varepsilon_{i}})$.

  * •

Compute
$(y^{i}_{\mathcal{B}},y_{\mathcal{C}}^{i},\sigma_{i}^{*})\leftarrow(\Pi_{x_{\mathcal{B}}}^{\mathcal{B}}\otimes\Pi_{x_{\mathcal{C}}}^{\mathcal{C}})(\sigma_{i-1})$,
where
$y_{\mathcal{B}}^{i},y_{\mathcal{C}}^{i}\in\left\\{0,1\right\\}^{m}\cup\left\\{\bot\right\\}$
and $\sigma_{i}^{*}$ is the post-measurement state.

  * •

Compute
$\rho_{i}\leftarrow\mathsf{NLRepair}_{\mathsf{Ver},\widetilde{\mathcal{A}},\Pi^{\mathcal{B}}_{x_{\mathcal{B}}},\Pi^{\mathcal{C}}_{x_{\mathcal{C}}}}(\sigma_{i}^{*},y^{i}_{\mathcal{B}},q_{\mathcal{B}}^{i-1},y_{\mathcal{C}}^{i},q_{\mathcal{C}}^{i-1},1^{1/\varepsilon_{i},1^{k+1}})$.

  * •

Compute $({\sf
state}_{i}^{*},p^{i}_{\mathcal{B}},p_{\mathcal{C}}^{i})\leftarrow\mathsf{NLValEst}_{\mathsf{Ver},\widetilde{\mathcal{A}}}(\rho_{i},1^{1/\varepsilon_{i}})$.

  * •

Output $(y_{\mathcal{B}},y_{\mathcal{C}},{\sf state}_{i}^{*})$, where
$y_{\mathcal{B}}$, register ${\bf B}$ is $R_{1}$’s output while
$y_{\mathcal{C}}$, register ${\bf C}$ is $R_{2}$’s output.

Note that $R_{1}$ and $R_{2}$ are defined implicitly above given that every
step is a non-local algorithm; $R_{1}^{\mathcal{B}}$ performs the operations
on the ${\bf B}$ register, and $R_{2}^{\mathcal{C}}$ on the ${\bf C}$
register.

Consider a solver-aided non-local algorithm $\mathcal{S}^{\mathcal{R}^{*}}$
with input $z$, and the random variables sampled by the process below:

  * •

$(p_{\mathcal{B}}^{*},p_{\mathcal{C}}^{*},{\sf state}_{0}^{*})\leftarrow
S^{\mathcal{A}}({\sf state}_{0})$. Equivalently, $({\sf
state}_{0}^{*},p_{\mathcal{B}}^{*},p_{\mathcal{C}}^{*})\leftarrow\mathsf{NLValEst}_{\mathsf{Ver},\widetilde{\mathcal{A}}}({\sf
state}_{0},1^{2/\eta})$.

  * •

For $i\geq 1$, $(y^{i}_{\mathcal{B}},y_{\mathcal{C}}^{i},{\sf
state}_{i}^{*})\leftarrow
R^{\mathcal{A}}(1^{\lambda},1^{i},x_{\mathcal{B}}^{i},x_{\mathcal{C}}^{i},{\sf
state}_{i-1}^{*})$, where $(x_{\mathcal{B}}^{i},x_{\mathcal{C}}^{i})$ is the
$i$th pair of inputs chosen by $\mathcal{S}_{z}^{\mathcal{R}^{*}}$. In more
detail,

    * –

$(\sigma_{i-1},q_{\mathcal{B}}^{i-1},q_{\mathcal{C}}^{i-1})\leftarrow\mathsf{NLValEst}_{\mathsf{Ver},\widetilde{\mathcal{A}}}({\sf
state}_{i-1}^{*},1^{1/\varepsilon_{i}})$.

    * –

$(y^{i}_{\mathcal{B}},y_{\mathcal{C}}^{i},\sigma_{i}^{*})\leftarrow(\Pi_{x_{\mathcal{B}}^{i}}^{\mathcal{B}}\otimes\Pi_{x_{\mathcal{C}}^{i}}^{\mathcal{C}})(\sigma_{i-1})$.

    * –

$\rho_{i}\leftarrow\mathsf{NLRepair}_{\mathsf{Ver},\widetilde{\mathcal{A}},\Pi^{\mathcal{B}}_{x_{\mathcal{B}}^{i}},\Pi^{\mathcal{C}}_{x_{\mathcal{C}}^{i}}}(\sigma_{i}^{*},y^{i}_{\mathcal{B}},q_{\mathcal{B}}^{i-1},y_{\mathcal{C}}^{i},q_{\mathcal{C}}^{i-1},1^{1/\varepsilon_{i},1^{k+1}})$.

    * –

$({\sf
state}_{i}^{*},p^{i}_{\mathcal{B}},p_{\mathcal{C}}^{i})\leftarrow\mathsf{NLValEst}_{\mathsf{Ver},\widetilde{\mathcal{A}}}(\rho_{i},1^{1/\varepsilon_{i}})$.

Over the randomness of this process, we have the following identities:

$\displaystyle\operatorname*{\mathbb{E}}\left[p_{\mathcal{B}}^{*}p_{\mathcal{C}}^{*}\right]=p$
(7)
$\displaystyle\Pr\left[\left|p_{\mathcal{B}}^{*}-q_{\mathcal{B}}^{0}\right|\geq\eta/10\lor\left|p_{\mathcal{C}}^{*}-q_{\mathcal{C}}^{0}\right|\geq\eta/10\right]\leq\eta/10$
(8)
$\displaystyle\Pr\left[\left|p_{\mathcal{B}}^{i}-q_{\mathcal{B}}^{i}\right|\geq\varepsilon_{i}\lor\left|p_{\mathcal{C}}^{i}-q_{\mathcal{C}}^{i}\right|\geq\varepsilon_{i}\right]\leq\varepsilon_{i},\quad\forall
i\geq 1$ (9)
$\displaystyle\Pr\left[\left|q_{\mathcal{B}}^{i-1}-p_{\mathcal{B}}^{i}\right|\geq\varepsilon_{i}\lor\left|q_{\mathcal{C}}^{i-1}-p_{\mathcal{C}}^{i}\right|\geq\varepsilon_{i}\right]\leq\varepsilon_{i},\quad\forall
i\geq 1$ (10)
$\displaystyle\operatorname*{\mathbb{E}}\left[q_{\mathcal{B}}^{i-1}q_{\mathcal{C}}^{i-1}\right]=\mathsf{val}_{P}^{\widetilde{\mathcal{D}}}\left[i-1,\mathcal{S}_{z}^{\mathcal{R}^{*}}\right],\quad\forall
i\geq 1$ (11)
$\displaystyle\Pr\left[\left|p_{\mathcal{B}}^{i-1}p_{\mathcal{C}}^{i-1}-\mathsf{val}_{P}^{\widetilde{\mathcal{D}}}\left[i-1,\mathcal{S}_{z}^{\mathcal{R}^{*}}\right]\right|\geq\varepsilon_{i}\right]\leq\varepsilon_{i},\quad\forall
i\geq 1,\mathcal{S},z$ (12)

Equation 7 follows from the value estimation property in Lemma 19 and the fact
that $\widetilde{\mathcal{A}}$ is a wrapper solver for $\mathcal{A}$. This is
the first bullet we need to show to prove the theorem.

Moving on to the second bullet (persistence), eqs. 8 and 9 follow from the
almost-projective estimation property in Lemma 19 since
$\varepsilon\leq\eta/2$ and $\varepsilon_{i+1}\leq\varepsilon_{i}$. Equation
10 follows from the repairing property. Finally, eq. 12 follows from the value
estimation property and from the fact that323232Here we define
$\mathsf{Ver}(1^{\lambda},r,\bot)=0$ for convenience.
$\mathsf{val}_{P}^{\widetilde{\mathcal{D}}}\left[i-1,\mathcal{S}_{z}^{\mathcal{R}^{*}}\right]=\Pr\left[\mathsf{Ver}(1^{\lambda},r_{\mathcal{B}}^{i},y_{\mathcal{B}}^{i})=\mathsf{Ver}(1^{\lambda},r_{\mathcal{C}}^{i},y_{\mathcal{C}}^{i})=1\right]$.
The latter is true because $y_{\mathcal{B}}^{i}$ (resp.,
$y_{\mathcal{C}}^{i}$) is distributed the same as the output of $\mathcal{B}$
(resp., $\mathcal{C}$) conditioned on $y_{\mathcal{B}}^{i}\neq\bot$, and
otherwise the verification fails as expected.

Therefore, by union bound we have with probability at least
$1-\eta/10-\sum_{i=1}^{\infty}4\varepsilon_{i}\geq 1-\eta$ that

  1. 1.

$\left|p_{\mathcal{B}}^{*}-q_{\mathcal{B}}^{0}\right|\leq\eta/10$ and
$\left|p_{\mathcal{C}}^{*}-q_{\mathcal{C}}^{0}\right|\leq\eta/10$,

  2. 2.

$\left|p_{\mathcal{B}}^{i}-q_{\mathcal{B}}^{i}\right|\leq\varepsilon_{i}$ and
$\left|p_{\mathcal{C}}^{i}-q_{\mathcal{C}}^{i}\right|\leq\varepsilon_{i}$,

  3. 3.

$\left|p_{\mathcal{B}}^{i}-q_{\mathcal{B}}^{i-1}\right|\leq\varepsilon_{i}$
and
$\left|p_{\mathcal{C}}^{i}-q_{\mathcal{C}}^{i-1}\right|\leq\varepsilon_{i}$,

  4. 4.

$\operatorname*{\mathbb{E}}\left[q_{\mathcal{B}}^{i-1}q_{\mathcal{C}}^{i-1}\right]=\mathsf{val}_{P}^{\widetilde{\mathcal{D}}}\left[i-1,\mathcal{S}_{z}^{\mathcal{R}^{*}}\right]$

for all $i\geq 1$. Conditioned on the inequalities 1-4 above being true, we
will show that

$\displaystyle\left|p_{\mathcal{B}}^{*}p_{\mathcal{C}}^{*}-\mathsf{val}_{P}^{\widetilde{\mathcal{D}}}\left[i,\mathcal{S}_{z}^{\mathcal{R}^{*}}\right]\right|\leq\eta$
(13)

to finish the proof. Indeed, by triangle inequality we have that
$\left|p_{\mathcal{B}}^{*}-q_{\mathcal{B}}^{i}\right|\leq\eta/10+\sum_{j=1}^{i}2\varepsilon_{j}\leq\eta/3$,
and similarly
$\left|p_{\mathcal{C}}^{*}-q_{\mathcal{C}}^{i}\right|\leq\eta/3$. Since
$p_{\mathcal{B}}^{*},p_{\mathcal{C}}^{*}\in[0,1]$, this implies that
$\left|p_{\mathcal{B}}^{*}p_{\mathcal{C}}^{*}-q_{\mathcal{C}}^{i}q_{\mathcal{C}}^{i}\right|\leq
2(\eta/3)+(\eta/3)^{2}\leq\eta$. Taking the expectation, we obtain eq. 13.

If $P$ does not have a verifiably polynomial image, note that we can always
take $k=2^{n}$, i.e. $P$ always has a verifiably _exponential_ image. Thus,
the proof remains the same, except the runtime of $R$ now depends
exponentially on $n$.

∎

######  Remark 7.

We note that the transformation in Theorem 20 is not optimal in terms of
concrete efficiency. For instance, it is redundant to apply value estimation
once in $S$ and twice in $R$. The reason we do this is to use previous work as
closely to a black-box as possible, thus keeping the proof simple.

####  5.3.5 Non-Local Classical-to-Quantum Lifting Theorem

The remaining steps to reach our non-local lifting theorem (Theorem 22) are
essentially the same as those in [BBK22]. For this reason, we do not repeat
the detailed proofs here. Nonetheless, we note that the proof has the
following (informal) structure: given a $P$-solver,

  1. 1.

Obtain a persistent $P$-solver.

  2. 2.

Next, obtain a memoryless $P$-solver, i.e. one that only remembers the number
of times it has interacted with the assumption.

  3. 3.

Next, obtain a stateless solver.

Step 1 corresponds to Theorem 20, whereas steps 2,3 can be summarized below:

######  Theorem 21.

There exists an efficient non-local quantum algorithm
$\mathsf{Sim}=\mathsf{Sim}_{1}\otimes\mathsf{Sim}_{2}$ with the following
properties. Let $\mathcal{A}=(\mathcal{B},\mathcal{C},{\sf state}_{0})$ be a
$(p,\eta)$-persistent $(\ell,\ell_{\mathcal{B}},\ell_{\mathcal{C}})$-stateful
non-local independent-challenge $P$-solver for a falsifiable non-interactive
assumption $P$. Let $\vec{x}_{\mathcal{B}}$ and $\vec{x}_{\mathcal{C}}$ each
be (independently) sampled from an efficiently samplable distribution over
$k$-tuples of $P$-instances and define
$\vec{x}:=(\vec{x}_{\mathcal{B}},\vec{x}_{\mathcal{C}})$. Then, there exists a
$(p,\eta)$-persistent distribution
$\left\\{\mathcal{A}^{\alpha}=(\mathcal{B}^{\alpha},\mathcal{C}^{\alpha})\right\\}_{\alpha}$
over stateless solvers such that

$\mathsf{Sim}^{\mathcal{A}}(1^{\lambda},1^{\ell},1^{1/\delta},\vec{x}^{*})=\mathsf{Sim}_{1}^{\mathcal{B}}(1^{\lambda},1^{\ell_{\mathcal{B}}},1^{1/\delta},\vec{x_{\mathcal{B}}}^{*})\otimes\mathsf{Sim}_{2}^{\mathcal{C}}(1^{\lambda},1^{\ell_{\mathcal{C}}},1^{1/\delta},\vec{x_{\mathcal{C}}}^{*})$

makes non-adaptive black-box queries to $\mathcal{B}$ and $\mathcal{C}$ and
produces a distribution within $\delta$ statistical distance from
$\mathcal{A}^{\alpha}(1^{\lambda},\vec{x})$.

###### Proof (sketch).

Follows from Corollary 6.2 in [BBK22] after making the observation that the
simulators in Theorem 5.1 and Theorem 6.1 both preserve non-locality, i.e.
they are non-local simulators if given as input non-local solvers. ∎

The theorem below is a direct consequence of Theorems 20 and 21 as per Theorem
7.1 of [BBK22]. We refer the reader to [BBK22] for the proof.

######  Theorem 22 (Non-Local Classical-to-Quantum Lifting).

Let $P=(\mathsf{GenC}_{P},\mathsf{Ver}_{P},c_{P})$ and
$Q=(\mathsf{GenC}_{Q},\mathsf{Ver}_{Q},c_{Q})$ be non-interactive assumptions.
Assume there exists a non-adaptive non-local classical black-box
$(\widetilde{\mathcal{D}}_{P},c_{P},\widetilde{\mathcal{D}}_{Q},c_{Q})$-reduction
from solving $Q$ to solving $P$, where
$\widetilde{\mathcal{D}}_{P}=\mathcal{U}_{\left\\{0,1\right\\}^{d_{P}}\times\left\\{0,1\right\\}^{d_{P}}}$
is the uniform extension. Then, there exists an inefficient non-local quantum
$(\widetilde{\mathcal{D}}_{P},c_{P},\widetilde{\mathcal{D}}_{Q},c_{Q})$-reduction
from solving $Q$ to solving $P$. If $P$ has verifiably polynomial image, then
the reduction is efficient.

###  5.4 Applications

In this section, we present two applications of our main theorem (Theorems 13
and 14). The first one is information theoretic single-decryptor encryption
for one-bit messages, which relies on simultaneous quantum Goldreich-Levin
extraction. The second application involves the effect of changing the
challenge distribution in a cloning game to unclonable security. Informally,
we show that independent-challenge unclonable security implies unclonable
security for correlated distributions for primitives which have negligible
trivial success probability.

####  5.4.1 Single-Decryptor Encryption

In this section, we analyze a corollary of Theorem 14, which is Simultaneous
Quantum Goldreich-Levin Lemma. Then, we show a construction of information
theoretic single-decryptor encryption as a corollary.

######  Definition 33 (Simultaneous Extraction).

We say that an adversary $\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$
can _simultaneously extract_ a classical function $f(k,x,r)$ given a quantum
token $\rho_{k,x}$ using key $k=(k_{B},k_{C})$ with probability $\delta$ if
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ succeeds in the following
experiment with probability $\delta$:

  * •

In phase 1, the challenger sends $\rho_{k,x}$ to $\mathcal{A}$, who applies a
CPTP map to split the state into two registers $\mathcal{B}$ and
$\mathcal{C}$.

  * •

In phase 2, $\mathcal{B}$ and $\mathcal{C}$ can no longer communicate. The
challenger samples independent random coins
$(r,r^{\prime})\xleftarrow{\$}\mathcal{R}\times\mathcal{R}$, then sends
$(r,k_{B})$ to $\mathcal{B}$ and $(r^{\prime},k_{C})$ to $\mathcal{C}$. Later,
$\mathcal{B}$ outputs a string $z_{B}$ and $\mathcal{C}$ outputs a string
$z_{C}$.

  * •

The adversary wins if $z_{B}=f(k,x,r)$ and $z_{C}=f(k,x,r^{\prime})$.

It is understood that $x$ above is a random variable.

######  Lemma 23 (Simultaneous Quantum Goldreich-Levin).

Suppose that $\mathcal{R}=\left\\{0,1\right\\}^{n}$ and there exists a
(possibly inefficient) adversary
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ which can simultaneously
extract $\langle r,x\rangle$ from a quantum token $\rho_{k,x}$ using key $k$,
with probability $1/2+\varepsilon$ for a non-negligible function
$\varepsilon$. Then, there exists an adversary
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$
which can simultaneously extract333333We note that the values $(r,r^{\prime})$
can be ignored when extracting $x$. $x$ given the same token $\rho_{k,x}$
using key $k$ with non-negligible probability $\varepsilon^{\prime}$.

###### Proof.

We will interpret the key
$k=(k_{B},k_{C})=:(\mathsf{ch}_{\mathcal{B}},\mathsf{ch}_{\mathcal{C}})$ as
the challenge and $x=:m$ as the message in a cloning game. We will assume here
that $k_{B},k_{C}$ are independently distributed, which is sufficient for the
application to single-decryptor encryption. See Appendix A for a direct
proof343434The direct proof also shows that if the simultaneous extractor for
$\langle r,x\rangle$ is efficient, then so is the simultaneous extractor for
$x$. of Lemma 23 which covers the general case. Let
$\mathcal{G}^{\prime}=(\mathsf{Setup},\mathsf{GenT},\mathsf{GenC}^{\prime},\mathsf{Ver}^{\prime})$
be a (stateful) cloning game, such that:

  * •

$\rho_{k,x}$ is the token received by $\mathcal{A}$, $x$ is the message, and
$k$ is the challenge received by $\mathcal{B}$ and $\mathcal{C}$.

  * •

$\mathsf{Ver}^{\prime}(\mathsf{sk},x,\mathsf{ch},\mathsf{ans})$ accepts if and
only if $\mathsf{ans}=x$, i.e. $\mathcal{G}$ is a search game.

Now define a new cloning game
$\mathcal{G}=(\mathsf{Setup},\mathsf{GenT},\mathsf{GenC},\mathsf{Ver})$,
where:

  * •

$\mathsf{GenC}(\mathsf{sk},x)$ computes
$\mathsf{ch}\leftarrow\mathsf{GenC}(\mathsf{sk},x)$ and samples
$r\leftarrow\mathcal{U}_{\mathcal{R}}$. It outputs $(r,\mathsf{ch})$.

  * •

$\mathsf{Ver}(\mathsf{sk},x,(r,\mathsf{ch}),\mathsf{ans})$ accepts if and only
if $\mathsf{ans}=\langle r,x\rangle$.

Suppose that the distribution of $x$, denoted by $\mathcal{D}_{\mathcal{M}}$,
is non-trivial in the sense that
$p^{\mathsf{triv}}(\mathcal{G},\mathcal{D}_{\mathcal{M}})\leq
1/2+\mathsf{negl}(\lambda)$ and $\mathcal{G}^{\prime}$ is
$\mathcal{D}_{\mathcal{M}}$-evasive, for otherwise the proof is trivial.

We will use the contrapositive of Theorem 14, with and
$\widetilde{\mathsf{GenC}}=\mathsf{GenC}_{\mathsf{ind}}$. Now if
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ exists, then $\mathcal{G}$
does not have information theoretic
$(\mathcal{D}_{\mathcal{M}},\mathsf{negl})$ independent-challenge unclonable
security, where $\mathcal{M}=\left\\{0,1\right\\}^{n}$ is the message space
and $\mathcal{D}_{\mathcal{M}}$ denotes the distribution of $x$. Now we
observe that the conditions of Theorem 14, i.e. conditions in items (1), (2)
and (3) and item (b) of Theorem 13, are all satisfied. Indeed, items (1), (2)
and (3) are satisfied by assumption. Item (b) follows from the well-known
classical local Goldreich-Levin extraction353535Note that even though the
success probability of the extractor may depend on $x$, its description does
not. [GL89]. Therefore, it follows that $\mathcal{G}$ does not have
$(\mathcal{D}_{\mathcal{M}},\mathsf{negl})$ information theoretic independent-
challenge unclonable security, meaning there exists
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$
which can simultaneously extract $x$ with non-negligible probability as
desired.

∎

##### Search to Decision Transformation.

######  Corollary 4 (Search to Decision).

Let $\mathcal{G}=(\mathsf{Setup},\mathsf{GenT},\mathsf{GenC},\mathsf{Ver})$ be
a cloning search game with extension $\widetilde{\mathsf{GenC}}$ such that (1)
$\mathsf{GenC}(\mathsf{sk},m)$ and $\widetilde{\mathsf{GenC}}(\mathsf{sk},m)$
both do not depend on $m$, (2) $\mathcal{G}$ has statistical correctness, and
(3) $\mathcal{G}$ has $(\mathcal{D},\varepsilon,\widetilde{\mathsf{GenC}})$
unclonable security. Define a (stateful) cloning decision game
$\mathcal{G}^{\prime}=(\mathsf{Setup}^{\prime},\mathsf{GenT}^{\prime},\mathsf{GenC}^{\prime},\mathsf{Ver}^{\prime})$
as follows:

  * •

There is no message, i.e. $\mathcal{M}^{\prime}=\left\\{\bot\right\\}$ is the
message space.

  * •

$\mathsf{Setup}^{\prime}(1^{\lambda})$ computes
$\mathsf{sk}\leftarrow\mathsf{Setup}(1^{\lambda})$.
$\mathsf{sk}^{\prime}=\mathsf{sk}$.

  * •

$\mathsf{GenT}^{\prime}(\mathsf{sk}^{\prime},m^{\prime})$ parses the input as
$\mathsf{sk}^{\prime}=\mathsf{sk}$, samples $m\leftarrow\mathcal{D}$, and
computes $\rho\leftarrow\mathsf{GenT}(\mathsf{sk},m)$. It outputs a token
$\rho$ and random coins $r_{\mathsf{GenT}^{\prime}}=m$

  * •

$\mathsf{GenC}^{\prime}(\mathsf{sk}^{\prime},m^{\prime};r_{\mathsf{GenC}^{\prime}})$
parses the input as $\mathsf{sk}^{\prime}=\mathsf{sk}$. It interprets the
random coins as $r_{\mathsf{GenC}^{\prime}}=(r,b,r_{\mathsf{GenC}})$, where
$r\in\mathcal{M}$, $b\in\left\\{0,1\right\\}$, and $r_{\mathsf{GenC}}$ is
randomness for $\mathsf{GenC}$. Then it computes
$\mathsf{ch}\leftarrow\mathsf{GenC}(\mathsf{sk},m;r_{\mathsf{GenC}})$, and
outputs $\mathsf{ch}^{\prime}=(r,\langle r,m\rangle\oplus b,\mathsf{ch})$.

  * •

$\mathsf{Ver}^{\prime}(\mathsf{sk}^{\prime},m^{\prime},\mathsf{ch}^{\prime},\mathsf{ans}^{\prime},r_{\mathsf{GenC}^{\prime}})$
parses the input as $r_{\mathsf{GenC}^{\prime}}=(r,b,r_{\mathsf{GenC}})$ and
outputs $b^{\prime}=[\mathsf{ans}^{\prime}==b]$.

Then, $\mathcal{G}^{\prime}$ has statistical correctness and
$(\mathcal{D}_{\bot},\sqrt{\varepsilon}/2,\widetilde{\mathsf{GenC}}^{\prime})$
independent-challenge unclonable security, where the extension
$\widetilde{\mathsf{GenC}}^{\prime}(\mathsf{sk},m^{\prime})$ is defined as
follows:

  1. 1.

Run $(r_{B},r_{C})\leftarrow\mathsf{GenC}(\mathsf{sk},m)$

  2. 2.

Sample $r_{B}^{\prime},r_{C}^{\prime}\xleftarrow{\$}\mathcal{M}$ and
$b_{B},b_{C}\xleftarrow{\$}\left\\{0,1\right\\}$

  3. 3.

Output
$\left((r_{B}^{\prime},b_{B},r_{B}),(r_{C}^{\prime},b_{C},r_{C})\right)$.

In particular, if $\mathcal{G}$ has $(\mathcal{D},\varepsilon)$ independent-
challenge unclonable security, then $\mathcal{G}^{\prime}$ has
$(\mathcal{D}_{\bot},\sqrt{\varepsilon}/2)$ independent-challenge unclonable
security.

###### Proof.

We construct the game
$\mathcal{G}^{\prime}=(\mathsf{Setup}^{\prime},\mathsf{GenT}^{\prime},\mathsf{GenC}^{\prime},\mathsf{Ver}^{\prime})$
as follows:

We define several hybrids:

  * •

Hybrid 0: This is the cloning experiment
$\mathfrak{CE}^{\widetilde{\mathsf{GenC}}^{\prime}}_{\mathcal{G}^{\prime},\mathcal{D}_{\bot}}$.
Since $\mathcal{G}^{\prime}$ is a decision game, we have
$p^{\mathsf{triv}}(\mathcal{G}^{\prime},\mathcal{D}^{\prime},\widetilde{\mathsf{GenC}}^{\prime})\geq
1/2$. Assume for the sake of contradiction that the statement is false, then
there exists a cloning adversary
$\left(\mathcal{A}_{0},\mathcal{B}_{0},\mathcal{C}_{0}\right)$ that succeeds
in this experiment with probability $p>\frac{1}{2}+\sqrt{\varepsilon}/2$.

  * •

Hybrid 1: In this hybrid, we modify the success condition for the adversary.
Instead of outputting the bits $b_{B}$ and $b_{C}$, $\mathcal{B}$ and
$\mathcal{C}$ are now required to output $\langle r,m\rangle$ and $\langle
r^{\prime},m\rangle$, respectively, where $(r,r^{\prime})$ are the random
coins generated for $\mathsf{ch}_{\mathcal{B}}^{\prime}$ and
$\mathsf{ch}_{\mathcal{C}}^{\prime}$, respectively. This hybrid is clearly
equivalent to Hybrid 0, since $\langle r,m\rangle\oplus b_{B}$ and $\langle
r^{\prime},m\rangle\oplus b_{C}$ are known to $\mathcal{B}$ and $\mathcal{C}$,
respectively. Thus, there exists
$\left(\mathcal{A}_{1},\mathcal{B}_{1},\mathcal{C}_{1}\right)$ which succeeds
in this hybrid with probability $p$. Specifically, $\mathcal{B}_{1}$ and
$\mathcal{C}_{1}$ simply run $\mathcal{B}_{0}$ and $\mathcal{C}_{0}$; then
they XOR the output with the value mentioned above.

  * •

Hybrid 2: In this hybrid, we truncate the challenges given to
$\mathcal{B}^{\prime}$ and $\mathcal{C}^{\prime}$. Specifically, instead of
getting $\mathsf{ch}_{\mathcal{B}}^{\prime}=(r,\langle r,m\rangle\oplus
b_{B},\mathsf{ch}_{\mathcal{B}})$, $\mathcal{B}$ will receive
$(r,\mathsf{ch}_{\mathcal{B}})$; similarly $\mathcal{C}$ will receive
$(r^{\prime},\mathsf{ch}_{\mathcal{C}})$. This hybrid is equivalent to Hybrid
1, so there exists an adversary
$\left(\mathcal{A}_{2},\mathcal{B}_{2},\mathcal{C}_{2}\right)$ which succeeds
in this hybrid with probability $p$. The reason is that $b_{B},b_{C}$ are
uniformly random bits that information theoretically hide the inner products
$\langle r,m\rangle$ and $\langle r^{\prime},m\rangle$. In more detail,
$\left(\mathcal{A}_{2},\mathcal{B}_{2},\mathcal{C}_{2}\right)$ can be
constructed as follows:

    * –

Upon receiving a token $\rho$, $\mathcal{A}_{2}$ runs
$\rho_{BC}\leftarrow\mathcal{A}_{1}$ and samples random bits
$b_{B}^{\prime},b_{C}^{\prime}\xleftarrow{\$}\left\\{0,1\right\\}$. Then it
sends the bipartite state
$\rho_{BC}\otimes\ket{b_{B}^{\prime}}\\!\\!\bra{b_{B}^{\prime}}_{B}\otimes\ket{b_{C}}\\!\\!\bra{b_{C}}_{C}$
to $\mathcal{B}_{2}$ and $\mathcal{C}_{2}$.

    * –

$\mathcal{B}_{2}$, upon receiving $(r,\mathsf{ch}_{\mathcal{B}})$ from the
challenger and a state
$\rho_{B}\otimes\ket{b_{B}^{\prime}}\\!\\!\bra{b_{B}^{\prime}}_{B}$ from
$\mathcal{A}_{2}$, runs $\mathcal{B}_{1}$ with input
$(r,b_{B}^{\prime},\mathsf{ch}_{\mathcal{B}})$. $\mathcal{C}_{2}$ is defined
similarly.

Since the view of
$\left(\mathcal{A}_{1},\mathcal{B}_{1},\mathcal{C}_{1}\right)$ exactly matches
Hybrid 1, we conclude that
$\left(\mathcal{A}_{2},\mathcal{B}_{2},\mathcal{C}_{2}\right)$ succeeds in
Hybrid 2 with probability $p>\frac{1}{2}+\sqrt{\varepsilon}/2$.

By Lemma 23, this implies that there exists a cloning adversary
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$
which succeeds in
$\mathfrak{CE}_{\mathcal{G},\mathcal{D}}^{\widetilde{\mathsf{GenC}}}$ with
probability greater than $4(\sqrt{\varepsilon}/2)^{2}=\varepsilon$, a
contradiction.

∎

By plugging in $\mathcal{G}=\mathcal{G}_{\mathsf{BB84}}$ from Definition 21,
we get the following corollary:

######  Corollary 5.

There exists a single-decryptor encryption scheme in the plain model with
information-theoretic independent-challenge security.

###### Proof.

It could easily be checked that the resulting game $\mathcal{G}^{\prime}$ is
the cloning game corresponding to the following single-decryptor encryption
scheme $(\mathsf{Gen},\mathsf{GenT},\mathsf{Enc},\mathsf{Dec})$:

  1. 1.

$(\mathsf{Gen}(1^{\lambda}))$: Sample
$m,\theta\xleftarrow{\$}\left\\{0,1\right\\}^{\lambda}$. Output
$\mathsf{sk}=(m,\theta)$

  2. 2.

$\mathsf{GenT}(\mathsf{sk})$: Parse the input as $\mathsf{sk}=(m,\theta)$ and
output the decryption token $\ket{m^{\theta}}\\!\\!\bra{m^{\theta}}$.

  3. 3.

$\mathsf{Enc}(\mathsf{sk},b)$: Sample
$r\xleftarrow{\$}\left\\{0,1\right\\}^{\lambda}$. Output $ct=(r,\langle
r,m\rangle\oplus b,\theta)$

  4. 4.

$\mathsf{Dec}(\rho,ct)$: Parse $ct=(r,b^{\prime},\theta)$. Measure $\rho$ in
basis $H^{\theta}$ to get $m$. Output $\langle r,m\rangle\oplus b^{\prime}$.

Note that since $\mathcal{G}_{\mathsf{BB84}}$ is a cloning encryption game, it
is secure against any extension, including the independent-challenge case.
Therefore, the single-decryptor scheme above is optimally secure against
independent challenges by Corollary 4.

∎

####  5.4.2 Relationship Between Challenge Distributions

As a second application, we show that when the trivial success probability of
a cloning game is negligible, unclonable security for independent challenges
implies unclonable security for any challenge distribution, up to a polynomial
loss in the success probability.

######  Corollary 6.

Let $\mathcal{G}=(\mathsf{Setup},\mathsf{GenT},\mathsf{GenC},\mathsf{Ver})$ be
a $\mathcal{D}$-evasive cloning game with $(\mathcal{D},\mathsf{negl})$
independent-challenge unclonable security. Suppose that for any key-message
pair $(\mathsf{sk},m)$, the non-interactive assumption induced by
$(\mathcal{G},\mathcal{D},\mathsf{sk},m)$ has verifiably polynomial image.
Then, $\mathcal{G}$ has
$(\mathcal{D},\mathsf{negl},\widetilde{\mathsf{GenC}})$ unclonable security
for any extension $\widetilde{\mathsf{GenC}}$. In particular, $\mathcal{G}$
has $(\mathcal{D},\mathsf{negl})$ identical-challenge unclonable security.

###### Proof.

Follows directly from Theorem 13 by setting
$\mathcal{G}=\mathcal{G}^{\prime}$. The only non-trivial condition is (b),
which follows by Corollary 3. Note that the classical reduction is the
identity reduction, hence it does not depend on $(\mathsf{sk},m)$. ∎

######  Remark 8.

The corollary above can be applied to any unclonable primitive with verifiably
polynomial image, where $p^{\mathsf{triv}}$ is negligible, including copy-
protection for functions with output-length $\omega(\log\lambda)$.

##### Direct Proof with Concrete Bounds.

We can in fact show a stronger statement without using the main theorem,
namely that the identity reduction works in Corollary 6 with a cubic loss in
success probability.

###### Alternate proof of Corollary 6.

Follows directly from Lemma 18 after setting $\mathcal{D}$ in the lemma
statement to be the output of $\mathsf{GenC}^{\prime}$, setting
$\widetilde{\mathcal{D}}$ to be the output of the extension
$\widetilde{\mathsf{GenC}}$, and setting $B_{r}$ ($C_{r}$) to be a POVM
element which tests whether $\mathcal{B}$ ($\mathcal{C}$) passes the
verification $\mathsf{Ver}$ on challenge $r$. ∎

##  6 Relating Unclonable-Search and Unclonable-Indistinguishability

In this section, we will give a relationship between games satisfying
unclonable-indistinguishability security Definition 11 and unclonable-search
security Definition 10.

In Section 6.1, we show that games with unclonable-search property imply games
satisfying unclonable-indistinguishability property. In Section 6.2, we show
that games with unclonable-indistinguishability property imply games
satisfying unclonable-search property.

We start with some simple observations before moving onto our results.

##### Trivial Success.

We show upper and lower bounds for trivial success probability of search
games.

######  Lemma 24 (Trivial Success Probability of Search Games).

Let $\mathcal{G}=(\mathsf{Setup},\mathsf{GenT},\mathsf{GenC},\mathsf{Ver})$ be
a cloning search game with correctness $\delta$ and let
$\widetilde{\mathsf{GenC}}$ be an extension. Then,

$\displaystyle(1-\sqrt{1-\delta})\left(\mathsf{OPT}(m\mid\mathsf{ch})-\sqrt{1-\delta}\right)\leq
p^{\mathsf{triv}}(\mathcal{G},\mathcal{D},\widetilde{\mathsf{GenC}})\leq\mathsf{OPT}(m\mid\mathsf{ch}).$

where the variables $(m,\mathsf{ch})$ are sampled as in Definition 2.

###### Proof Sketch.

Consider a $\mathcal{B}$-trivial attack. For the upper-bound, simply bound the
success probability of $\mathcal{B}$. For the lower bound, note that for
$(1-\sqrt{1-\sigma})$ fraction of the time, $\mathcal{C}$ will succeed with
probability at least $1-\sqrt{1-\sigma}$ by correctness. Observe that
$\mathcal{B}$ can succeed with probability
$\mathsf{OPT}(m\mid\mathsf{ch}_{\mathcal{B}},\mathsf{aux})$ without the token.
Use union bound to complete the proof. Similar for the $\mathcal{C}$-trivial
attack. ∎

######  Corollary 7.

If $\mathcal{G}$ is a search game with perfect correctness, then
$p^{\mathsf{triv}}(\mathcal{G},\mathcal{D},\widetilde{\mathsf{GenC}})=\mathsf{OPT}(m\mid\mathsf{ch})$.

##### Message Hiding.

Clearly, a search game must have the property that the token hides the
message, for otherwise cloning would be trivial. We formalize this in the
lemma below.

######  Lemma 25 (Message Hiding).

Let $\mathcal{G}=(\mathsf{Setup},\mathsf{GenT},\mathsf{GenC},\mathsf{Ver})$ be
a cloning search game with $(\mathcal{D},\varepsilon)$ unclonable security,
then for any QPT adversary $\mathcal{A}$ we have

$\displaystyle\Pr\left[m\leftarrow\mathcal{A}(1^{\lambda},\rho)\;:\;\begin{subarray}{c}\mathsf{sk}\leftarrow\mathsf{Setup}(1^{\lambda})\\\
m\leftarrow\mathcal{D}\\\
\rho\leftarrow\mathsf{GenT}(\mathsf{sk},m)\end{subarray}\right]\leq
p^{\mathsf{triv}}(\mathcal{D},\varepsilon)+\varepsilon(\lambda)$

###### Proof.

If the statement is false, then $\mathcal{A}$ can send $m$ to $\mathcal{B}$
and $\mathcal{C}$ in the splitting phase, both of which output $m$ as their
answer, hence $\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ breaks the
$(\mathcal{D},\varepsilon)$ unclonable security of $\mathcal{G}$. ∎

###  6.1 Search-to-Indistinguishability

We transform games satisfying unclonable-search property to games satisfying
unclonable-indistinguishability property in the following steps.

  1. 1.

In Section 6.1.1, we present a generic transformation that reduces the
unclonable-search security of cloning games, where the message distribution
comes from a high entropy distribution, to unclonable-search security, where
the message distribution is uniform.

  2. 2.

In Section 6.1.2, we consider a new notion of security called augmented
unclonable security. In this security notion, all the adversaries have oracle
access to a point function $P_{m}(\cdot)$, where $m$ is such that the
adversary receives a token generated using $m$. We show that we can
generically transform any game satisfying unclonable-search security into one
satisfying augmented unclonable-search security.

  3. 3.

In Section 6.1.3, we show how augmented unclonable security implies
unclonable-indistinguishability security.

####  6.1.1 Relationship Between Message Distributions

The following lemma is adapted from Theorem 9 in [BL20].

######  Lemma 26.

Let $\mathcal{G}=(\mathsf{Setup},\mathsf{GenT},\mathsf{GenC},\mathsf{Ver})$ be
a cloning game. Let $\mathcal{D}$ be a distribution over the message space
$\mathcal{M}$ with min-entropy $h$, then for any cloning adversary
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ and any extension
$\widetilde{\mathsf{GenC}}$ of $\mathsf{GenC}$, we have

$\displaystyle\Pr\left[1\leftarrow\mathfrak{CE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{D}}(1^{\lambda},\left(\mathcal{A},\mathcal{B},\mathcal{C}\right))\right]\leq
2^{\log_{2}|\mathcal{M}|-h}\cdot\Pr\left[1\leftarrow\mathfrak{CE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{U}_{\mathcal{M}}}(1^{\lambda},\left(\mathcal{A},\mathcal{B},\mathcal{C}\right))\right].$

###### Proof.

$\displaystyle\Pr\left[1\leftarrow\mathfrak{CE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{D}}(1^{\lambda},\left(\mathcal{A},\mathcal{B},\mathcal{C}\right))\right]$
$\displaystyle=\sum_{m\in\mathcal{M}}\Pr\left[m\leftarrow\mathcal{D}\right]\cdot\Pr\left[1\leftarrow\mathfrak{CE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{D}}(1^{\lambda},\left(\mathcal{A},\mathcal{B},\mathcal{C}\right))\mid
m\right]$
$\displaystyle\leq\sum_{m\in\mathcal{M}}2^{-h}\cdot\Pr\left[1\leftarrow\mathfrak{CE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{D}}(1^{\lambda},\left(\mathcal{A},\mathcal{B},\mathcal{C}\right))\mid
m\right]$
$\displaystyle=2^{\log_{2}|\mathcal{M}|-h}\sum_{m\in\mathcal{M}}\frac{1}{|\mathcal{M}|}\cdot\Pr\left[1\leftarrow\mathfrak{CE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{U}_{\mathcal{M}}}(1^{\lambda},\left(\mathcal{A},\mathcal{B},\mathcal{C}\right))\mid
m\right]$
$\displaystyle=2^{\log_{2}|\mathcal{M}|-h}\cdot\Pr\left[1\leftarrow\mathfrak{CE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{U}_{\mathcal{M}}}(1^{\lambda},\left(\mathcal{A},\mathcal{B},\mathcal{C}\right))\right]$

∎

####  6.1.2 Generically Augmenting Security

######  Definition 34 (Augmented Unclonable Security).

Let $\mathcal{G}$ be a cloning search game and $\mathcal{D}$ be a distribution
over the message space $\mathcal{M}$. Let
$\mathfrak{ACE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{D}}$ be the
following _augmented cloning experiment_ , with the modification highlighted
in blue:

  * •

Setup Phase:

    * –

All parties get a security parameter $1^{\lambda}$ as input.

    * –

$\mathsf{Ref}$ samples a message $m\leftarrow\mathcal{D}$.

    * –

$\mathsf{Ref}$ computes $\mathsf{sk}\leftarrow\mathsf{Setup}(1^{\lambda})$ and
$\rho\leftarrow\mathsf{GenT}(\mathsf{sk},m)$.

    * –

$\mathcal{R}$ sends $\rho$ to $\mathcal{A}$.

    * –

$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ all get oracle access to
the point function $P_{m}(\cdot)$.

  * •

Splitting Phase:

    * –

$\mathcal{A}$ computes a bipartite state $\rho^{\prime}$ over registers $B,C$.

    * –

$\mathcal{A}$ sends $\rho^{\prime}[B]$ to $\mathcal{B}$ and $\rho^{\prime}[C]$
to $\mathcal{C}$.

  * •

Challenge Phase:

    * –

$\mathsf{Ref}$ samples
$(r_{\mathcal{B}},r_{\mathcal{C}})\leftarrow\widetilde{\mathsf{GenC}}(\mathsf{sk},m)$
and computes
$\mathsf{ch}_{\mathcal{B}}=\widetilde{\mathsf{GenC}}(\mathsf{sk},m;r_{\mathcal{B}}),\mathsf{ch}_{\mathcal{C}}=\widetilde{\mathsf{GenC}}(\mathsf{sk},m;r_{\mathcal{C}})$

    * –

$\mathsf{Ref}$ sends $\mathsf{ch}_{\mathcal{B}}$ to $\mathcal{B}$ and
$\mathsf{ch}_{\mathcal{C}}$ to $\mathcal{C}$.

    * –

$\mathsf{Ref}$ sends $\mathsf{ch}_{\mathcal{B}}$ to $\mathcal{B}$ and
$\mathsf{ch}_{\mathcal{C}}$ to $\mathcal{C}$.

    * –

$\mathcal{B}$ and $\mathcal{C}$ send back answers $\mathsf{ans}_{\mathcal{B}}$
and $\mathsf{ans}_{\mathcal{C}}$, respectively.

    * –

$\mathsf{Ref}$ computes bits
$b_{\mathcal{B}}\leftarrow\mathsf{Ver}(\mathsf{sk},m,\mathsf{ch}_{\mathcal{B}},\mathsf{ans}_{\mathcal{B}})$
and
$b_{\mathcal{C}}\leftarrow\mathsf{Ver}(\mathsf{sk},m,\mathsf{ch}_{\mathcal{C}},\mathsf{ans}_{\mathcal{C}})$.

    * –

The outcome of the game is denoted by
$\mathfrak{ACE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{D}}(1^{\lambda},\left(\mathcal{A},\mathcal{B},\mathcal{C}\right))$,
which equals 1 if $b_{\mathcal{B}}=b_{\mathcal{C}}=1$, indicating that the
adversary has won, and 0 otherwise, indicating that the adversary has lost.

Note that
$\mathfrak{ACE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{D}}$ defined
the same as
$\mathfrak{CE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{D}}$, but
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ additionally get oracle
access to $P_{m}(\cdot)$. We say that $\mathcal{G}$ has
_$(\mathcal{D},\varepsilon,\widetilde{\mathsf{GenC}})$ augmented unclonable
security_ if for all QPT cloning adversaries
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ we have

$\displaystyle\Pr\left[1\leftarrow\mathfrak{ACE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{D}}(1^{\lambda},\left(\mathcal{A},\mathcal{B},\mathcal{C}\right))\right]\leq
p^{\mathsf{triv}}(\mathcal{G},\mathcal{D},\widetilde{\mathsf{GenC}})+\varepsilon(\lambda).$

######  Lemma 27.

Let $\mathcal{G}=(\mathsf{Setup},\mathsf{GenT},\mathsf{GenC},\mathsf{Ver})$ be
a cloning search game with message space $\mathcal{M}$ such that
$p^{\mathsf{triv}}(\mathcal{G},\mathcal{U}_{\mathcal{M}})$ is negligible. If
$\mathcal{G}$ has $(\mathcal{U}_{\mathcal{M}},|\mathcal{M}|^{-\delta})$
unclonable search security for some $\delta>0$, then $\mathcal{G}$ has
$(\mathcal{U}_{\mathcal{M}},\mathsf{negl})$ augmented unclonable security.

###### Proof.

We will define a sequence of hybrids:

##### Hybrid 1:

This is the original augmented cloning experiment
$\mathfrak{ACE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{D}}$.
Suppose for the sake of contradiction that there exists a QPT adversary
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ which succeeds with non-
negligible probability $p$.

##### Hybrid 2:

In this hybrid, we replace the oracles $P_{m}(\cdot)$ with $P_{S}(\cdot)$,
where $S\subset\mathcal{M}$ is a random subset containing $m$ of size
$|\mathcal{M}|^{1-\delta/2}$. The fact that
$p^{\mathsf{triv}}(\mathcal{G},\mathcal{U}_{\mathcal{M}})$ is negligible
implies that $\frac{1}{|\mathcal{M}|}$ is negligible, hence
$\frac{|S|}{|\mathcal{M}|}=\frac{1}{|\mathcal{M}|^{\delta/2}}$ is also
negligible. We claim that $\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$
succeeds in this hybrid with probability at least $p-\mathsf{negl}(\lambda)$.

Suppose not, we will construct an adversary $\mathcal{A}^{\prime}$ which will
violate Corollary 2:

  * •

$\mathcal{A}^{\prime}$ picks $m\leftarrow\mathcal{U}_{\mathcal{M}}$ and
receives oracle access to $\mathcal{O}$, where either $\mathcal{O}=P_{m}$ or
$\mathcal{O}=P_{S}$ for a random subset $S\subset\mathcal{M}$ of size
$|\mathcal{M}|^{1-\delta/2}$ containing $m$.

  * •

$\mathcal{A}^{\prime}$ then simulates
$\mathfrak{ACE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{D}}$ for
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$, using $m$ as the message
and using $\mathcal{O}$ as the oracle given to
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$. Since
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ are QPT algorithms,
$\mathcal{A}^{\prime}$ only makes polynomially many queries.
$\mathcal{A}^{\prime}$ outputs the bit
$\mathfrak{ACE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{D}}(1^{\lambda},\left(\mathcal{A},\mathcal{B},\mathcal{C}\right))$.

If $\mathcal{O}=P_{m}$, then the view of
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ is exactly Hybrid 1, and
otherwise it is exactly Hybrid 2. Thus, $\mathcal{A}^{\prime}$ has a non-
negligible advantage.

##### Hybrid 3:

In this hybrid, we change the order of sampling. A random subset
$S\subset\mathcal{M}$ of size $|\mathcal{M}|^{1-\delta/2}$ is sampled at the
beginning of the experiment, and the message later is sampled as
$m\leftarrow\mathcal{U}_{S}$. This is perfectly indistinguishable from Hybrid
2, as the view of $\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ is
unchanged.

##### Hybrid 4:

In this hybrid, we fix a particular $S$ such that
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$
succeeds with probability $p-\mathsf{negl}(\lambda)$ in Hybrid 3, by an
averaging argument.

Now we observe that Hybrid 4 is exactly the experiment
$\mathfrak{CE}^{\widetilde{\mathsf{GenC}}}_{\mathcal{G},\mathcal{U}_{S}}$.
Note that the distribution $\mathcal{U}_{S}$ has min-entropy
$(1-\delta/2)\log_{2}|\mathcal{M}|$. Thus, by Lemma 26, we have

$\displaystyle
p-\mathsf{negl}(\lambda)\leq\Pr\left[1\leftarrow\mathfrak{CE}_{\mathcal{G},\mathcal{U}_{S}}(1^{\lambda},\left(\mathcal{A},\mathcal{B},\mathcal{C}\right))\right]\leq|\mathcal{M}|^{\delta/2}\Pr\left[1\leftarrow\mathfrak{CE}_{\mathcal{G},\mathcal{U}_{\mathcal{M}}}(1^{\lambda},\left(\mathcal{A},\mathcal{B},\mathcal{C}\right))\right]\leq|\mathcal{M}|^{-\delta/2},$

which contradicts the assumption that $p$ is non-negligible. ∎

####  6.1.3 From Augmented Security to Unclonable-Indistinguishability

Now, we state our result that shows how to go from a search game in the plain
model to a search game in QROM with unclonable indistinguishable security. We
first invoke Lemma 27 to generically obtain augmented unclonable-search
security and we then leverage this notion of security to obtain unclonable-
indistinguishable security.

######  Theorem 28 (Search to Indistinguishability).

Let $\mathcal{G}=(\mathsf{Setup},\mathsf{GenT},\mathsf{GenC},\mathsf{Ver})$ be
a statistically correct cloning search game with message space
$\mathcal{M}=\left\\{0,1\right\\}^{\ell}$, where
$\ell=\mathsf{poly}(\lambda)$, such that
$p^{\mathsf{triv}}(\mathcal{G},\mathcal{U}_{\mathcal{M}})$ is negligible and
$\mathsf{GenC}(\mathsf{sk},m)$ does not depend363636This requirement can be
lifted by extending the definition of stateful cloning games and having
$\widetilde{\mathsf{GenC}}$ know the random coins of $\mathsf{GenT}^{\prime}$
(in this case $m$). We keep the syntax simple for there is no known
application to the more general case. on $m$. Suppose that $\mathcal{G}$ has
$(\mathcal{U}_{\mathcal{M}},|\mathcal{M}|^{-\delta})$ unclonable search
security for some $\delta>0$. Let $n=\mathsf{poly}(\lambda)$, and define a
cloning search game
$\mathcal{G}^{\prime}=(\mathsf{Setup}^{\prime},\mathsf{GenT}^{\prime},\mathsf{GenC}^{\prime},\mathsf{Ver}^{\prime})$
in QROM as follows:

  * •

$\mathcal{G}^{\prime}$ has message space
$\mathcal{M}^{\prime}=\left\\{0,1\right\\}^{n}$.

  * •

Let $H:\mathcal{M}\to\mathcal{M}^{\prime}$ be a random oracle.

  * •

$\mathsf{Setup}^{\prime}(1^{\lambda})$ runs
$\mathsf{sk}\leftarrow\mathsf{Setup}(1^{\lambda})$. It outputs
$\mathsf{sk}^{\prime}=\mathsf{sk}$.

  * •

$\mathsf{GenT}^{\prime}(\mathsf{sk}^{\prime},m^{\prime})$ parses the input as
$\mathsf{sk}^{\prime}=(\mathsf{sk},m)$. It samples
$m\leftarrow\mathcal{U}_{\mathcal{M}}$ and computes
$\rho\leftarrow\mathsf{GenT}(sk,m)$, then it outputs the token
$\rho^{\prime}=\rho\otimes\ket{m^{\prime}\oplus
H(m)}\\!\\!\bra{m^{\prime}\oplus H(m)}$ and random coins
$r_{\mathsf{GenT}^{\prime}}=m$

  * •

$\mathsf{GenC}^{\prime}(\mathsf{sk}^{\prime},m^{\prime})$ parses the input as
$\mathsf{sk}^{\prime}=\mathsf{sk}$. It computes
$\mathsf{ch}\leftarrow\mathsf{GenC}(\mathsf{sk},m)$ (recall that by assumption
this does not require knowledge of $m$) and outputs $\mathsf{ch}$.

  * •

$\mathcal{G}^{\prime}$ is a search game, which defines
$\mathsf{Ver}^{\prime}$.

Then, $\mathcal{G}^{\prime}$ has statistical correctness and $\mathsf{negl}$
unclonable indistinguishable security.

###### Proof.

Statistical correctness of $\mathcal{G}^{\prime}$ follows easily from
statistical correctness of $\mathcal{G}$, so it suffices to show
$\mathsf{negl}$ unclonable indistinguishable security. Keep in mind that by
Lemma 27, $\mathcal{G}$ has $\mathsf{negl}$ augmented unclonable security.
Suppose there exists a QPT cloning adversary
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ which breaks the unclonable
distinguishing security of $\mathcal{G}^{\prime}$. Let
$(m_{0}^{\prime},m_{1}^{\prime})$ be the messages used by
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$. Note that
$p^{\mathsf{triv}}(\mathcal{G}^{\prime},\mathcal{D}_{m_{0}^{\prime},m_{1}^{\prime}})\geq
1/2-\mathsf{negl}(\lambda)$ by the statistical correctness of
$\mathcal{G}^{\prime}$ and Lemma 24, so that we have

$\displaystyle\Pr\left[1\leftarrow\mathfrak{CE}_{\mathcal{G}^{\prime},\mathcal{D}_{m_{0}^{\prime},m_{1}^{\prime}}}(1^{\lambda},\left(\mathcal{A},\mathcal{B},\mathcal{C}\right))\right]\geq\frac{1}{2}+\mu(\lambda)$

for some non-negligible function $\mu$.

We first define a sequence of hybrids:

  * •

Hybrid 0: The original cloning experiment
$\mathfrak{CE}_{\mathcal{G}^{\prime},\mathcal{D}_{m_{0}^{\prime},m_{1}^{\prime}}}$.
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$
succeeds with probability $1/2+\mu(\lambda)$ in this experiment.

  * •

Hybrid 1: In this hybrid, we will replace the oracle $H$ for
$\mathcal{A}^{\prime}$ only with the reprogrammed oracle $H_{1}$, where

$\displaystyle H_{1}(x):=\begin{cases}u,\quad x=m\\\ H(x),\quad x\neq
m\end{cases},$

where $u\in\left\\{0,1\right\\}^{n}$ is an independent random string. We claim
that $\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ succeeds in this
hybrid with probability at least
$\frac{1}{2}+\mu(\lambda)-\mathsf{negl}(\lambda)$.

Suppose not, we will construct an adversary $\mathcal{A}^{\prime}$ that breaks
the message hiding property of $\mathcal{G}$ (Lemma 25):

    * –

$\mathcal{A}^{\prime}$ simulates Hybrid 1 for $\mathcal{A}$, using the token
$\rho$ it receives and a fresh random oracle $H^{\prime}$ it simulates on-the-
fly.

    * –

Then $\mathcal{A}^{\prime}$ measures a random query made by $\mathcal{A}$ to
$H^{\prime}$.

Note that if $H^{\prime}$ was replaced by $H$, the view of $\mathcal{A}$ would
be exactly Hybrid 0. Thus, by Theorem 4, $\mathcal{A}^{\prime}$ outputs the
message $m$ with non-negligible probability, which is larger than
$p^{\mathsf{triv}}(\mathcal{G},\mathcal{U}_{\mathcal{M}})+|\mathcal{M}|^{-\delta}$,
a contradiction.

  * •

Hybrid 2: In this hybrid, we change the order of sampling with regard to
$H(m)$ in the experiment without changing the view of
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$,
so that the probability of success remains the same. More specifically, we
sample $r\xleftarrow{\$}\left\\{0,1\right\\}^{n}$ and send it to $\mathcal{A}$
instead of $m^{\prime}\oplus H(m)$. Then, we sample
$b\xleftarrow{\$}\left\\{0,1\right\\}$ and give both $\mathcal{B}$ and
$\mathcal{C}$ the reprogrammed oracle $H_{2}^{b}$, where

$\displaystyle H_{2}^{b}(x):=\begin{cases}m_{b}^{\prime}\oplus r,\quad x=m\\\
H(x),\quad x\neq m\end{cases}$

For fixed $\mathsf{sk},m,\mathsf{ch}_{\mathcal{B}},\mathsf{ch}_{\mathcal{C}}$
and fixed $H_{-m}$, which is the partial random oracle defined on inputs
$x\neq m$, consider the following projectors:

  * •

$\Pi_{B}^{b}:$ Run $\mathcal{B}^{\prime}$ on challenge
$\mathsf{ch}_{\mathcal{B}}$ with oracle $H_{2}^{b}$. Check if the output of
$\mathcal{B}^{\prime}$ is $m_{b}^{\prime}$. Undo the computation.

  * •

Similarly define $\Pi_{C}^{b}$ for $b\in\left\\{0,1\right\\}$.

Without loss of generality assume that the bipartite state output by
$\mathcal{A}$ is a pure state $\ket{\phi_{BC}}$ in Hybrid 2. Let
$\Pi_{B}=(\Pi_{B}^{0}+\Pi_{B}^{1})/2$ and
$\Pi_{C}=(\Pi_{C}^{0}+\Pi_{C}^{1})/2$. We spectrally decompose the state as

$\displaystyle\ket{\phi_{BC}}=\sum_{i,j}\alpha_{i,j}\ket{\varphi_{i}}_{B}\otimes\ket{\psi_{j}}_{C}.$

where $\Pi_{B}\ket{\varphi_{i}}=\lambda_{i}\ket{\varphi_{i}}$ and
$\Pi_{C}\ket{\psi_{j}}=\gamma_{j}\ket{\psi_{j}}$.

######  Claim 3.

For any polynomial $p(\cdot)$, with overwhelming probability over
$\mathsf{sk},m,\mathsf{ch}_{\mathcal{B}},\mathsf{ch}_{\mathcal{C}},H_{-m}$, we
have

$\displaystyle\sum_{\begin{subarray}{c}i\;:\;|\lambda_{i}-1/2|\geq
1/p(\lambda)\\\ j\;:\;|\gamma_{j}-1/2|\geq
1/p(\lambda)\end{subarray}}\left|\alpha_{i,j}\right|^{2}\leq\mathsf{negl}(\lambda)$
(14)

###### Proof.

Assume the quantity in eq. 14 is a non-negligible function $w(\lambda)$. We
will construct an adversary
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$
which breaks the $\mathsf{negl}$ augmented security of $\mathcal{G}$:

  * •

$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$
get oracle access to $P_{m}(\cdot)$, where $m\leftarrow\mathcal{D}$.

  * •

$\mathcal{A}^{\prime}$ gets a quantum token $\rho$. It samples a $2t$-wise
independent hash function
$H:\left\\{0,1\right\\}^{\ell}\to\left\\{0,1\right\\}^{n}$ to simulate a
random oracle and a random string $r\xleftarrow{\$}\left\\{0,1\right\\}^{n}$,
where $t=\mathsf{poly}(\lambda)$ is an upper-bound on the number of total
random oracle queries made by
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$. Then, it runs
$\mathcal{A}$ on $\rho\otimes\ket{r}\\!\\!\bra{r}$ to get a bipartite state
$\ket{\phi_{BC}}$. It sends this state to $\mathcal{B}^{\prime}$ and
$\mathcal{C}^{\prime}$. It also sends the description of $H$ to both of them.

  * •

$\mathcal{B}^{\prime}$ receives a challenge $\mathsf{ch}_{\mathcal{B}}$ from
the challenger. It implements the operator $\Pi_{B}$ defined above. Note that
$\mathcal{B}^{\prime}$ can reprogram the random oracle $H_{2}$ on input $m$
using and its oracle access to $P_{m}(\cdot)$. Then, $\mathcal{B}^{\prime}$
applies the efficient symmetric approximate threshold measurement
$\mathsf{SATI}_{(P,Q),\gamma}^{\epsilon,\delta}$ in Theorem 9 with
$P=(\Pi^{B}_{0}+\Pi^{B}_{1})/2$, $Q=I-P$, $\gamma=3/4p$, $\epsilon=1/4p$ and
$\delta=2^{-\lambda}$. If the outcome is 0, $\mathcal{B}^{\prime}$ aborts. If
the outcome is 1, $\mathcal{B}^{\prime}$ then runs $\mathcal{B}$ on the
leftover state with $H_{2}^{0}$ or $H_{2}^{1}$ picked uniformly at random. It
measures and outputs a random query $\mathcal{B}$ makes to the random oracle.

  * •

$\mathcal{C}^{\prime}$ is defined the same way as $\mathcal{B}^{\prime}$, in
the end outputting a random query made by $\mathcal{C}$ to the random oracle.

By Theorem 9 bullet (1), both $\mathcal{B}^{\prime}$ and
$\mathcal{C}^{\prime}$ will get outcome 1 with non-negligible probability
$w-2\delta$, in which case by bullet (2) the leftover state will be
$4\delta$-close to the the following state:

$\displaystyle\sum_{\begin{subarray}{c}i:|\lambda_{i}-1/2|>1/4p\\\
j:|\gamma_{j}-1/2|>1/4p\end{subarray}}\alpha_{i,j}\ket{\varphi_{i}}_{B}\otimes\ket{\psi_{j}}_{C}.$

Observe that when $\mathcal{B}$ does not query $m$, it will succeed with
probability exactly $1/2$. Therefore, by Theorem 4, the query weight of
$\mathcal{B}$ on $m$ is non-negligible. Similarly, the query weight of
$\mathcal{C}$ on $m$ is non-negligible. Therefore,
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$
succeed with non-negligible probability, a contradiction.

∎

Therefore, for any polynomial $p$, we have that $\ket{\phi_{BC}}$ is
negligibly close to the state $\ket{\phi_{B}}+\ket{\phi_{C}}$, where

$\displaystyle\ket{\phi_{B}}=\sum_{\begin{subarray}{c}i:|\lambda_{i}-1/2|\leq
1/p\end{subarray}}\alpha_{i,j}\ket{\varphi_{i}}_{B}\otimes\ket{\psi_{j}}_{C},\quad\ket{\phi_{C}}=\sum_{\begin{subarray}{c}i:|\lambda_{i}-1/2|>1/p\\\
j:|\gamma_{j}-1/2|\leq
1/p\end{subarray}}\alpha_{i,j}\ket{\varphi_{i}}_{B}\otimes\ket{\psi_{j}}_{C},$

in which case we could bound the success probability of
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ in Hybrid 2 as:

$\displaystyle\frac{1}{2}+\mu(\lambda)-\mathsf{negl}(\lambda)\leq(\left|(\Pi^{0}_{B}\otimes\Pi^{0}_{C})(\ket{\phi_{B}}+\ket{\phi_{C}})\right|^{2}+\left|(\Pi^{1}_{B}\otimes\Pi^{1}_{C})(\ket{\phi_{B}}+\ket{\phi_{C})}\right|^{2})/2$
$\displaystyle=$
$\displaystyle\frac{1}{2}\cdot\left(\langle\phi_{B}|(\Pi^{0}_{B}\otimes\Pi^{0}_{C})|\phi_{B}\rangle+\langle\phi_{B}|(\Pi^{1}_{B}\otimes\Pi^{1}_{C})|\phi_{B}\rangle+\langle\phi_{C}|(\Pi^{0}_{B}\otimes\Pi^{0}_{C})|\phi_{C}\rangle+\langle\phi_{C}|(\Pi^{1}_{B}\otimes\Pi^{1}_{C})|\phi_{C}\rangle\right)$
$\displaystyle+$
$\displaystyle\mathsf{Re}\left(\langle\phi_{B}|(\Pi^{0}_{B}\otimes\Pi^{0}_{C})|\phi_{C}\rangle+\langle\phi_{B}|(\Pi^{1}_{B}\otimes\Pi^{1}_{C})|\phi_{C}\rangle\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\cdot\left(\langle\phi_{B}|(\Pi^{0}_{B}\otimes
I)|\phi_{B}\rangle+\langle\phi_{B}|(\Pi^{1}_{B}\otimes
I)|\phi_{B}\rangle+\langle\phi_{C}|(I\otimes\Pi^{0}_{C})|\phi_{C}\rangle+\langle\phi_{C}|(I\otimes\Pi^{1}_{C})|\phi_{C}\rangle\right)$
$\displaystyle+$
$\displaystyle\mathsf{Re}\left(\langle\phi_{B}|(\Pi^{0}_{B}\otimes\Pi^{0}_{C})|\phi_{C}\rangle+\langle\phi_{B}|(\Pi^{1}_{B}\otimes\Pi^{1}_{C})|\phi_{C}\rangle\right)$
$\displaystyle=$ $\displaystyle\langle\phi_{B}|(\Pi_{B}\otimes
I)|\phi_{B}\rangle+\langle\phi_{C}|(I\otimes\Pi_{C})|\phi_{C}\rangle+\mathsf{Re}\left(\langle\phi_{B}|(\Pi^{0}_{B}\otimes\Pi^{0}_{C})|\phi_{C}\rangle+\langle\phi_{B}|(\Pi^{1}_{B}\otimes\Pi^{1}_{C})|\phi_{C}\rangle\right)$
$\displaystyle\leq\frac{1}{2}+\frac{1}{p},$

where in the last step we used Lemma 6. Since $p$ is arbitrary, this is a
contradiction.

∎

As a corollary, we achieve unclonable encryption in QROM using BB84 states.
This is an improvement over the main result of [AKL+22], as it can be more
easily implemented on near-term quantum computers.

######  Corollary 8 (Existence of Unclonable Encryption in QROM Using Prepare-
and-Measure States).

There exists a public-key unclonable encryption scheme with unclonable
indistinguishable security in QROM, which uses only prepare-and-measure
quantum operations.

###### Proof.

Set $\mathcal{G}=\mathcal{G}_{\mathsf{BB84}}$ from Definition 21, then it
satisfies the condition of Theorem 28, so there exists $\mathcal{G}^{\prime}$
as described in the theorem. Observe that since $\mathcal{G}$ is a cloning
encryption game, so is $\mathcal{G}^{\prime}$. Thus, $\mathcal{G}^{\prime}$
gives a construction of unclonable encryption in QROM, and the $\mathsf{negl}$
unclonable distinguishing security implies unclonable security of this
encryption scheme.

Finally, we invoke the generic compiler in [AK21] to achieve a public-key
scheme373737Although [AK21] only showed that their transformation preserves
weak unclonable security, it could easily be checked that it also preserves
strong unclonable security.. ∎

###  6.2 Indistinguishablity-to-Search

######  Theorem 29.

If $\mathcal{G}=(\mathsf{Setup},\mathsf{GenT},\mathsf{GenC},\mathsf{Ver})$ is
a cloning search game with statistical correctness and $\varepsilon$
unclonable indistinguishable security, then $\mathcal{G}$ has
$(\mathcal{D},2\varepsilon+\mathsf{negl})$ unclonable security for any
distribution $\mathcal{D}$ over the message space $\mathcal{M}$ such that
$\mathcal{G}$ is $\mathcal{D}$-evasive.

###### Proof.

We will give a generic proof that works for an arbitrary extension
$\widetilde{\mathsf{GenC}}$, which we will omit for simplicity. Suppose there
exists a cloning adversary $\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$
which breaks $(\mathcal{D},\varepsilon)$ unclonable security of $\mathcal{G}$.
We will construct an adversary
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$,
which will break $(\mathcal{D}_{m_{0},m},\varepsilon^{\prime})$ unclonable
security of $\mathcal{G}$, where
$\varepsilon^{\prime}=\varepsilon/2-\mathsf{negl}$, $m_{0}\in\mathcal{M}$ is a
fixed message, and $m$ is a message sampled as $m\leftarrow\mathcal{D}$. By
convexity, this would imply that there exists a fixed value of $m$ for which
the security is broken, hence finishing the proof. We describe
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$
below:

  * •

$\mathcal{A}^{\prime}$ is the same as $\mathcal{A}$.

  * •

$\mathcal{B}^{\prime}$ runs $\mathcal{B}$ with the input it receives. If the
output is $m$, $\mathcal{B}^{\prime}$ outputs $m$; otherwise
$\mathcal{B}^{\prime}$ outputs $m_{0}$.

  * •

$\mathcal{C}^{\prime}$ is defined similarly to $\mathcal{B}^{\prime}$.

Note that if the message in the experiment
$\mathfrak{CE}_{\mathcal{G},\mathcal{D}_{m_{0},m}}$ above is $m$, then by
assumption
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$
wins with probability $p>\varepsilon$. On the other hand, if the message is
$m_{0}$, then the probability that $\mathcal{B}^{\prime}$ outputs $m$ is at
most $\mathsf{OPT}(m\mid\mathsf{ch}_{\mathcal{B}})\leq\mathsf{negl}(\lambda)$
by Lemma 24. Hence, by union bound,
$\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right)$
succeeds with overwhelming probability in this case, and we have

$\displaystyle\operatorname*{\mathbb{E}}_{m\leftarrow\mathcal{D}}\Pr\left[1\leftarrow\mathfrak{CE}_{\mathcal{G},\mathcal{D}_{m_{0},m}}(1^{\lambda},\left(\mathcal{A}^{\prime},\mathcal{B}^{\prime},\mathcal{C}^{\prime}\right))\right]=\frac{1}{2}\left(p+1-\mathsf{negl}\right)\geq\frac{1}{2}+\frac{\varepsilon(\lambda)}{2}-\mathsf{negl}(\lambda)$

∎

as desired.

##  7 From Search to Decision Games

We present a transformation from search games to decision games. We remark
that the transformation is tailored to application of copy-protection and
thus, the resulting decision game has a specific form.

######  Theorem 30 (Search to Decision).

Let $\mathcal{G}=(\mathsf{Setup},\mathsf{GenT},\mathsf{GenC},\mathsf{Ver})$ be
a statistically correct cloning encryption game with message space
$\mathcal{M}=\left\\{0,1\right\\}^{\ell}$, where
$\ell=\mathsf{poly}(\lambda)$, such that

  * •

$\mathsf{Setup}(1^{\lambda})$ outputs a uniformly random key
$\mathsf{sk}\xleftarrow{\$}\mathcal{K}$, where $|\mathcal{K}|^{-1}$ is
negligible in $\lambda$.

  * •

$\mathcal{G}$ is $\mathcal{U}_{\mathcal{M}}$-evasive.

  * •

$\mathcal{G}$ has $(\mathcal{U}_{\mathcal{M}},|\mathcal{M}|^{-\delta})$
unclonable search security for some $\delta>0$

Define a cloning decision game
$\mathcal{G}^{\prime}=(\mathsf{Setup}^{\prime},\mathsf{GenT}^{\prime},\mathsf{GenC}^{\prime},\mathsf{Ver}^{\prime})$
in QROM as follows:

  * •

Let $\mathcal{M}^{\prime}$ be an arbitrary message space.

  * •

Let $H:\mathcal{M}\to\left\\{0,1\right\\}^{n}$ and
$G:\mathcal{M}^{\prime}\to\mathcal{K}$ be random oracles, where
$n=\Omega(\lambda)$.

  * •

$\mathsf{Setup}^{\prime}(1^{\lambda})$ outputs $\mathsf{sk}^{\prime}=\bot$

  * •

$\mathsf{GenT}^{\prime}(\mathsf{sk}^{\prime},m^{\prime})$ samples
$m\leftarrow\mathcal{U}_{\mathcal{M}}$. It computes
$\rho\leftarrow\mathsf{GenT}(G(m^{\prime}),m)$. It outputs
$\rho^{\prime}=\rho\otimes\ket{H(m)}\\!\\!\bra{H(m)}$.

  * •

$\mathsf{GenC}^{\prime}(\mathsf{sk}^{\prime},m^{\prime})$ is an algorithm
which does not depend on $\mathsf{sk}^{\prime}$, and outputs a value
$\mathsf{ch}^{\prime}\in\mathcal{M}^{\prime}$.

  * •

$\mathsf{Ver}^{\prime}(\mathsf{sk}^{\prime},m^{\prime},\mathsf{ch}^{\prime},\mathsf{ans}^{\prime})$
accepts if $\mathsf{ans}^{\prime}=[\mathsf{ch}^{\prime}==m^{\prime}]$.

Then, $\mathcal{G}^{\prime}$ has statistical correctness and
$(\mathcal{D}^{\prime},\mathsf{negl})$ independent-challenge unclonable
security for any unlearnable distribution $\mathcal{D}^{\prime}$ over
$\mathcal{M}$.

###### Proof.

We begin with correctness. Following Definition 3, we define a QPT algorithm
$\mathcal{A}_{\mathcal{G}^{\prime}}(\rho^{\prime},\mathsf{ch}^{\prime})$ as
follows:

  * •

Parse the token as $\rho^{\prime}=\rho\otimes\ket{y}\\!\\!\bra{y}$, i.e.
measure the last register to obtain $y\in\left\\{0,1\right\\}^{n}$.

  * •

Compute $\mathsf{ch}\leftarrow\mathsf{GenC}(G(\mathsf{ch}^{\prime}),m)$,
recall that this does not require the knowledge of $m$.

  * •

Compute $m\leftarrow\mathcal{A}_{\mathcal{G}}(\rho,\mathsf{ch})$.

  * •

Output $b=[H(m)==y]$.

To analyze correctness, we consider two cases: (1)
$\mathsf{ch}^{\prime}=m^{\prime}$ and (2) $\mathsf{ch}^{\prime}\neq
m^{\prime}$.

  * •

If $\mathsf{ch}^{\prime}=m^{\prime}$, then by statistical correctness of
$\mathcal{G}$, $\mathcal{A}_{\mathcal{G}^{\prime}}$ receives the correct
message $m=\mathsf{sk}^{\prime}$ from $\mathcal{A}_{\mathcal{G}}$ above and
outputs 1 with overwhelming probability.

  * •

If $\mathsf{ch}^{\prime}\neq m^{\prime}$, then $\mathcal{A}_{\mathcal{G}}$
sees a challenge generated by a random key
$\tilde{\mathsf{sk}}=G(\mathsf{ch}^{\prime})$ that is independent from
$G(m^{\prime})$, which is the key used to generate the token $\mathcal{A}_{G}$
receives. We will show that the probability that $\mathcal{A}_{\mathcal{G}}$
outputs the correct message $m$ in this case is negligible. This will then
imply that $\mathcal{A}_{\mathcal{G}}^{\prime}$ outputs 0 with overwhelming
probability, since the output length of $H$ is $\Omega(\lambda)$.

Now suppose that $\mathcal{A}_{\mathcal{G}}$ outputs the correct message above
with non-negligible probability $p$, we will construct an adversary
$\mathcal{A}^{\prime}$ that breaks the message hiding property of
$\mathcal{G}$ using $\mathcal{A}_{\mathcal{G}}$:

    * –

$\mathcal{A}^{\prime}$ receives a token
$\rho\leftarrow\mathsf{GenT}(\mathsf{sk},m)$, where
$\mathsf{sk}\xleftarrow{\$}\mathcal{K}$ and $m\leftarrow\mathcal{D}$.

    * –

$\mathcal{A}^{\prime}$ then samples
$\tilde{\mathsf{sk}}\xleftarrow{\$}\mathcal{K}$ and computes
$\mathsf{ch}\leftarrow\mathsf{GenC}(\mathsf{sk},m)$. Recall that this does not
require the knowledge of $m$.

    * –

Next, $\mathcal{A}^{\prime}$ computes and outputs
$\tilde{m}\leftarrow\mathcal{A}_{\mathcal{G}}(\rho,\mathsf{ch})$.

By assumption, $\tilde{m}=m$ with non-negligible probability, since for
$\mathsf{ch}^{\prime}\neq m^{\prime}$ the value $G(\mathsf{ch}^{\prime})$ is
identically distributed as the value $\tilde{sk}$ sampled by
$\mathcal{A}^{\prime}$ above. Therefore, $\mathcal{A}^{\prime}$ breaks the
message-hiding property of $\mathcal{G}$ given in Lemma 25, a contradiction.

Next, we show $(\mathcal{D},\mathsf{negl})$ unclonable security. Note that by
Lemma 27, $\mathcal{G}$ has $\mathsf{negl}$ augmented unclonable security. We
will define a sequence of hybrids:

  * •

Hybrid 0: This is the original cloning experiment
$\mathfrak{CE}_{\mathcal{G}^{\prime},\mathcal{D}^{\prime}}^{\mathsf{ind}}$.
Suppose for the sake of contradiction that there exists a cloning adversary
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ which succeeds in this
hybrid with probability
$p=p^{\mathsf{triv}}(\mathcal{G}^{\prime},\mathcal{D}^{\prime})+\mu(\lambda)$
for a non-negligible function $\mu$.

  * •

Hybrid 1: In this hybrid, we will change the oracle $G$ for $\mathcal{A}$ only
to the punctured oracle $G_{m}$, defined as

$\displaystyle G_{m^{\prime}}(x):=\begin{cases}u,\quad x=m^{\prime}\\\
G(x),\quad x\neq m^{\prime}\end{cases},$

where $u\in\mathcal{K}$ is an independent uniformly random value. We claim
that $\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ succeed in this
experiment with probability $p-\mathsf{negl}(\lambda)$. Suppose this is false.
Let $\rho_{BC}^{j}$ be the bipartite state outputs by $\mathcal{A}$ in Hybrid
$j$, then $\mathsf{TD}\left(\rho_{BC}^{1},\rho_{BC}^{2}\right)$ must be non-
negligible, since the only difference between Hybrids 0-1 is on the random
oracle $G$ for $\mathcal{A}$. Using $\mathcal{A}$, we will construct an
adversary that breaks the unlearnability of $\mathcal{D}^{\prime}$:

    * –

$\mathcal{A}^{\prime}$ gets oracle access to $P_{m^{\prime}}(\cdot)$ (which
will not be used), where $m^{\prime}\leftarrow\mathcal{D}^{\prime}$. It
samples random oracles $G^{\prime}:\mathcal{M}^{\prime}\to\mathcal{K}$ and
$H^{\prime}:\mathcal{M}\to\left\\{0,1\right\\}^{n}$, as well as a message
$m\leftarrow\mathcal{D}$.

    * –

Then, $\mathcal{A}^{\prime}$ samples $\mathsf{sk}\xleftarrow{\$}\mathcal{K}$,
computes $\rho\leftarrow\mathsf{GenT}(\mathsf{sk},m)$, and runs
$\mathcal{A}(\rho,H^{\prime}(m))$.

    * –

During the last step, it measures and outputs a random query made by
$\mathcal{A}$ to the oracle $G^{\prime}$.

As the view of $\mathcal{A}$ in Hybrid 1 is perfectly simulated, by Theorem 4,
the query weight of $\mathcal{A}$ on $m^{\prime}$ is non-negligible, hence
$\mathcal{A}^{\prime}$ correctly outputs $m^{\prime}$ with non-negligible
probability, breaking unlearnability.

  * •

Hybrid 2: In this hybrid, we change the order of sampling. A random value
$k\leftarrow\mathcal{U}_{\mathcal{K}}$ is sampled at the beginning of the
experiment and the quantum part of the token received by $\mathcal{A}$ is
calculated as $\rho\leftarrow\mathsf{GenT}(k,m)$. In turn, the random oracle
$G$ for $\mathcal{B}$ and $\mathcal{C}$ is replaced by the reprogrammed oracle
$G^{2}_{m^{\prime}}$ which is defined as

$\displaystyle G^{2}_{m^{\prime}}(x):=\begin{cases}k,\quad x=m^{\prime}\\\
G(x),\quad x\neq m^{\prime}\end{cases},$

This hybrid is perfectly indistinguishable from Hybrid 1, hence
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ succeeds in this hybrid
with probability at least $p-\mathsf{negl}(\lambda)$.

  * •

Hybrid 3: In this hybrid, we replace the oracle $H$ for $\mathcal{A}$ with the
punctured oracle $H_{m}$ defined as

$\displaystyle H_{m}(x):=\begin{cases}w,\quad x=m\\\ G(x),\quad x\neq
m\end{cases},$

where $w\in\left\\{0,1\right\\}^{n}$ is an independent uniformly random value.
We claim that $\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ succeeds in
this hybrid with probability at least $p-\mathsf{negl}(\lambda)$. Suppose not,
then we have $\mathsf{TD}\left(\rho_{BC}^{2},\rho_{BC}^{3}\right)$ is non-
negligible. We will use $\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ to
construct an adversary $\mathcal{A}^{\prime}$ to break the message hiding
property of $\mathcal{G}$:

    * –

$\mathcal{A}^{\prime}$ receives $\rho\leftarrow\mathsf{GenT}(\mathsf{sk},m)$
from the challenger, where $\mathsf{sk}\xleftarrow{\$}\mathcal{K}$ and
$m\leftarrow\mathcal{D}$.

    * –

Then $\mathcal{A}^{\prime}$ samples $w\xleftarrow{\$}\left\\{0,1\right\\}^{n}$
and simulates random oracles
$H^{\prime}:\mathcal{M}\to\left\\{0,1\right\\}^{n},G^{\prime}:\mathcal{M}^{\prime}\to\mathcal{K}$
and runs $\mathcal{A}$ on input $\rho\otimes\ket{w}\\!\\!\bra{w}$ with oracles
$H^{\prime},G^{\prime}$. It measures and outputs a random query made by
$\mathcal{A}$ to the oracle $H^{\prime}$.

As the view of $\mathcal{A}$ in Hybrid 3 is perfectly simulated, by Theorem 4,
the query weight of $\mathcal{A}$ on $m$ is non-negligible, hence
$\mathcal{A}^{\prime}$ outputs $m$ with non-negligible probability,
contradicting the message-hiding property of $\mathcal{G}$ given in Lemma 25.

Therefore, we have established that
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ succeeds in Hybrid 3 with
probability
$p^{\mathsf{triv}}(\mathcal{G}^{\prime},\mathcal{D}^{\prime})+\eta(\lambda)$
for some non-negligible function $\eta$. Without loss of generality, assume
that the bipartite state created by $\mathcal{A}$ is a pure state, i.e.
$\rho_{BC}^{3}=\ket{\phi_{BC}}\\!\\!\bra{\phi_{BC}}$. Consider the following
binary POVM elements:

  * •

$\Pi_{B}$: Sample
$\mathsf{ch}^{\prime}\leftarrow\mathsf{GenC}^{\prime}(sk^{\prime},m^{\prime})$.
Run $\mathcal{B}$ with oracles $H,G^{2}_{m^{\prime}}$ and input
$\mathsf{ch}^{\prime}$. Measure if the output of $\mathcal{B}$ equals
$[\mathsf{ch}^{\prime}==m^{\prime}]$, in which case we will say that
$\mathcal{B}$ _passed_ $\Pi_{B}$.

  * •

Similarly define $\Pi_{C}$ for $\mathcal{C}$.

We write the state received by $\mathcal{B}$ and $\mathcal{C}$ in spectral
decomposition as

$\displaystyle\ket{\phi_{BC}}\\!\\!\bra{\phi_{BC}}=\sum_{i,j}\alpha_{i,j}\ket{\varphi_{i}}_{B}\ket{\psi_{j}}_{C},$

where $\Pi_{B}\ket{\varphi_{i}}_{B}=\lambda_{i}\ket{\varphi_{i}}_{B}$ and
$\Pi_{C}\ket{\psi_{j}}_{C}=\gamma_{j}\ket{\psi_{j}}_{C}$. Let $q$ be a
polynomial. Let
$p^{\mathsf{triv}}:=p^{\mathsf{triv}}(\mathcal{G}^{\prime},\mathcal{D}^{\prime})$.

We can bound the probability that
$\left(\mathcal{A},\mathcal{B},\mathcal{C}\right)$ succeeds in Hybrid 3 as

$\displaystyle
p-\mathsf{negl}(\lambda)\leq\braket{\phi_{BC}}{(\Pi_{B}\otimes\Pi_{C})}{\phi_{BC}}=\sum_{i,j}\left|\alpha_{i,j}\right|^{2}\lambda_{i}\gamma_{j}$
$\displaystyle\leq\sum_{\begin{subarray}{c}i:\;\lambda_{i}>p^{\mathsf{triv}}+1/q\\\
j:\;\gamma_{j}>p^{\mathsf{triv}}+1/q\end{subarray}}\left|\alpha_{i,j}\right|^{2}\lambda_{i}\gamma_{j}$
$\displaystyle+\left(p^{\mathsf{triv}}+\frac{1}{q}\right)\sum_{\begin{subarray}{c}i:\;\lambda_{i}\leq
p^{\mathsf{triv}}+1/q\\\
j:\;\gamma_{j}>p^{\mathsf{triv}}+1/q\end{subarray}}\left|\alpha_{i,j}\right|^{2}+\left(p^{\mathsf{triv}}+\frac{1}{q}\right)\sum_{i,j:\;\mu_{j}\leq
p^{\mathsf{triv}}+1/q}\left|\alpha_{i,j}\right|^{2}$ $\displaystyle\leq