$\displaystyle+(3q_{\mathsf{B}}q_{\mathsf{C}}+2)q_{\mathsf{B}}q_{\mathsf{C}}\,\mathbb{E}_{k}\mathbb{E}_{l}\left\|P_{\underline{v}}\otimes
P_{\underline{v}}\left(\left(U_{\mathsf{B}}O_{\mathsf{B}}^{F_{\underline{v},\underline{z}}}\right)^{k}\otimes\left(U_{\mathsf{C}}O_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}\right)^{l}\right)\ket{\psi}\right\|\,,$
(30)

where the inequality follows from a triangle inequality together with a bound
used in [BL19] (more precisely, Lemma 18 in [BL19]). Applying Jensen’s
inequality and the definition of $M$, we obtain

$\displaystyle\mathbb{E}_{F}\mathbb{E}_{\underline{z}\leftarrow\mathcal{Z}}\|$
$\displaystyle\Pi^{g(\underline{z})}\left(\left(U_{\mathsf{B}}O_{\mathsf{B}}^{F_{\underline{v},\underline{z}}}\right)^{q_{\mathsf{B}}}\otimes\left(U_{\mathsf{C}}O_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}\right)^{q_{\mathsf{C}}}\right)\ket{\psi}\|^{2}$
$\displaystyle\leq\mathbb{E}_{F}\mathbb{E}_{\underline{z}\leftarrow\mathcal{Z}}\|\Pi^{g(\underline{z})}\left(\left(U_{\mathsf{B}}O_{\mathsf{B}}^{F_{\underline{v},\underline{z}}}\right)^{q_{\mathsf{B}}}\otimes
V_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}+V_{\mathsf{B}}^{F_{\underline{v},\underline{z}}}\otimes
W_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}\right)\ket{\psi}\|^{2}$ (31)
$\displaystyle\quad\quad+(3q_{\mathsf{B}}q_{\mathsf{C}}+2)q_{\mathsf{B}}q_{\mathsf{C}}\sqrt{M}$
(32)

We will show that, for any fixed $F$,

$\mathbb{E}_{\underline{z}\leftarrow\mathcal{Z}}\|\Pi^{g(\underline{z})}\left(\left(U_{\mathsf{B}}O_{\mathsf{B}}^{F_{\underline{v},\underline{z}}}\right)^{q_{\mathsf{B}}}\otimes
V_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}+V_{\mathsf{B}}^{F_{\underline{v},\underline{z}}}\otimes
W_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}\right)\ket{\psi}\|^{2}\leq
9p_{\max{}}\,.$

Let

$\alpha=\mathbb{E}_{\underline{z}\leftarrow\mathcal{Z}}\|\Pi^{g(\underline{z})}\left(\left(U_{\mathsf{B}}O_{\mathsf{B}}^{F_{\underline{v},\underline{z}}}\right)^{q_{\mathsf{B}}}\otimes
V_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}\right)\ket{\psi}\|^{2}\,,$

and

$\beta=\mathbb{E}_{\underline{z}\leftarrow\mathcal{Z}}\|\Pi^{g(\underline{z})}\left(V_{\mathsf{B}}^{F_{\underline{v},\underline{z}}}\otimes
W_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}\right)\ket{\psi}\|^{2}\,.$

Applying triangle inequalities, and using that the $\Pi^{g(\underline{z})}$
are orthogonal projectors, we get

$\mathbb{E}_{\underline{z}\leftarrow\mathcal{Z}}\|\Pi^{g(\underline{z})}\left(\left(U_{\mathsf{B}}O_{\mathsf{B}}^{F_{\underline{v},\underline{z}}}\right)^{q_{\mathsf{B}}}\otimes
V_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}+V_{\mathsf{B}}^{F_{\underline{v},\underline{z}}}\otimes
W_{C}^{F_{\underline{v},\underline{z}}}\right)\ket{\psi}\|^{2}\leq\alpha+\beta+2\sqrt{\alpha\beta}$
(33)

Now, notice that $V_{\mathsf{B}}^{F_{\underline{v},\underline{z}}}$ and
$V_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}$ do not depend on
$\underline{z}$, since they always project on the support of
$\mathds{1}-P_{\underline{v}}$. Using standard properties of the operator
norm, we get

$\displaystyle\alpha$
$\displaystyle=\mathbb{E}_{\underline{z}\leftarrow\mathcal{Z}}\|\Pi^{g(\underline{z})}\left(\left(U_{\mathsf{B}}O_{\mathsf{B}}^{F_{\underline{v},\underline{z}}}\right)^{q_{\mathsf{B}}}\otimes
V_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}\right)\ket{\psi}\|^{2}$ (34)
$\displaystyle\leq\mathbb{E}_{\underline{z}\leftarrow\mathcal{Z}}\|(\mathds{1}_{\mathsf{B}}\otimes\Pi_{\mathsf{C}}^{g(\underline{z})})\left(\mathds{1}_{\mathsf{B}}\otimes
V_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}\right)\ket{\psi}\|^{2}$ (35)
$\displaystyle\leq\bra{\psi}\mathds{1}_{\mathsf{B}}\otimes\left(\left(V_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}\right)^{\dagger}\left(\mathbb{E}_{z\leftarrow\mathcal{Z}}\Pi_{C}^{g(\underline{z})}\right)V_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}\right)\ket{\psi}$
(36) $\displaystyle\leq p_{\max{}},$ (37)

where the last line follows because
$\mathbb{E}_{\underline{z}\leftarrow\mathcal{Z}}\Pi_{\mathsf{C}}^{g(\underline{z})}\leq
p_{\max{}}\mathds{1}$.

Similarly, one obtains $\beta\leq 4p_{\max{}}$, where the factor of $4$ is due
to the fact that $W_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}$ is not
unitary in general, and so we upper bound it by using

$\|W_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}\|_{\infty}\leq\|\left(U_{\mathsf{C}}O_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}\right)^{q_{\mathsf{C}}}\|_{\infty}+\|V_{\mathsf{C}}^{F_{\underline{v},\underline{z}}}\|_{\infty}\leq
2\,.$

It follows that $\alpha+\beta+2\sqrt{\alpha\beta}\leq 9p_{\max{}}$, as
desired. ∎

We specialize Lemma 20 to our exact case in the following corollary. Before
stating the corollary, let’s fix some notation. For functions
$H_{1},\ldots,H_{r}$, we define a “combined” oracle unitary
$O^{H_{1},\ldots,H_{r}}$, acting on a “control” register, a “query” register,
and an auxiliary register, as follows:

$O^{H_{1},\ldots,H_{r}}\ket{i}\ket{x}\ket{0}=\ket{i}O^{H_{i}}(\ket{x}\ket{0})\,.$

######  Corollary 3.

Let $r\in\mathbb{N}$. Let $v\in\\{0,1\\}^{m(\lambda)}$ and
$z,z^{\prime}\in\\{0,1\\}^{\lambda}$. For all unitaries
$U_{\mathsf{B}},U_{\mathsf{C}}$, for all bipartite states $\ket{\psi}$, the
following holds:

$\displaystyle\mathbb{E}_{H}\mathbb{E}_{w\leftarrow\\{0,1\\}^{r}}\|\Pi^{w}\left(U_{\mathsf{B}}O_{\mathsf{B}}^{H_{v,z}^{w_{1}},..,H_{v,z}^{w_{r}}}\right)^{q_{\mathsf{B}}}\otimes$
$\displaystyle\left(U_{\mathsf{C}}O_{\mathsf{C}}^{H_{v,z}^{w_{1}},..,H_{v,z}^{w_{r}}}\right)^{q_{\mathsf{C}}}\ket{\psi}\|^{2}$
(38)
$\displaystyle\leq\frac{9}{2^{r}}+\mathsf{poly}(q_{\mathsf{B}},q_{\mathsf{C}})\sqrt{M},\,$
(39)

where $\Pi^{w}=\Pi_{\mathsf{B}}^{w}\otimes\Pi_{\mathsf{C}}^{w}$,
$H:\\{0,1\\}^{m(\lambda)}\rightarrow\\{0,1\\}^{\lambda}$ and, for
$b\in\\{0,1\\}$,

$H_{v,z}^{b}:=\begin{cases}H_{v,z}&\text{if }b=0\,,\\\
H_{v,z^{\prime}}&\text{if }b=1\,,\end{cases}$

and

$M=\mathbb{E}_{k}\mathbb{E}_{l}\mathbb{E}_{H}\mathbb{E}_{w}\|\ket{v}\bra{v}\otimes\ket{v}\bra{v}(U_{\mathsf{B}}O^{H_{v,z}^{w_{1}},..,H_{v,z}^{w_{r}}}_{\mathsf{B}})^{k}\otimes(U_{\mathsf{C}}O^{H_{v,z}^{w_{1}},..,H_{v,z}^{w_{r}}}_{\mathsf{C}})^{l}\ket{\psi}\|^{2}\,.$

###### Proof.

We apply Lemma 20 with

  * •

$\mathcal{R}=\\{0,1\\}^{r}$, $\,\mathcal{X}=[r]\times\\{0,1\\}^{m(\lambda)}$,
$\,\mathcal{Y}=\\{0,1\\}^{\lambda}$.

  * •

$\mathcal{Z}=\\{(z_{1},\ldots,z_{r}):z_{i}\in\\{z,z^{\prime}\\}\\}$, and $Z$
the uniform distribution over $\mathcal{Z}$,

  * •

$g:\mathcal{Z}\rightarrow\mathcal{R}$ such that $g(z_{1},\ldots,z_{r})=w$
where $w_{i}=0$ if $z_{i}=z$ and $w_{i}=1$ if $z_{i}=z^{\prime}$.

  * •

$F:\mathcal{X}\rightarrow\mathcal{Y}$ is such that $F(i,x)=(i,H(x))$.

  * •

$\underline{v}=\big{(}(1,v),\ldots,(r,v)\big{)}$.

∎

######  Lemma 21.

For all query-bounded adversaries $\mathcal{A}$ there exists a negligible
function $\mu$ such that $\mathcal{A}$ wins game $\mathsf{G}_{r}$ with
probability at most $\frac{9}{2^{r}}+\mu(\lambda)$.

###### Proof.

Suppose for a contradiction that there existed an adversary
$(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})$, and a polynomial $p>0$, such
that $(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})$ wins game
$\mathsf{G}_{r}$ with probability greater than $\frac{9}{2^{r}}+1/p(\lambda)$
for infinitely many $\lambda$’s. We show that this implies an adversary that
wins at the following variant of the monogamy game of Section 2.2. Let
$\lambda,\lambda^{\prime}\in\mathbb{N}$. For clarity, we will denote the
adversary in this monogamy game as the triple $(\mathcal{P}^{\prime}$,
$\mathcal{F}_{1}^{\prime},\mathcal{F}_{2}^{\prime})$.

  * •

The challenger samples uniformly $\theta,v\leftarrow\\{0,1\\}^{\lambda}$ as in
the original game. The challenger picks a uniformly random function
$H:\\{0,1\\}^{\lambda}\rightarrow\\{0,1\\}^{\lambda^{\prime}}$ and sends
$H(v)$ to $\mathcal{P}^{\prime}$.

  * •

Additionally, the challenger samples uniformly $w\leftarrow\\{0,1\\}^{r}$, and
$z\leftarrow\\{0,1\\}^{\lambda^{\prime}}$. $\mathcal{P}$, $\mathcal{F}_{1}$
and $\mathcal{F}_{2}$ get oracle access to $H_{v,z}^{w_{i}}$, for $i\in[r]$,
where

$H_{v,z}^{b}:=\begin{cases}H&\text{if }b=0\,,\\\ H_{v,z}&\text{if
}b=1\,.\end{cases}$

  * •

The rest proceeds as in the original monogamy game.

We claim that as long as $\lambda^{\prime}<\frac{1}{5}\lambda$, any adversary
wins with at most negligible probability in the game. The reason is that as
long as $\lambda^{\prime}<\frac{1}{5}\lambda$, we have
$\mathbf{H}_{\min}(V|\mathsf{E})>\frac{4}{5}\lambda$, where $V$ is the random
variable for the string $v$, and $\mathsf{E}$ represents all classical and
quantum information that the adversary gets. Thus, Corollary 1 applies.

Next, we are ready to construct an adversary
$(\mathcal{P}^{\prime},\mathcal{F}_{1}^{\prime},\mathcal{F}_{2}^{\prime})$ for
the above monogamy game from an adversary
$(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})$ winning game $\mathsf{G}_{r}$
with probability $>\frac{9}{2^{r}}+1/p(\lambda)$ for some $\lambda$.
$(\mathcal{P}^{\prime},\mathcal{F}_{1}^{\prime},\mathcal{F}_{2}^{\prime})$ is
as follows:

  * •

$\mathcal{P}^{\prime}$ runs $\mathcal{P}$ on the state received from the
challenger. The output is a state on two registers: $\mathcal{P}^{\prime}$
sends the first half to $\mathcal{F}^{\prime}_{1}$ and the second half to
$\mathcal{F}^{\prime}_{2}$.

  * •

Let $q_{1}$ and $q_{2}$ be the number of oracle queries performed by the
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ algorithms. $\mathcal{F}_{1}^{\prime}$
and $\mathcal{F}_{2}^{\prime}$ respectively pick uniformly
$k\leftarrow[q_{1}]$ and $l\leftarrow[q_{2}]$. Then,
$\mathcal{F}_{1}^{\prime}$ and $\mathcal{F}_{2}^{\prime}$ respectively run the
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ algorithms for $k$ and $l$ queries,
using oracle access to $H^{w_{i}}_{v,z}$, for $i\in[r]$. Finally,
$\mathcal{F}^{\prime}_{1}$ and $\mathcal{F}^{\prime}_{2}$ measure the
respective oracle registers and return their outcomes to the challenger.

By Corollary 3, the outcome returned by $\mathcal{F}_{1}^{\prime}$ and
$\mathcal{F}_{2}^{\prime}$ is $v$ with inverse-polynomial probability.

∎

###### Proof of Lemma 17.

Combining lemmas 19 and 21, we deduce that, for any $r\geq 4$, the statement
of Lemma 17 must hold for any $\epsilon^{*}$ such that

$1-4r\sqrt{\epsilon^{*}}>\frac{10}{2^{r}}\,.$

Taking $r=5$, we deduce that the statement of Lemma 17 holds for any
$\epsilon^{*}\leq 10^{-4}$. ∎

###### Proof of Lemma 14.

Let $(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})$ be a strategy that wins
with probability $p$ in $H_{3}$. We will argue that
$(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})$ wins with probability at least
$p-\frac{2}{3}+\delta^{*}-\mathsf{negl}(\lambda)$ in $H_{4}$, where
$\delta^{*}>0$. When considering the winning probability of a strategy, we can
divide the analysis into three cases bases on what type of inputs the
challenger is challenging $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ on. Let
$\theta\in\\{0,1\\}^{m(\lambda)}$ denote the basis choice used to encode a
string $v\in\\{0,1\\}^{m(\lambda)}$. Then, in the input challenge phase,
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ receive basis choices $\theta_{1}$ and
$\theta_{2}$, respectively, according to the following distribution:

  * (i)

with probability $\frac{1}{3}$, the challenger picks uniformly random
$\theta^{\prime},\theta^{\prime\prime}\in\\{0,1\\}^{m(\lambda)}$, sends
$\theta^{\prime}$ to $\mathcal{F}_{1}$ and $\theta^{\prime\prime}$ to
$\mathcal{F}_{2}$.

  * (ii)

with probability $\frac{1}{3}$, the challenger picks a uniformly random
$\theta^{\prime}\in\\{0,1\\}^{m(\lambda)}$, sends $\theta^{\prime}$ to
$\mathcal{F}_{1}$ and the correct basis choice $\theta$ to $\mathcal{F}_{2}$.

  * (iii)

with probability $\frac{1}{3}$, the challenger picks a uniformly random
$\theta^{\prime}\in\\{0,1\\}^{\lambda}$, sends the correct basis choice
$\theta$ to $\mathcal{F}_{1}$ and $\theta^{\prime}$ to $\mathcal{F}_{2}$.

Conditioned on case (i), we argue that the winning probabilities of
$\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2}$ in $H_{3}$ and in $H_{4}$ are
negligibly close, i.e. there exists a negligible function $\nu$ such that:

$\displaystyle\Big{|}\Pr\Big{[}(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{
win in }H_{4}\,|\,\theta_{1}\text{ is random and }\theta_{2}\text{ is
random}\Big{]}$
$\displaystyle-\Pr\Big{[}(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{
win in }H_{3}\,|\,\theta_{1}\text{ is random and }\theta_{2}\text{ is
random}\Big{]}\Big{|}\leq\nu(\lambda).$ (40)

This follows from a similar argument made earlier. By an application of the
one-way-to-hiding lemma, one can bound the advantage in distinguishing $H_{3}$
from $H_{4}$ by the probability of querying at the encoded point $v$. An
adversary that queries with non-negligible probability at $v$
straightforwardly yields an adversary that wins with non-negligible
probability at the monogamy of entanglement game of Lemma 4. This implies that
the winning probability of $(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})$ in
$H_{4}$ is at least $p-\frac{2}{3}-\nu(\lambda)$.

What we will argue next is that in fact the lower bound is
$p-\frac{2}{3}+\delta^{*}-\mathsf{negl}(\lambda)$, for some $\delta^{*}>0$. We
appeal to Lemma 17, by which there exists $\epsilon^{*}>0$ (where we can take
$\epsilon^{*}=10^{-4}$), and a negligible function $\mu$, such that for all
$\lambda$, there exists an $i\in\\{1,2\\}$ such that $\mathcal{F}_{i}$
satisfies

$\displaystyle\Big{|}\Pr$ $\displaystyle[\mathcal{F}_{i}\text{ returns 1 in
}H_{4}\,|\,\theta_{i}\text{ is correct }]$
$\displaystyle-\Pr[\mathcal{F}_{i}\text{ returns 1 in
}H_{3}\,|\,\theta_{i}\text{ is
correct}]\Big{|}<1-\epsilon^{*}+\mu(\lambda)\,.$ (41)

Fix a $\lambda$, and assume (5.1) holds for $i=1$ for this particular
$\lambda$ (the other case being analogous).

We consider the two cases:

  * (a)

$\Pr[(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{ win in
}H_{3}\,|\,\theta_{1}\text{ is correct and }\theta_{2}\text{ is
random}]>1-\frac{\epsilon^{*}}{3}\,.$ (42)

  * (b)

$\Pr[(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{ win in
}H_{3}\,|\,\theta_{1}\text{ is a correct and }\theta_{2}\text{ is random}]\leq
1-\frac{\epsilon^{*}}{3}\,.$ (43)

We start by assuming (a). Then, Equation (5.1) implies that

$\Pr[\mathcal{F}_{1}\text{ returns 1 in }H_{4}\,|\,\theta_{1}\text{ is
correct}]>\frac{2\epsilon^{*}}{3}-\mu(\lambda)\,,$ (44)

where we are using the fact that the correlation generated by
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ is non-signalling to remove the
condition of $\theta_{2}$ being random.

By the same argument used for case (i), notice that

$|\Pr[\mathcal{F}_{2}\text{ returns 0 in }H_{3}\,|\,\theta_{2}\text{ is random
}]-\Pr[\mathcal{F}_{2}\text{ returns 0 in }H_{4}\,|\,\theta_{2}\text{ is
random }]|\leq\mathsf{negl}(\lambda)\,.$

Then, Equation (42) implies

$\Pr[\mathcal{F}_{2}\text{ returns 0 in }H_{4}\,|\,\theta_{2}\text{ is
random}]>1-\frac{\epsilon^{*}}{3}-\mathsf{negl}(\lambda)\,,$ (45)

where we again use the fact that the correlation generated by
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ is non-signalling.

Combining (44) and (45), and using a union bound implies that

$\Pr[(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{ win in
}H_{4}\,|\,\theta_{1}\text{ is correct and }\theta_{2}\text{ is
random}]>\frac{\epsilon^{*}}{3}-\mathsf{negl}(\lambda)\,.$ (46)

Thus, Equations (42) and (46) trivially imply that

$\displaystyle\Pr[(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{ win in
}H_{4}\,|\,\theta_{1}\text{ is correct and }\theta_{2}\text{ is random}]$
$\displaystyle>\Pr[(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{ win in
}H_{3}\,|\,\theta_{1}\text{ is correct and }\theta_{2}\text{ is
random}]-\left(1-\frac{\epsilon^{*}}{3}\right)-\mathsf{negl}(\lambda)\,.$ (47)

Now, equations (5.1) and (5.1) imply:

$\displaystyle\Pr[(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{ win in
}H_{4}]$
$\displaystyle=\frac{1}{3}\Pr\big{[}(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{
win in }H_{4}\,|\,\theta_{1}\text{ is random and }\theta_{2}\text{ is
random}\big{]}$
$\displaystyle+\frac{1}{3}\Pr\big{[}(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{
win in }H_{4}\,|\,\theta_{1}\text{ is correct and }\theta_{2}\text{ is
random}\big{]}$
$\displaystyle+\frac{1}{3}\Pr\big{[}(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{
win in }H_{4}\,|\,\theta_{1}\text{ is random and }\theta_{2}\text{ is
correct}\big{]}$
$\displaystyle>\frac{1}{3}\Pr\big{[}(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{
win in }H_{3}\,|\,\theta_{1}\text{ is random and }\theta_{2}\text{ is
random}\big{]}$
$\displaystyle+\frac{1}{3}\left(\Pr\big{[}(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{
win in }H_{3}\,|\,\theta_{1}\text{ is correct and }\theta_{2}\text{ is a
random}\big{]}-1+\frac{\epsilon^{*}}{3}\right)$
$\displaystyle+\frac{1}{3}\left(\Pr\big{[}(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{
win in }H_{3}\,|\,\theta_{1}\text{ is random and }\theta_{2}\text{ is
correct}\big{]}-1\right)-\mathsf{negl}(\lambda)$
$\displaystyle=p-\frac{2}{3}+\frac{\epsilon^{*}}{9}-\mathsf{negl}(\lambda)\,.$
(48)

Now, instead, we assume (b), i.e.

$\Pr\big{[}(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{ win in
}H_{3}\,|\,\theta_{1}\text{ is correct and }\theta_{2}\text{ is
random}\big{]}\leq 1-\frac{\epsilon^{*}}{3}\,.$ (49)

Then, we immediately have

$\displaystyle\Pr\big{[}(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{
win in }H_{4}\,|\,\theta_{1}\text{ is correct and }\theta_{2}\text{ is
random}\big{]}$
$\displaystyle>\Pr\big{[}(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{
win in }H_{3}\,|\,\theta_{1}\text{ is correct and }\theta_{2}\text{ is
random}\big{]}-\left(1-\frac{\epsilon^{*}}{3}\right)\,.$ (50)

A similar calculation to Equation (48) gives

$\Pr\big{[}(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{ win in
}H_{4}\big{]}>p-\frac{2}{3}+\frac{\epsilon^{*}}{9}-\mathsf{negl}(\lambda)\,.$
(51)

This gives the desired bound with $\delta^{*}=\frac{\epsilon^{*}}{9}$.

∎

This concludes the proof of Lemma 14, and hence of Theorem 4.

###  5.2 Proof of quantum virtual black-box obfuscation

In this section, we show that our quantum copy-protection scheme for point
functions is also a quantum virtual black-box ($\mathsf{VBB}$) obfuscator
[AF16]. In particular, we will show that the algorithm $\mathsf{CP.Protect}$
from Construction 3 satisfies a notion of obfuscation called _distributional
indistinguishability_ , which for evasive classes of circuits is equivalent to
$\mathsf{VBB}$ obfuscation [WZ17] (it is straightforward to see that
distributional indistinguishability implies VBB - the reverse implication
requires slightly more work). $\mathsf{CP.Protect}$ is already functionality
preserving, this follows from the definition of a copy-protection scheme. All
that is left to show is security. In what follows, we assume that a program
has an associated set of parameters $P.\mathsf{params}$ (input size, output
size, circuit size) which we are not required to hide.

######  Definition 8 (Distributional indistinguishability).

An obfuscator $\mathsf{Obf}$ for the class of distributions $\mathcal{D}$ over
programs $\mathcal{C}$, satisfies distributional indistinguishability if there
exists a $\mathsf{QPT}$ simulator $\mathsf{Sim}$, such that for every
distribution ensemble $D=\\{D_{\lambda}\\}\in\mathcal{D}$, we have

$\mathbb{E}_{P\leftarrow
D_{\lambda}}\mathsf{Obf}(1^{\lambda},P)\,\approx_{c}\,\mathsf{Sim}(1^{\lambda},P.\mathsf{params})\,.$
(52)

(where the notation “$\approx_{c}$” was introduced in Definition 1.) We remark
that the notion of indistinguishability of ensembles of quantum states
(Definition 1) already accounts for auxiliary quantum information in the two
ensembles.

Distributional indistinguishability relative to any oracle is analogous to
Definition 8, except that the algorithms $\mathsf{Obf}$ and $\mathsf{Sim}$ are
quantum oracle algorithms, and the notation “$\approx_{c}$” refers to
Definition 2.

######  Theorem 5.

The $\mathsf{QPT}$ algorithm $\mathsf{CP.Protect}$ from Construction 3
satisfies distributional indistinguishability in the QROM for the class of
distributions $\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{UNP}}$.

###### Proof.

We define the following simulator $\mathsf{Sim}$:

  * •

$\mathsf{Sim}$ takes as input $1^{\lambda}$, an auxiliary state $\nu$, and
outputs the state: $\frac{\mathds{1}}{2^{m(\lambda)+\lambda}}\otimes\nu$,
where the first factor is the maximally mixed state on $m(\lambda)+\lambda$
qubits.

Let

$\rho_{\lambda,G,H}:=\mathbb{E}_{P_{y}\leftarrow
D_{\lambda}}\mathsf{CP.Protect}^{G,H}(1^{\lambda},P_{y})=\mathbb{E}_{P_{y}\leftarrow
D_{\lambda}}\mathbb{E}_{v}\ket{v^{G(y)}}\bra{v^{G(y)}}\otimes\ket{H(v)}\bra{H(v)}\,,$

and

$\sigma_{\lambda,H}:=\mathbb{E}_{\theta}\mathbb{E}_{v}\ket{v^{\theta}}\bra{v^{\theta}}\otimes\ket{H(v)}\bra{H(v)}\,.$

By an argument analogous to that of the proof of Lemma 12, it holds that, for
any computationally bounded oracle adversary $\mathcal{A}$, and any auxiliary
state $\nu_{\lambda}$,

$\mathbb{E}_{G,H}\big{|}\Pr[\mathcal{A}^{G,H}(\rho_{\lambda,G,H}\otimes\nu_{\lambda})=1]-\Pr[\mathcal{A}^{G,H}(\sigma_{\lambda,H}\otimes\nu_{\lambda})=1]\big{|}=\mathsf{negl}(\lambda)\,.$

Next, we replace the state $\sigma_{\lambda,H}$ with the state
$\sigma^{\prime}_{\lambda}:=\mathbb{E}_{\theta}\mathbb{E}_{v}\mathbb{E}_{z}\ket{v^{\theta}}\bra{v^{\theta}}\otimes\ket{z}\bra{z}$.
We argue that for any query bounded adversary $\mathcal{A}$, the following
holds:

$\mathbb{E}_{H}\big{|}\Pr[\mathcal{A}^{H}(\sigma_{\lambda,H}\otimes\nu_{\lambda})=1]-\Pr[\mathcal{A}^{H}(\sigma^{\prime}_{\lambda}\otimes\nu_{\lambda})=1]\big{|}=\mathsf{negl}(\lambda)\,.$
(53)

Let $\mathcal{A}$ be a distinguisher making $q$ queries. Without loss of
generality, let $\mathcal{A}$ be specified by the unitary $(UO^{H})^{q}$, for
some unitary $U$.

We apply one-way-to-hiding (Lemma 7) to deduce that the LHS of (53) is
negligible if the quantity

$\mathbb{E}_{H}\mathbb{E}_{v}\mathbb{E}_{\theta}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\mathbb{E}_{k}\mbox{$\mathrm{Tr}\Big{[}\ket{v}\bra{v}(UO^{H})^{k}\left(\ket{v^{\theta}}\bra{v^{\theta}}\otimes\ket{z}\bra{z}\otimes\nu_{\lambda}\right)(UO^{H})^{k}\Big{]}$}$

is negligible.

Suppose for a contradiction the latter is not negligible. Then, we can
construct an adversary that wins at the monogamy of entanglement game of Lemma
4. The reduction is straightforward: the adversary for the monogamy of
entanglement game prepares the auxiliary state $\nu_{\lambda}$, and runs
$\mathcal{A}$ (by simulating an oracle) to extract $v$. Then sends $v$ to both
$\mathcal{B}$ and $\mathcal{C}$ (using the notation for the monogamy game of
Lemma 4).

The conclusion of the theorem follows by observing that
$\sigma^{\prime}_{\lambda}$ is the maximally mixed state. ∎

##  6 Extension to compute-and-compare programs

In this section, we show that a quantum copy-protection scheme for point
functions, which is secure with respect to the appropriate program and
challenge ensembles, implies a quantum copy-protection scheme for compute-and-
compare programs with the same level of security.

The idea is simple: to copy-protect the compute-and-compare program
$\mathsf{CC}[f,y]$, we copy-protect the point function $P_{y}$, and give $f$
in the clear. By copy-protecting $P_{y}$ we are copy-protecting the portion of
the compute-and-compare program which checks equality with $y$. The intuition
is that this is sufficient to make the functionality unclonable because its
output is not already determined by $f$. More generally, one might suspect
that, for copy-protecting a function $F=f_{1}\circ f_{2}...\circ f_{\ell}$, it
should be sufficient to copy-protect any of the functions $f_{i}$ that is
sufficiently non-constant _within its context_.

Let
$(\mathsf{CP}\mbox{-}\mathsf{PF.Protect},\mathsf{CP}\mbox{-}\mathsf{PF.Eval})$
be a copy-protection scheme for point functions.

######  Construction 4 (Copy-protection scheme for compute-and-compare
programs).

The copy-protection scheme for compute-and-compare programs
$(\mathsf{CP}\mbox{-}\mathsf{CC.Protect},\mathsf{CP}\mbox{-}\mathsf{CC.Eval})$
is defined as follows:

  * •

$\mathsf{CP}\mbox{-}\mathsf{CC.Protect}(1^{\lambda},(f,y))$: Takes as input a
security parameter $\lambda$ and a compute-and-compare program
$\mathsf{CC}[f,y]$, specified succinctly by $f$ and $y$. Then,

    * –

Let $\rho=\mathsf{CP}\mbox{-}\mathsf{PF.Protect}(\lambda,y))$.

    * –

Output $(f,\rho)$.

  * •

$\mathsf{CP}\mbox{-}\mathsf{CC.Eval}(1^{\lambda},(f,\rho);x)$: Takes as input
a security parameter $\lambda$, an alleged copy-protected program $(f,\rho)$,
and a string $x\in\\{0,1\\}^{n}$ (where $n$ is the size of the inputs to $f$).
Then,

    * –

Compute $y^{\prime}=f(x)$.

    * –

Let $b\leftarrow\mathsf{CP}\mbox{-}\mathsf{PF.Eval}(\rho;y^{\prime})$. Output
$b$.

Recall the definition of the class of distributions over point functions
$\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{UNP}}$ from Section 5. We define a
related class of distributions over compute-and-compare programs.

  * •

$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{UNP}}$. We refer to this class as the
class of unpredictable compute-and-compare programs. This consists of
ensembles $D=\\{D_{\lambda}\\}$ where $D_{\lambda}$ is a distribution over
compute-and-compare programs such that $\mathsf{CC}[f,y]\leftarrow
D_{\lambda}$ satisfies $\mathbf{H}_{\min}(y|f)\geq\lambda^{\epsilon}$ for some
$\epsilon>0$, and where the input length of $f$ is $\lambda$ and the output
length is bounded by some polynomial $t(\lambda)$.

We also define the following class of distributions over input challenges:

  * •

$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{Chall}}$. An ensemble
$D=\\{D_{f,y}\\}$, where each $D_{f,y}$ is a distribution over pairs of
elements in the domain of $f$, belongs to the class
$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{Chall}}$ if there exists an
efficiently sampleable family $\\{X_{\lambda}\\}$ of distributions over
$\\{0,1\\}^{\lambda}$ with
$\mathbf{H}_{\min}(X_{\lambda})\geq\lambda^{\epsilon}$, for some $\epsilon>0$,
and an efficiently sampleable family $\\{Z_{f,y}\\}$, where $Z_{f,y}$ is a
distribution over the set $f^{-1}(y)$, such that $D_{f,y}$ is the following
distribution (where $\lambda$ is the size of inputs to $f$):

    * –

With probability $1/3$, sample $z\leftarrow Z_{f,y}$ and $x\leftarrow
X_{\lambda}$, and output $(x,z)$.

    * –

With probability $1/3$, sample $z\leftarrow Z_{f,y}$ and $x\leftarrow
X_{\lambda}$, and output $(z,x)$.

    * –

With probability $1/3$, sample $x,x^{\prime}\leftarrow X_{\lambda}$, and
output $(x,x^{\prime})$.

We say the ensemble $D$ is _specified_ by the families $\\{X_{\lambda}\\}$ and
$\\{Z_{f,y}\\}$.

Just like in the point function case, we also define two classes of
distributions over pairs of programs and challenges.

  * •

$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}}.$ This
consists of pairs of ensembles
$\left(D=\\{D_{\lambda}\\},D^{\prime}=\\{D^{\prime}_{f,y}\\}\right)$ where
$D\in\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{UNP}}$ and
$D^{\prime}\in\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{Chall}}$ satisfying the
following. Let $D^{\prime}$ be parametrized by the families
$\\{X_{\lambda}\\}$ and $\\{Z_{f,y}\\}$ (following the notation introduced
above), and denote by
$\mathsf{MarkedInput}\left(D_{\lambda},\\{Z_{f,y}\\}\right)$ the distribution
over $\\{0,1\\}^{\lambda}$ induced by $D_{\lambda}$ and $\\{Z_{f,y}\\}$, i.e.:

    * –

Sample $(f,y)\leftarrow D_{\lambda}$, then $z\leftarrow Z_{f,y}$.

For any fixed $f_{*}$ with domain $\\{0,1\\}^{\lambda}$ such that
$(f_{*},y_{*})$ is in the support of $D_{\lambda}$ for some $y_{*}$, denote by
$\mathsf{MarkedInput}(D_{\lambda},\\{Z_{f,y}\\})|_{f_{*}}$, the distribution
$\mathsf{MarkedInput}(D_{\lambda},\\{Z_{f,y}\\})$ conditioned on $D_{\lambda}$
sampling $f_{*}$. Then, we require that, for any sequence
$\\{f_{*}^{(\lambda)}\\}$ (where, for all $\lambda$,
$(f_{*}^{(\lambda)},y_{*})$ is in the support of $D_{\lambda}$ for some
$y_{*}$), the families $\\{X_{\lambda}\\}$ and
$\\{\mathsf{MarkedInput}(D_{\lambda},\\{Z_{f,y}\\})|_{f_{*}^{(\lambda)}}\\}$
are statistically indistinguishable.

  * •

$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{comp}}.$ This
is defined in the same way as
$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}}$, except
that we only require $\\{X_{\lambda}\\}$ and
$\\{\mathsf{MarkedInput}(D_{\lambda},\\{Z_{f,y}\\})|_{f_{*}^{(\lambda)}}\\}$
to be _computationally_ indistinguishable.

######  Theorem 6.

Let
$(\mathsf{CP}\mbox{-}\mathsf{PF.Protect},\mathsf{CP}\mbox{-}\mathsf{PF.Eval})$
be a copy-protection scheme for point functions that is $\delta$-secure with
respect to all pairs
$(D,D^{\prime})\in\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}}$
($\in\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{comp}}$).
Then, the scheme of Construction 4, instantiated with
$(\mathsf{CP}\mbox{-}\mathsf{PF.Protect},\mathsf{CP}\mbox{-}\mathsf{PF.Eval})$,
is a $\delta$-secure copy-protection scheme for compute-and-compare programs
with respect to all pairs
$(D,D^{\prime})\in\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}}$
($\in\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{comp}}$).
The same conclusion holds relative to any oracle, i.e. when all algorithms
have access to the same oracle, with respect to query-bounded (computationally
bounded) adversaries.

###### Proof.

We prove the theorem for the case of
$\left(\\{D_{\lambda}\\},\\{D_{f,y}\\}\right)\in\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}}$
(the case of
$\left(\\{D_{\lambda}\\},\\{D_{f,y}\\}\right)\in\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{comp}}$
being virtually identical). Let $t(\lambda)$ be the length of strings in the
range of $f$’s sampled from $D_{\lambda}$. Let the ensemble $\\{D_{f,y}\\}$ be
specified by $\\{Z_{f,y}\\}$ and $\\{X_{\lambda}\\}$ (using the notation
introduced above for ensembles in
$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{Chall}}$).

Let $\mathcal{A}=(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})$ be an
adversary for the compute-and-compare copy-protection scheme of Construction 4
with respect to ensembles $\\{D_{\lambda}\\}$ and $\\{D_{f,y}\\}$. Suppose
$\mathcal{A}$ wins with probability $p(\lambda)>0$. It follows that for each
$\lambda$ there exists $f_{*}^{(\lambda)}$ such that $(f_{*}^{(\lambda)},y)$
is in the support of $D_{\lambda}$ for some $y$, and the probability that
$\mathcal{A}$ wins is at least $p(\lambda)$, conditioned on $f^{(\lambda)}$
being sampled.

We will construct an adversary $\mathcal{A}^{\prime}$ that wins with
probability $p(\lambda)-\mathsf{negl}(\lambda)$ in the point function security
game with respect to $\\{D^{\prime}_{t(\lambda)}\\}$ and
$\\{D^{\prime}_{y}\\}$, defined as follows:

  * •

$D^{\prime}_{t(\lambda)}$: sample $x\leftarrow X_{\lambda}$ and output the
point function $P_{f^{(\lambda)}_{*}(x)}$.

  * •

$D^{\prime}_{y}$: sample $(x,x^{\prime})\leftarrow D_{f_{*}^{(\lambda)},y}$
and output $(f_{*}^{(\lambda)}(x),f_{*}^{(\lambda)}(x^{\prime}))$.

The adversary
$\mathcal{A}^{\prime}=(\mathcal{P}^{\prime},\mathcal{F}_{1}^{\prime},\mathcal{F}_{2}^{\prime})$
then acts as follows:

  * •

$\mathcal{P}^{\prime}$ receives as input a state $\rho$. Then,
$\mathcal{P}^{\prime}$ provides $(f_{*}^{(\lambda)},\rho)$ as input to
$\mathcal{P}$. Let $\textsf{A}_{1}$ and $\textsf{A}_{2}$ be the registers
returned by $\mathcal{P}$. $\mathcal{P}^{\prime}$ forwards $\textsf{A}_{1}$
and $\textsf{A}_{2}$ to $\mathcal{F}_{1}^{\prime}$ and
$\mathcal{F}_{2}^{\prime}$ respectively.

  * •

Upon receiving a challenge $x_{i}$, $\mathcal{F}_{i}^{\prime}$ samples
$x_{i}^{\prime}\leftarrow Z_{f,x_{i}}$. $\mathcal{F}_{i}^{\prime}$ then runs
$\mathcal{F}_{i}$ on input $x^{\prime}_{i}$ and the register $\textsf{A}_{i}$.
Let $b_{i}$ be the output returned by $\mathcal{F}_{i}$.
$\mathcal{F}_{i}^{\prime}$ returns $b_{i}$ to the challenger.

It is straightforward to check that the game “simulated” by
$(\mathcal{P}^{\prime},\mathcal{F}_{1}^{\prime},\mathcal{F}_{2}^{\prime})$ for
$(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})$ is statistically
indistinguishable from a security game with respect to $\\{D_{\lambda}\\}$ and
$\\{D_{f,y}\\}$, conditioned on $f^{(\lambda)}_{*}$. Thus, we deduce, by
hypothesis, that $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ both return the
correct bits with probability at least $p(\lambda)-\mathsf{negl}(\lambda)$,
and thus
$(\mathcal{P}^{\prime},\mathcal{F}_{1}^{\prime},\mathcal{F}_{2}^{\prime})$
wins with probability at least $p(\lambda)-\mathsf{negl}(\lambda)$. Crucially,
note that
$\left(\\{D^{\prime}_{t(\lambda)}\\},\\{D^{\prime}_{y}\\}\right)\in\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}}$.
It follows that if the point function copy-protection scheme is
$\delta$-secure, then the compute-and-compare copy-protection scheme must also
be $\delta$-secure. It is easy to check that all steps of the proof also hold
relative to an oracle. ∎

######  Corollary 4.

Let $\delta^{*}>0$ be the constant from Theorem 4. There exists a
$\delta^{*}$-secure copy-protection scheme for compute-and-compare programs
with respect to ensembles
$(D,D^{\prime})\in\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}}$
($\in\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{comp}}$)
against query-bounded adversaries (computationally bounded adversaries,
assuming the existence of quantum-secure one-way functions).

###### Proof.

Combining Theorem 4 with Theorem 6 immediately gives this corollary. ∎

##  7 Secure software leasing

Recall that the level of security achieved by our copy-protection scheme in
Theorem 4 is far from ideal (our security guarantees that the freeloaders fail
at least with some constant probability at simultaneously answering
correctly). In this section, we show that our construction (augmented with a
verification routine) satisfies a weaker notion of copy-protection called
“secure software leasing” $(\mathsf{SSL})$, introduced in [ALP20], but with a
standard level of security, i.e. the adversarial advantage is negligible in
the security parameter.

We formalize the notion of $\mathsf{SSL}$.

######  Definition 9 (Secure software leasing).

Let $\mathcal{C}$ be a family of classical circuits with a single bit output.
A secure software leasing $(\mathsf{SSL})$ scheme
$(\mathsf{SSL}.\mathsf{Gen},\mathsf{SSL}.\mathsf{Lease},\mathsf{SSL}.\mathsf{Eval},\mathsf{SSL}.\mathsf{Verify})$
consists of the following $\mathsf{QPT}$ algorithms:

  * •

$\mathsf{SSL}.\mathsf{Gen}(1^{\lambda})$ takes as input the security parameter
$\lambda$ and outputs a secret key $\mathsf{sk}$.

  * •

$\mathsf{SSL}.\mathsf{Lease}(\mathsf{sk},C)$ takes as input a secret key
$\mathsf{sk}$ and a circuit $C\in\mathcal{C}$ with input size $n$, and outputs
a quantum state $\rho_{C}$.

  * •

$\mathsf{SSL}.\mathsf{Eval}(x,\rho_{C})$ takes a string $x$ as input to $C$
together with a state $\rho_{C}$, and outputs a bit and a post-evaluation
state $\tilde{\rho}_{C}$.

  * •

$\mathsf{SSL}.\mathsf{Verify}(\mathsf{sk},C,\sigma)$ takes as input the secret
key $\mathsf{sk}$, the circuit $C\in\mathcal{C}$ and a state $\sigma$, and
outputs $1$, if $\sigma$ is a valid lease state for $C$, and $0$ otherwise.

There exists a negligible function $\mu$ such that the scheme satisfies:

  * •

Correctness of evaluation: for all $\lambda$, for all $C\in\mathcal{C}$, and
for all $x$ in the domain of $C$,

$\Pr\big{[}\mathsf{SSL}.\mathsf{Eval}(x,\rho)=C(x):\rho\leftarrow\mathsf{SSL}.\mathsf{Lease}(\mathsf{sk},C),\,\mathsf{sk}\leftarrow\mathsf{SSL}.\mathsf{Gen}(1^{\lambda})\big{]}\geq
1-\mu(\lambda).\quad\quad\quad\quad\quad\quad\quad\,\,\,$

  * •

Correctness of verification: for all $\lambda$, for all $C\in\mathcal{C}$, and
for all $x$ in the domain of $C$,

$\Pr\big{[}\mathsf{SSL}.\mathsf{Verify}(\mathsf{sk},C,\rho)=1:\rho\leftarrow\mathsf{SSL}.\mathsf{Lease}(\mathsf{sk},C),\,\mathsf{sk}\leftarrow\mathsf{SSL}.\mathsf{Gen}(1^{\lambda})\big{]}\geq
1-\mu(\lambda).$

Security is defined in terms of a security game between a lessor and an
adversary $\mathcal{A}$ (the lessee). Informally, any secure software leasing
($\mathsf{SSL}$) scheme should satisfy the following key property. After
receiving a leased copy of $C$ denoted by $\rho_{C}$ (generated using
$\mathsf{SSL}.\mathsf{Lease}$), the adversary should not be able to produce a
quantum state $\sigma$ on registers $\mathsf{R}_{1}$ and $\mathsf{R}_{2}$ such
that:

  * •

$\mathsf{SSL}.\mathsf{Verify}$ deems the contents of register $\mathsf{R}_{1}$
of $\sigma_{\mathsf{R_{1}R_{2}}}$ to be valid, once it is returned.

  * •

The adversary can still compute $C$ (on inputs chosen by the lessor) from the
post-measurement state in register $\mathsf{R_{2}}$ given by
$\sigma_{\mathsf{R_{2}}}^{*}\propto\mathrm{Tr}_{\mathsf{R_{1}}}\big{[}\Pi_{1}\big{[}\big{(}\mathsf{SSL}.\mathsf{Verify}(\cdot)_{\mathsf{R_{1}}}\otimes\mathds{1}_{\mathsf{R_{2}}}\big{)}\sigma_{\mathsf{R_{1}R_{2}}}\big{]}\big{]}$.

As in the case of copy protection, the security game is specified by a
security parameter $\lambda$, a distribution $D_{\lambda}$ over circuits $C$
from $\mathcal{C}$, and a family of distributions
$\\{D_{C}\\}_{C\in\mathcal{C}}$ over inputs to $C$. The game proceeds as
follows:

  * •

The lessor samples a circuit $C\leftarrow D_{\lambda}$ and runs
$\mathsf{sk}\leftarrow\mathsf{SSL}.\mathsf{Gen}(1^{\lambda})$. Then, the
lessor runs $\rho\leftarrow\mathsf{SSL}.\mathsf{Lease}(\mathsf{sk},C)$. The
lessor sends $\rho$ to $\mathcal{A}$.

  * •

$\mathcal{A}$ outputs a (possibly entangled) state $\sigma$ on two registers
$\mathsf{R}_{1}$ and $\mathsf{R}_{2}$, and then sends the first register
$\mathsf{R}_{1}$ to the lessor.

  * •

For verification, the lessor runs $\mathsf{SSL}.\mathsf{Verify}$ on input the
secret key $\mathsf{sk}$, the circuit $C\in\mathcal{C}$ and the register
$\mathsf{R}_{1}$ of the state $\sigma_{\mathsf{R}_{1}\mathsf{R}_{2}}$. If
$\mathsf{SSL}.\mathsf{Verify}$ accepts, the lessor outputs $\mathsf{ok}=1$ and
lets the game continue, otherwise, the lessor outputs $\mathsf{ok}=0$ and
$\mathcal{A}$ loses.

  * •

The lessor samples $x\leftarrow\mathcal{D}_{C}$, and sends $x$ to the
adversary.

  * •

$\mathcal{A}$ responds with a bit $b$. If $b=C(x)$, the lessor outputs $1$.
Otherwise, the lessor outputs $0$.

We let $\mathsf{SSLGame}(\lambda,\mathcal{A},D_{\lambda},\\{D_{C}\\})$ denote
a random variable that is equal to $1$, if the above security game is won, and
$0$ otherwise.

As in the case of full copy protection, we define the trivial winning
probability, which in the case of $\mathsf{SSL}$ is just the straightforward
guessing probability for the answer to the challenge,

$p^{\mathrm{triv},\mathsf{SSL}}_{D_{\lambda},\\{D_{C}\\}_{C\in\mathcal{C}}}=\max_{b\in\\{0,1\\}}\mathbb{E}_{C\leftarrow
D_{\lambda}}\hat{D}_{C}(b),$ (54)

where $\hat{D}_{C}(b)$ is the probability that the correct answer to a
challenge sampled from $D_{C}$ is $b$.

######  Definition 10 (Security).

A secure software leasing $(\mathsf{SSL})$ scheme for a family of classical
circuits $\mathcal{C}=\\{C_{\lambda}\\}_{\lambda\in\mathbb{N}}$ is said to be
$\delta$-secure with respect to the ensemble
$D=\\{D_{\lambda}\\}_{\lambda\in\mathbb{N}}$ of distributions over circuits in
$\mathcal{C}$, and with respect to the ensemble
$\\{D_{C}\\}_{C\in\mathcal{C}}$, where $D_{C}$ is a distribution over
challenge inputs to program $C$, if for any $\lambda\in\mathbb{N}$ and any
$\mathsf{QPT}$ adversary $\mathcal{A}$,

$\Pr[\mathsf{SSLGame}(\lambda,\mathcal{A},D_{\lambda},\\{D_{C}\\})=1]\leq
1-\delta(\lambda)+\mathsf{negl}(\lambda)\,.$

If
$\delta(\lambda)=1-p^{\mathrm{triv},\mathsf{SSL}}_{D_{\lambda},\\{D_{C}\\}_{C\in\mathcal{C}}}$,
we simply call the scheme secure.

We refer to $D=\\{D_{\lambda}\\}_{\lambda\in\mathbb{N}}$ as the program
ensemble, and to $\\{D_{C}\\}_{C\in\mathcal{C}}$ as the input challenge
ensemble.

###  7.1 Secure software leasing for point functions

We first consider a version of the scheme for point functions in Construction
3, augmented with a verification procedure. Then, in Section 7.3, we extend
the scheme to the class of compute-and-compare programs, in a similar way as
in the case of copy-protection. Again, for simplicity, we hand the marked
input $y\in\\{0,1\\}^{n}$ to the leasing algorithm as an input, rather than a
circuit for the point function $P_{y}$ itself. We also omit the procedure
$\mathsf{SSL}.\mathsf{Gen}$ as we do not require it in our construction.

######  Construction 5 ($\mathsf{SSL}$ scheme for point functions).

Let $\lambda$ be the security parameter, and let
$H:\\{0,1\\}^{m(\lambda)}\rightarrow\\{0,1\\}^{\lambda}$ and
$G:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{m(\lambda)}$ be hash functions, where
$m(\lambda)\geq\lambda$. Consider the following secure software leasing
$(\mathsf{SSL})$ scheme
$(\mathsf{SSL}.\mathsf{Lease},\mathsf{SSL}.\mathsf{Eval},\mathsf{SSL}.\mathsf{Verify})$
for point functions $P_{y}$ with marked input $y\in\\{0,1\\}^{n}$:

  * •

$\mathsf{SSL}.\mathsf{Lease}(1^{\lambda},y)$: Takes as input a security
parameter $\lambda$ and a point function $P_{y}$, succinctly specified by the
marked input $y$ (of size $n$)

    * –

Set $\theta=G(y)$.

    * –

Sample $v\leftarrow\\{0,1\\}^{m(\lambda)}$ uniformly at random and let
$z=H(v)$.

    * –

Output $(\ket{v^{\theta}},z)$.

  * •

$\mathsf{SSL}.\mathsf{Eval}(1^{\lambda},(\rho,z);x)$: Takes as input a
security parameter $\lambda$, a program $(\rho,z)$, and a string
$x\in\\{0,1\\}^{n}$ (the input on which the program is to be evaluated).

    * –

Set $\theta^{\prime}=G(x)$.

    * –

Apply Hadamards
$H^{\theta^{\prime}}=H^{\theta^{\prime}_{1}}\otimes\dots\otimes
H^{\theta^{\prime}_{\lambda}}$ to $\rho$. Append $n+1$ ancillary qubits, all
in state $\ket{0}$, and compute the hash function $H$ with input $\rho$ into
the first $n$ of them (possibly making use of additional ancillary qubits).
Then, coherently measure whether the first $n$ ancilla qubits are in state
$\ket{z}$, recording the result in the last ancilla qubit, uncompute the hash
function $H$ and undo the Hadamards $H^{\theta^{\prime}}$. Finally, measure
the last ancilla qubit to obtain a bit $b$ as output.

  * •

$\mathsf{SSL}.\mathsf{Verify}(1^{\lambda},y,z,\sigma)$: Apply $H^{\theta}$ to
the input state $\sigma$, where $\theta=G(y)$, and measure in the standard
basis. Output $1$ if the result is $v$ such that $H(v)=z$, and $0$ otherwise.

The correctness property of Construction 5 according to Definition 9 is
immediate to verify. Before stating our main theorem on the security of
Construction 5, we recall the following class of distributions over point
functions, which was defined in Section 5.

  * •

$\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{UNP}}$. The class of unpredictable
point function distributions $\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{UNP}}$
consists of ensembles $D=\\{D_{\lambda}\\}$ where $D_{\lambda}$ is a
distribution over point functions on $\\{0,1\\}^{\lambda}$ such that
$P_{y}\leftarrow D_{\lambda}$ satisfies
$\mathbf{H}_{\min}(y)\geq\lambda^{\epsilon}$ for some $\epsilon>0$.

We also define the following class of distributions over input challenges.

  * •

$\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{Chall}\mbox{-}\mathsf{SSL}}$. An
ensemble $D=\\{D_{y}\\}$, where each $D_{y}$ is a distribution over
$\\{0,1\\}^{|y|}$, belongs to the class
$\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{Chall}\mbox{-}\mathsf{SSL}}$ if there
exists an efficiently sampleable family $\\{X_{\lambda}\\}$ of distributions
over $\\{0,1\\}^{\lambda}$ with
$\mathbf{H}_{\min}(X_{\lambda})\geq\lambda^{\epsilon}$, for some $\epsilon>0$,
such that $D_{y}$ is the following distribution (where $\lambda=|y|$):

    * –

with probability $1/2$, output $y$.

    * –

with probability $1/2$, sample $x\leftarrow X_{\lambda}$, and output $x$.

We say the ensemble $D$ is _specified_ by the ensemble $X_{\lambda}$.

We finally define two classes of distributions over pairs of programs and
challenges.

  * •

$\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}\mbox{-}\mathsf{SSL}}.$
This consists of pairs of ensembles
$\left(D=\\{D_{\lambda}\\},D^{\prime}=\\{D^{\prime}_{y}\\}\right)$ where
$D\in\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{UNP}}$ and
$D^{\prime}\in\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{Chall}\mbox{-}\mathsf{SSL}}$
satisfying the following. Let $D^{\prime}$ be parametrized by the family
$\\{X_{\lambda}\\}$ (following the notation introduced above), and denote by
$\mathsf{MarkedInput}(D_{\lambda})$ the distribution over marked points in
$\\{0,1\\}^{\lambda}$ induced by $D_{\lambda}$. Then, the families
$\\{X_{\lambda}\\}$ and $\\{\mathsf{MarkedInput}(D_{\lambda})\\}$ are
statistically indistinguishable.

  * •

$\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{comp}\mbox{-}\mathsf{SSL}}.$
This is defined in the same way as
$\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}\mbox{-}\mathsf{SSL}}$,
except that we only require $\\{X_{\lambda}\\}$ and
$\\{\mathsf{MarkedInput}(D_{\lambda})\\}$ to be _computationally_
indistinguishable.

The following is our main result on the security of Construction 5.

######  Theorem 7.

The scheme of Construction 5, with $m(\lambda)=\mathsf{poly}(\lambda)$, is a
secure software leasing scheme for point functions with respect to any pair of
ensembles
$(D,D^{\prime})\in\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}\mbox{-}\mathsf{SSL}}$
($\in\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{comp}\mbox{-}\mathsf{SSL}}$),
against query-bounded (computationally bounded) adversaries in the quantum
random oracle model.

Theorem 7 implies that, once a leased copy is successfully returned to the
lessor, no adversary can distinguish the marked input of a point function from
a random (non-marked) input with probability better than $1/2$, except for a
negligible advantage (in the parameter $\lambda$).

We give a proof of Theorem 7 in the next section.

###  7.2 Proof of security

To prove the theorem, we rely on a few technical results.

######  Lemma 22.

Let $\alpha\in\mathbb{C}^{n}$ and $A_{1},\dots,A_{n}\in\mathbb{C}^{m\times
m}$. Then, it holds that

$\mathrm{Tr}\Big{[}\sum_{i=1}^{n}\alpha_{i}A_{i}\Big{]}\,\leq\,\|\alpha\|_{1}\cdot\sum_{i=1}^{n}|\mathrm{Tr}[A_{i}]|.$

###### Proof.

Using the Cauchy-Schwarz inequality, we have

$\mathrm{Tr}\Big{[}\sum_{i=1}^{n}\alpha_{i}A_{i}\Big{]}=\sum_{i=1}^{n}\alpha_{i}\mathrm{Tr}\big{[}A_{i}\big{]}\leq\sqrt{\sum_{i=1}^{n}|\alpha_{i}|^{2}}\cdot\sqrt{\sum_{i=1}^{n}|\mathrm{Tr}\big{[}A_{i}\big{]}|^{2}}.$

The claim follows from the norm inequality $\|x\|_{2}\leq\|x\|_{1}$, for all
$x\in\mathbb{C}^{n}$. ∎

######  Lemma 23.

Let $0\leq\Pi\leq\mathds{1}$ and let $\rho$ and $\sigma$ be states such that
$\mathsf{TD}(\rho,\sigma)\leq\gamma.$ Then,

$\mathrm{Tr}[\Pi\rho]-\gamma\leq\mathrm{Tr}[\Pi\sigma]\leq\mathrm{Tr}[\Pi\rho]+\gamma$

###### Proof.

By the standard identity
$\mathsf{TD}(\sigma,\rho)=\underset{0\leq\Lambda\leq\mathds{1}}{\max}\mathrm{Tr}[\Lambda(\sigma-\rho)]$,
it follows that:

$\displaystyle\mathrm{Tr}[\Pi\sigma]$
$\displaystyle=\mathrm{Tr}[\Pi\rho]+\mathrm{Tr}[\Pi(\sigma-\rho)]$
$\displaystyle\leq\mathrm{Tr}[\Pi\rho]+\underset{0\leq\Lambda\leq\mathds{1}}{\max}\mathrm{Tr}[\Lambda(\sigma-\rho)]$
$\displaystyle=\mathrm{Tr}[\Pi\rho]+\mathsf{TD}(\sigma,\rho)$
$\displaystyle\leq\mathrm{Tr}[\Pi\rho]+\gamma.$

The other inequality can be shown by reversing the role of $\rho$ and
$\sigma$. ∎

######  Lemma 24 ([Unr15], Lemma 18).

Let $\theta\in\\{0,1\\}^{m}$ and define
$\Pi_{\theta}^{\mathsf{eq}}=\sum_{v\in\\{0,1\\}^{m}}H^{\theta}\ket{v}\bra{v}H^{\theta}\otimes
H^{\theta}\ket{v}\bra{v}H^{\theta}$ (i.e the projector that checks if two
registers yield the same outcome if measured in the $H^{\theta}$ basis). Then,
the following is true for every $t\in[m]$. For any approximate $\mathsf{EPR}$
state,

$\ket{\phi^{+}_{ab}}=\frac{1}{\sqrt{2^{m}}}\sum_{v\in\\{0,1\\}^{m}}\ket{v}\otimes
X^{a}Z^{b}\ket{v},$

where $a,b\in\\{0,1\\}^{m}$ have Hamming weight at most $t$, it follows that:

  * •

$\Pi_{\theta}^{\mathsf{eq}}\ket{\phi^{+}_{ab}}=\ket{\phi^{+}_{ab}}$ holds if
and only if for all $i\in[m]$:

$(\theta_{i}=0\land a_{i}=0)\lor(\theta_{i}=1\land b_{i}=0).$

  * •

$\Pi_{\theta}^{\mathsf{eq}}\ket{\phi^{+}_{ab}}=0$ holds for all other cases.

We also rely on the next lemma which is based on a result by Unruh [Unr15,
Lemma 15]. To state the lemma, we define the projector onto the subspace
spanned by $\mathsf{EPR}$-pairs in registers $\mathsf{XY}$ with up to
$t\in\mathbb{N}$ single-qubit Pauli operators applied to register
$\mathsf{Y}$:

$\Pi_{t}^{\mathsf{EPR}}=\sum_{\begin{subarray}{c}a,b\in\\{0,1\\}^{m}\\\
w(a),w(b)\leq
t\end{subarray}}\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}},\quad\quad\ket{\phi^{+}_{ab}}=\frac{1}{\sqrt{2^{m}}}\sum_{v\in\\{0,1\\}^{m}}\ket{v}\otimes
X^{a}Z^{b}\ket{v},$

where $w(a),w(b)$ denote the Hamming weights of the strings $a$ and $b$. Since
$\big{\\{}\ket{\phi_{ab}^{+}}:a,b\in\\{0,1\\}^{m}\big{\\}}$ forms an
orthogonal basis of $\mathsf{XY}$, any state $\rho$ such that
$\left(\Pi_{t}^{\mathsf{EPR}}\otimes\mathds{1}_{\mathsf{R}}\right)\rho_{\mathsf{XYR}}=\rho_{\mathsf{XYR}}$
on registers $\mathsf{X,Y}$ and $\mathsf{R}$ can be written as follows (where
$a,b$ of weight greater than $t$ have probability zero):

$\rho_{\mathsf{XYR}}\,=\sum_{\begin{subarray}{c}a,b\in\\{0,1\\}^{m}\\\
w(a),w(b)\leq
t\end{subarray}}p_{ab}\,\left(\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}}_{\mathsf{XY}}\otimes\sigma^{a,b}_{\mathsf{R}}\right),$
(55)

for some arbitrary states $\sigma^{a,b}$ and indices $a,b\in\\{0,1\\}^{m}$. We
show the following lemma:

######  Lemma 25 (Monogamy uncertainty relation).

Fix a parameter $t\in\mathbb{N}$ and string $\theta\in\\{0,1\\}^{m}$. Let
$\rho$ be a density matrix on registers $\mathsf{X,Y}$ and $\mathsf{R}$ such
that
$\left(\Pi_{t}^{\mathsf{EPR}}\otimes\mathds{1}_{\mathsf{R}}\right)\rho_{\mathsf{XYR}}=\rho_{\mathsf{XYR}}$.
Let $\\{\Pi_{v^{\prime}}\\}_{v^{\prime}\in\\{0,1\\}^{m}}$ be an arbitrary
complete set of orthogonal projectors on register $\mathsf{R}$ and measure
according to the set
$\left\\{H^{\theta}\ket{v}\bra{v}_{\mathsf{X}}H^{\theta}\otimes\mathds{1}_{\mathsf{Y}}\otimes{\Pi_{v^{\prime}}}_{\mathsf{R}}\right\\}_{v^{\prime}\in\\{0,1\\}^{m}}$.
Then,

$\Pr[v^{\prime}=v]\,\,=\sum_{v\in\\{0,1\\}^{m}}\mathrm{Tr}\big{[}\big{(}H^{\theta}\ket{v}\bra{v}_{\mathsf{X}}H^{\theta}\otimes\mathds{1}_{\mathsf{Y}}\otimes{\Pi_{v}}_{\mathsf{R}}\big{)}\,\rho_{\mathsf{XYR}}\big{]}\,\leq\,2^{-m}(m+1)^{2t}.$

In other words, the min-entropy of the random variable $V$ (with outcome $v$)
given register $\mathsf{R}$ is at least $\mathbf{H}_{\min}(V|\mathsf{R})\geq
m-2t\log(m+1)$.

###### Proof.

For brevity, we define a family of projectors $\\{\Lambda_{u}^{\theta}\\}_{u}$
acting on registers $\mathsf{X}$ and $\mathsf{Y}$, where

$\Lambda_{u}^{\theta}=\big{(}H^{\theta}\ket{u}\bra{u}_{\mathsf{X}}H^{\theta}\otimes\mathds{1}_{\mathsf{Y}}\big{)}.$

Let $T$ be the set of all possible indices of weight less or equal than $t$.
Now, using decomposition (55), we can bound the success probability of
measuring $v^{\prime}=v$ using the information in the ancilla register
$\mathsf{R}$ as follows:

$\displaystyle\Pr[v^{\prime}=v]$
$\displaystyle=\sum_{v\in\\{0,1\\}^{m}}\mathrm{Tr}\big{[}\left(H^{\theta}\ket{v}\bra{v}_{\mathsf{X}}H^{\theta}\otimes\mathds{1}_{\mathsf{Y}}\otimes{\Pi_{v}}_{\mathsf{R}}\right)\rho_{\mathsf{XYR}}\big{]}$
$\displaystyle=\sum_{v\in\\{0,1\\}^{m}}\mathrm{Tr}\Big{[}\sum_{\begin{subarray}{c}a,b\in\\{0,1\\}^{m}\\\
w(a),w(b)\leq
t\end{subarray}}p_{ab}\,\left(\Lambda_{v}^{\theta}\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}}_{\mathsf{XY}}\Lambda_{v}^{\theta}\right)\otimes\left({\Pi_{v}}\sigma^{a,b}_{\mathsf{R}}\right)\Big{]}$
(by def.)
$\displaystyle\leq\sum_{v\in\\{0,1\\}^{m}}\Big{(}\sum_{\begin{subarray}{c}a,b\in\\{0,1\\}^{m}\\\
w(a),w(b)\leq
t\end{subarray}}p_{ab}\Big{)}\cdot\Big{(}\sum_{\begin{subarray}{c}a,b\in\\{0,1\\}^{m}\\\
w(a),w(b)\leq
t\end{subarray}}\|\Lambda_{v}^{\theta}\ket{\phi^{+}_{ab}}\|^{2}\cdot\mathrm{Tr}\big{[}{\Pi_{v}}\sigma^{a,b}_{\mathsf{R}}\big{]}\Big{)}$
(Lem. 22)
$\displaystyle=\sum_{v\in\\{0,1\\}^{m}}\sum_{\begin{subarray}{c}a,b\in\\{0,1\\}^{m}\\\
w(a),w(b)\leq
t\end{subarray}}\|H^{\theta}\ket{v}\bra{v}_{\mathsf{X}}H^{\theta}\otimes\mathds{1}_{\mathsf{Y}}\ket{\phi^{+}_{ab}}\|^{2}\cdot\mathrm{Tr}\big{[}{\Pi_{v}}\sigma^{a,b}_{\mathsf{R}}\big{]}$
(by def.)
$\displaystyle=\sum_{v\in\\{0,1\\}^{m}}\sum_{\begin{subarray}{c}a,b\in\\{0,1\\}^{m}\\\
w(a),w(b)\leq
t\end{subarray}}\|H^{\theta}\ket{v}\bra{v}_{\mathsf{X}}H^{\theta}\otimes
X^{a}Z^{b}_{\mathsf{Y}}\ket{\phi^{+}}\|^{2}\cdot\mathrm{Tr}\big{[}{\Pi_{v}}\sigma^{a,b}_{\mathsf{R}}\big{]}$
$\displaystyle=\sum_{v\in\\{0,1\\}^{m}}\sum_{\begin{subarray}{c}a,b\in\\{0,1\\}^{m}\\\
w(a),w(b)\leq t\end{subarray}}\|H^{\theta}\otimes
X^{a}Z^{b}H^{\theta}\big{(}\ket{v}\bra{v}_{\mathsf{X}}\otimes\mathds{1}_{\mathsf{Y}}\big{)}\ket{\phi^{+}}\|^{2}\cdot\mathrm{Tr}\big{[}{\Pi_{v}}\sigma^{a,b}_{\mathsf{R}}\big{]}$
(Lem. 1)
$\displaystyle=\sum_{v\in\\{0,1\\}^{m}}\sum_{\begin{subarray}{c}a,b\in\\{0,1\\}^{m}\\\
w(a),w(b)\leq
t\end{subarray}}\frac{\mathrm{Tr}\big{[}{\Pi_{v}}\sigma^{a,b}_{\mathsf{R}}\big{]}}{2^{m}}\,=\,\sum_{\begin{subarray}{c}a,b\in\\{0,1\\}^{m}\\\
w(a),w(b)\leq
t\end{subarray}}\frac{\mathrm{Tr}\big{[}\sigma^{a,b}_{\mathsf{R}}\big{]}}{2^{m}}=\frac{|T|}{2^{m}},$

where in the second-to-last step we used the completeness property that
$\sum_{v}\Pi_{v}=\mathds{1}$, and in the last step we use that the
${\sigma^{a,b}}$ have unit trace, for every $a,b\in\\{0,1\\}^{m}$. It now
suffices to bound $|T|$, the number of error indices of weight less or equal
to $t$. In total we have $t$ indices to assign to $m+1$ possible choices (we
add an additional degree of freedom to account for when there are no errors
assigned). Since we have two independent indices $a,b\in\\{0,1\\}^{m}$, we
get:

$\Pr[v^{\prime}=v]\leq 2^{-m}|T|\leq 2^{-m}(m+1)^{2t}.$

This proves the claim. ∎

Let us now proceed with the security proof. We consider the following sequence
of hybrids of $\mathsf{SSLGame}$. We will show that the optimal winning
probability in each successive hybrid changes at most negligibly. We will then
bound the optimal winning probability in the final hybrid.

$H_{0}$: This is the original game $\mathsf{SSLGame}$ in Section 7:

  * •

The lessor runs
$\mathsf{SSL}.\mathsf{Lease}(1^{\lambda},y\in\\{0,1\\}^{\lambda})$ to sample
$v\leftarrow\\{0,1\\}^{m}$ and $\theta\leftarrow G(y)\in\\{0,1\\}^{m}$, and
sends $(\ket{v^{\theta}},H(v))$ together with a circuit for
$\mathsf{SSL}.\mathsf{Eval}$ to the adversary $\mathcal{A}$.

  * •

Having access to the random oracles $G$ and $H$, the adversary $\mathcal{A}$
outputs a (possibly entangled) state $\sigma$ on two registers $\mathsf{Y}$
and $\mathsf{R}$, and sends the register $\mathsf{Y}$ to the lessor.

  * •

For verification, the lessor runs
$\mathsf{SSL}.\mathsf{Verify}(y,\mathsf{Y})$: Measure the register
$\mathsf{Y}$ in the $H^{\theta}$ basis according to $\theta=G(y)$. If the
outcome is equal to $v$ such that $H(v)=z$, the lessor outputs $\mathsf{ok}=1$
and lets the game continue, otherwise, the lessor outputs $\mathsf{ok}=0$ and
$\mathcal{A}$ loses.

  * •

Conditioning on $\mathsf{ok}=1$, the lessor sends the adversary a sample
$x\leftarrow\mathcal{D}_{y}$ to which $\mathcal{A}$ responds with a bit (we
refer to this phase of the security game as the “input challenge phase”).
Using the string $y$ given as input, the lessor outputs $1$, if the bit is
equal to $P_{y}(x)$, and $0$ otherwise.

$H_{1}$: The game is the same as before, except that in the input challenge
phase the lessor samples $x\leftarrow D_{y}$, and sends $G(x)$ to
$\mathcal{A}$, (instead of sending $x$ directly).

$H_{2}$: The game is the same as before, except for the input challenge phase.
The lessor samples $x\leftarrow D_{y}$. Then, if $x\neq y$, the lessor chooses
$\theta^{\prime}\leftarrow\\{0,1\\}^{m}$ and sends $\theta^{\prime}$ to
$\mathcal{A}$ (instead of $G(x)$).

$H_{3}$: The game is the same as before, except that the lessor samples
$\theta\leftarrow\\{0,1\\}^{m}$ (instead of $\theta\leftarrow G(y)$). Then, in
the input challenge phase, the lessor samples $x\leftarrow D_{y}$. If $x=y$,
the lessor sends $\theta$ to $\mathcal{A}$.

$H_{4}$: The game is identical to the game before, except that we replace
$H(v)$ with a uniformly random string $z\leftarrow\\{0,1\\}^{\lambda}$.

First, we show that the advantage of any adversary in $H_{4}$ is negligible.
Again, in the rest of the section, we denote by $p(H_{i})$ the optimal winning
probability in hybrid $H_{i}$ (see the proof in Section 5.1 for a
clarification on what the expression $p(H_{i})$ means formally).

######  Lemma 26.

$p(H_{4})\leq\frac{1}{2}$.

###### Proof.

First, the optimal probability of the adversary winning the game can only
increase if we remove the verification portion of the game, and the lessor
directly executes the input challenge phase.

Then, we consider the state received by the adversary in the two distinct
cases of the input challenge phase.

  * •

The lessor samples the marked point. In this case, the state received by the
adversary is the following, which is completely independent of the oracle $H$:

$\mathbb{E}_{\theta,v}\left(\ket{v^{\theta}}\bra{v^{\theta}}\otimes\ket{\theta}\bra{\theta}\right)\otimes\mathbb{E}_{z}\ket{z}\bra{z}\,.$

Notice that the latter state is maximally mixed.

  * •

The lessor samples a point other than the marked point. In this case, the
adversary receives the following state, which is again independent of the
oracle:

$\mathbb{E}_{\theta,\theta^{\prime},v}\left(\ket{v^{\theta}}\bra{v^{\theta}}\otimes\ket{\theta^{\prime}}\bra{\theta^{\prime}}\right)\otimes\mathbb{E}_{z}\ket{z}\bra{z}\,.$

The latter state is again maximally mixed.

Thus, an adversary can win the game $H_{4}$ with probability at most
$\frac{1}{2}$. ∎

We will now show that the optimal success probabilities in successive hybrids
do not deviate by more than a negligible amount.

######  Lemma 27.

$|p(H_{1})-p(H_{0})|=\mathsf{negl}(\lambda)$.

###### Proof.

The proof is analogous to the proof of Lemma 11 in the security of our copy-
protection scheme. The intuition is that, since $G$ is a random oracle, the
pre-image $x$ does not help the adversary, and can be simulated. ∎

######  Lemma 28.

$|p(H_{2})-p(H_{1})|=\mathsf{negl}(\lambda)$.

###### Proof.

The proof is analogous to the proof of Lemma 12, where an adversary that wins
with non-negligible difference in $H_{2}$ and $H_{1}$ yields a distinguisher
for $G(X_{\lambda})$ and $U_{m(\lambda)}$. ∎

######  Lemma 29.

$|p(H_{3})-p(H_{2})|=\mathsf{negl}(\lambda)$.

###### Proof.

The proof is analogous to the proof of Lemma 13, where an adversary that wins
with probabilities that differ non-negligibly in $H_{3}$ and $H_{2}$ yields a
distinguisher for $G(X_{\lambda})$ and $U_{m(\lambda)}$. ∎

The crux of the security proof is showing that $p(H_{3})$ and $p(H_{4})$ are
negligibly close.

######  Lemma 30.

$|p(H_{4})-p(H_{3})|=\mathsf{negl}(\lambda)\,.$

The rest of the section is devoted to proving this lemma. At a high level, the
proof has two parts:

  * •

For any adversary making $q$ queries to the oracle, we bound the difference
between the winning probability in $H_{3}$ and in $H_{4}$ by
$\mathsf{poly}(q)\cdot M$, where $M$ is a quantity related to the probability
that the adversary queries the oracle at the encoded string $v$.

  * •

Then, we show that the quantity $M$ is negligible.

######  Lemma 31.

Let $\mathcal{A}$ be an adversary for $H_{3}$ and $H_{4}$, making
$\mathsf{poly}(\lambda)$ oracle queries (pre and post verification). Suppose
that $\mathcal{A}$ passes the verification step with probability at least
$\frac{1}{2}-\mathsf{negl}(\lambda)$ in $H_{3}$. Let $\mathcal{A}$ be
specified by the unitary $U$ (i.e. $\mathcal{A}$ alternates oracles calls with
applications of $U$). Let $p_{v,\theta,z,H}\in[0,1]$, and let
$\rho_{\mathsf{R}}^{v,\theta,z,H}$ be density matrices, for all
$v,\theta,z,H$. Let

$\sigma_{\mathsf{LR}}=\mathbb{E}_{v,\theta,z,H}\,p_{v,\theta,z,H}\left(\ket{H}\bra{H}\otimes\ket{v}\bra{v}\otimes\ket{\theta}\bra{\theta}\otimes\ket{z}\bra{z}\right)_{\mathsf{L}}\otimes\rho^{v,\theta,z,H}_{\mathsf{R}}$

be the post-verification state of the lessor and $\mathcal{A}$ in $H_{4}$
conditioned on $\mathcal{A}$ passing the verification step. Let
$\tau_{\theta}=\frac{1}{2}\ket{\theta}\bra{\theta}+\frac{1}{2}\mathbb{E}_{\theta^{\prime}}\ket{\theta^{\prime}}\bra{\theta^{\prime}}$.
Then,

$|\Pr[\mathcal{A}\text{ wins in }H_{3}]-\Pr[\mathcal{A}\text{ wins in
}H_{4}]|\leq\mathsf{poly}(\lambda)\cdot M+\mathsf{negl}(\lambda)\,,$

where

$\displaystyle M$
$\displaystyle=\frac{1}{2}\,\mathbb{E}_{H}\mathbb{E}_{v}\mathbb{E}_{\theta}\mathbb{E}_{z}\mathbb{E}_{k}p_{v,\theta,z,H}\mbox{$\mathrm{Tr}\Big{[}\ket{v}\bra{v}(UO^{H_{v,z}})^{k}\left(\rho^{v,\theta,z,H}_{\mathsf{R}}\otimes\tau_{\theta}\right)\left(UO^{H_{v,z}})^{k}\right)^{\dagger}\Big{]}$}$
$\displaystyle+\frac{1}{2}\,\mathbb{E}_{H}\mathbb{E}_{v}\mathbb{E}_{\theta}\mathbb{E}_{z}\mathbb{E}_{k}p_{v,\theta,z,H}\mbox{$\mathrm{Tr}\Big{[}\ket{v}\bra{v}(UO^{H})^{k}\left(\rho^{v,\theta,z,H}_{\mathsf{R}}\otimes\tau_{\theta}\right)\left(UO^{H})^{k}\right)^{\dagger}\Big{]}$}.$

###### Proof.

As we have done in several earlier proofs, we can recast $H_{3}$ as follows:
$\mathcal{A}$ receives a uniformly random $z$, and gets access to a the
reprogrammed oracle $H_{v,z}$. Let $\ket{v^{\theta}}$ denote the encoding of
string $v$ using basis $\theta$. Let $q_{1}$ and $q_{2}$ denote the number of
queries made by the adversary respectively before and after the verification
phase.

First notice that the global states of the lessor and adversary right before
the verification is executed are negligibly close in trace distance in $H_{3}$
and $H_{4}$.

$\displaystyle\mathbb{E}_{H}\mathbb{E}_{v}\mathbb{E}_{\theta}\mathbb{E}_{z}\ket{H}\bra{H}\otimes\ket{v}\bra{v}\otimes\ket{\theta}\bra{\theta}\otimes\left((UO^{H_{v,z}})^{q_{1}}\ket{v^{\theta}}\bra{v^{\theta}}\otimes\ket{z}\bra{z}\left((UO^{H_{v,z^{\prime}}})^{q_{1}}\right)^{\dagger}\right)$
$\displaystyle\approx\,$
$\displaystyle\mathbb{E}_{H}\mathbb{E}_{v}\mathbb{E}_{\theta}\mathbb{E}_{z}\ket{H}\bra{H}\otimes\ket{v}\bra{v}\otimes\ket{\theta}\bra{\theta}\otimes\left((UO^{H})^{q_{1}}\ket{v^{\theta}}\bra{v^{\theta}}\otimes\ket{z}\bra{z}\left((UO^{H})^{q_{1}}\right)^{\dagger}\right)\,.$
(56)

Here we have stored the complete function $H$ in an additional register, the
quantum way of formulating indistinguishability of the joint distribution of
$H$ and the adversary’s state.

Equation (56) follows from the one-way-to-hiding lemma (Lemma 7), and the fact
that $\mathcal{A}$ only queries at $v$ with negligible probability (otherwise
$\mathcal{A}$ would straightforwardly imply an adversary that wins the
monogamy game (more precisely the variant of Lemma 4).

It follows that:

  * •

The probabilities of $\mathcal{A}$ passing the verification step in $H_{3}$
and in $H_{4}$ are negligibly close.

  * •

The post-verification states, conditioned on passing verification must be
negligibly close (this uses (56) together with the fact that, by hypothesis,
$\mathcal{A}$ passes verification with probability at least
$\frac{1}{2}-\mathsf{negl}(\lambda)$).

By definition, the joint state of lessor and adversary post-verification state
in $H_{4}$ conditioned on $\mathcal{A}$ passing verification is

$\sigma_{\mathsf{LR}}=\mathbb{E}_{v,\theta,z,H}\,p_{v,\theta,z,H}\left(\ket{H}\bra{H}\otimes\ket{v}\bra{v}\otimes\ket{\theta}\bra{\theta}\otimes\ket{z}\bra{z}\right)_{\mathsf{L}}\otimes\rho^{v,\theta,z,H}_{\mathsf{R}}\,.$

Let the analogous state in $H_{3}$ be

$\tilde{\sigma}_{\mathsf{LR}}=\mathbb{E}_{v,\theta,z,H}\,p_{v,\theta,z,H}\left(\ket{H}\bra{H}\otimes\ket{v}\bra{v}\otimes\ket{\theta}\bra{\theta}\otimes\ket{z}\bra{z}\right)_{\mathsf{L}}\otimes\tilde{\rho}^{v,\theta,z,H}_{\mathsf{R}}\,.$

Then $\sigma_{\mathsf{L,R}}\approx\tilde{\sigma}_{\mathsf{L,R}}$. Now, denote
by $\\{\Pi^{0},\Pi^{1}\\}$ the projective measurement performed by
$\mathcal{A}$ to guess the answer to the input challenge phase. Then,

$\displaystyle\Pr[\mathcal{A}\text{ wins in }H_{4}|\text{verification is
passed}]$
$\displaystyle=\mathbb{E}_{v,\theta,z,H}\,p_{v,\theta,z,H}\Bigg{[}\frac{1}{2}\mbox{$\mathrm{Tr}\Big{[}\Pi^{1}(UO^{H})^{q_{2}}\rho^{v,\theta,z,H}_{\mathsf{R}}\otimes\ket{\theta}\bra{\theta}\left((UO^{H})^{q_{2}}\right)^{\dagger}\Big{]}$}$
$\displaystyle+\frac{1}{2}\mathbb{E}_{\theta^{\prime}}\mbox{$\mathrm{Tr}\Big{[}\Pi^{0}(UO^{H})^{q_{2}}\rho^{v,\theta,z,H}_{\mathsf{R}}\otimes\ket{\theta^{\prime}}\bra{\theta^{\prime}}\left((UO^{H})^{q_{2}}\right)^{\dagger}\Big{]}$}\Bigg{]}\,.$
(57)

And, similarly,

$\displaystyle\Pr[\mathcal{A}\text{ wins in }H_{3}|\text{verification is
passed}]$
$\displaystyle=\mathbb{E}_{v,\theta,z,H}\,p_{v,\theta,z,H}\Bigg{[}\frac{1}{2}\mbox{$\mathrm{Tr}\Big{[}\Pi^{1}(UO^{H_{v,z}})^{q_{2}}\tilde{\rho}^{v,\theta,z,H}_{\mathsf{R}}\otimes\ket{\theta}\bra{\theta}\left((UO^{H_{v,z}})^{q_{2}}\right)^{\dagger}\Big{]}$}$
$\displaystyle+\frac{1}{2}\mathbb{E}_{\theta^{\prime}}\mbox{$\mathrm{Tr}\Big{[}\Pi^{0}(UO^{H_{v,z}})^{q_{2}}\tilde{\rho}^{v,\theta,z,H}_{\mathsf{R}}\otimes\ket{\theta^{\prime}}\bra{\theta^{\prime}}\left((UO^{H_{v,z}})^{q_{2}}\right)^{\dagger}\Big{]}$}\Bigg{]}$
$\displaystyle\approx\mathbb{E}_{v,\theta,z,H}\,p_{v,\theta,z,H}\Bigg{[}\frac{1}{2}\mbox{$\mathrm{Tr}\Big{[}\Pi^{1}(UO^{H_{v,z}})^{q_{2}}\rho^{v,\theta,z,H}_{\mathsf{R}}\otimes\ket{\theta}\bra{\theta}\left((UO^{H_{v,z}})^{q_{2}}\right)^{\dagger}\Big{]}$}$
$\displaystyle+\frac{1}{2}\mathbb{E}_{\theta^{\prime}}\mbox{$\mathrm{Tr}\Big{[}\Pi^{0}(UO^{H_{v,z}})^{q_{2}}\rho^{v,\theta,z,H}_{\mathsf{R}}\otimes\ket{\theta^{\prime}}\bra{\theta^{\prime}}\left((UO^{H_{v,z}})^{q_{2}}\right)^{\dagger}\Big{]}$}\Bigg{]}\,.$
(58)

Using equations (7.2) and (7.2), and applying the O2H lemma twice (once to
bound the distance between the first terms in expressions (7.2) and (7.2), and
once to bound the distance between the second terms in (7.2) and (7.2)), we
obtain:

$\displaystyle\left|\Pr[\mathcal{A}\text{ wins in }H_{4}|\text{verification is
passed}]-\Pr[\mathcal{A}\text{ wins in }H_{3}|\text{verification is
passed}]\right|$
$\displaystyle\leq\mathsf{poly}(\lambda)\cdot\frac{1}{2}\mathbb{E}_{v,\theta,z,H}\,p_{v,\theta,z,H}\mbox{$\mathrm{Tr}\Big{[}\ket{v}\bra{v}(UO^{H})^{k}\left(\rho^{v,\theta,z,H}_{\mathsf{R}}\otimes\ket{\theta}\bra{\theta}\right)\left(UO^{H})^{k}\right)^{\dagger}\Big{]}$}$
$\displaystyle+\mathsf{poly}(\lambda)\cdot\frac{1}{2}\mathbb{E}_{v,\theta,z,H}\,p_{v,\theta,z,H}\mbox{$\mathrm{Tr}\Big{[}\ket{v}\bra{v}(UO^{H_{v,z}})^{k}\left(\rho^{v,\theta,z,H}_{\mathsf{R}}\otimes\ket{\theta}\bra{\theta}\right)\left(UO^{H_{v,z}})^{k}\right)^{\dagger}\Big{]}$}$
$\displaystyle+\mathsf{poly}(\lambda)\cdot\frac{1}{2}\mathbb{E}_{v,\theta,z,H,\theta^{\prime}}\,p_{v,\theta,z,H}\mbox{$\mathrm{Tr}\Big{[}\ket{v}\bra{v}(UO^{H})^{k}\left(\rho^{v,\theta,z,H}_{\mathsf{R}}\otimes\ket{\theta^{\prime}}\bra{\theta^{\prime}}\right)\left(UO^{H})^{k}\right)^{\dagger}\Big{]}$}$
$\displaystyle+\mathsf{poly}(\lambda)\cdot\frac{1}{2}\mathbb{E}_{v,\theta,z,H,\theta^{\prime}}\,p_{v,\theta,z,H}\mbox{$\mathrm{Tr}\Big{[}\ket{v}\bra{v}(UO^{H_{v,z}})^{k}\left(\rho^{v,\theta,z,H}_{\mathsf{R}}\otimes\ket{\theta^{\prime}}\bra{\theta^{\prime}}\right)\left(UO^{H_{v,z}})^{k}\right)^{\dagger}\Big{]}$}+\mathsf{negl}(\lambda)$
$\displaystyle=\mathsf{poly}(\lambda)\cdot\frac{1}{2}\mathbb{E}_{v,\theta,z,H}\,p_{v,\theta,z,H}\mbox{$\mathrm{Tr}\Big{[}\ket{v}\bra{v}(UO^{H})^{k}\left(\rho^{v,\theta,z,H}_{\mathsf{R}}\otimes\tau_{\theta}\right)\left(UO^{H})^{k}\right)^{\dagger}\Big{]}$}$
$\displaystyle+\mathsf{poly}(\lambda)\cdot\frac{1}{2}\mathbb{E}_{v,\theta,z,H}\,p_{v,\theta,z,H}\mbox{$\mathrm{Tr}\Big{[}\ket{v}\bra{v}(UO^{H_{v,z}})^{k}\left(\rho^{v,\theta,z,H}_{\mathsf{R}}\otimes\tau_{\theta}\right)\left(UO^{H_{v,z}})^{k}\right)^{\dagger}\Big{]}$}+\mathsf{negl}(\lambda)$
$\displaystyle=\mathsf{poly}(\lambda)\cdot M+\mathsf{negl}(\lambda)\,,$ (59)

where to get two equalities we used the definition of $\tau_{\theta}$ and $M$.
This is the desired bound. ∎

In the rest of the section, we show that the quantity $M$ from Lemma 31 is
negligible. First of all, notice that $M$ is negligible if and only if the
second term in $M$ is negligible, i.e. if and only if,

$\mathbb{E}_{H}\mathbb{E}_{v}\mathbb{E}_{\theta}\mathbb{E}_{z}\mathbb{E}_{k}p_{v,\theta}\mbox{$\mathrm{Tr}\Big{[}\ket{v}\bra{v}(UO^{H})^{k}\left(\rho^{v,\theta,z,H}_{\mathsf{R}}\otimes\tau_{\theta}\right)\left(UO^{H})^{k}\right)^{\dagger}\Big{]}$}=\mathsf{negl}(\lambda)\,.$
(60)

where we are using the same notation as in Lemma 31. Thus, what we wish to
show is equivalent to showing that, for any adversary $\mathcal{A}$ in $H_{4}$
who passes verification with probability at least
$\frac{1}{2}-\mathsf{negl}(\lambda)$, the probability of querying the oracle
at the encoded string $v$ at any point after a successful verification is
negligible.

Thus, we will show that (60) is negligible. First, notice that an adversary
$\mathcal{A}$ which passes verification in $H_{4}$ with probability at least
$\frac{1}{2}-\mathsf{negl}(\lambda)$ and violates (60) immediately implies an
adversary which succeeds at the following game $\widetilde{H}_{0}$ with non-
negligible probability.

$\widetilde{H}_{0}$: This is identical to $H_{4}$ except we ask the adversary
to return a guess

$v^{\prime}$ for the encoded string $v$, instead of a bit. $\mathcal{A}$ wins
if $v^{\prime}=v$.

The reduction crucially uses the hypothesis that $\mathcal{A}$ passes
verification with probability at least $\frac{1}{2}-\mathsf{negl}(\lambda)$.
We will show through another sequence of hybrids (which we denote using
tildes) that the optimal winning probability in $\widetilde{H}_{0}$ is
negligible. This will complete the proof that the quantity in (60), and thus
$M$ is negligible, for any adversary $\mathcal{A}$ who passes verification
with probability at least $\frac{1}{2}-\mathsf{negl}(\lambda)$. Since the
optimal winning probability in $H_{3}$ and $H_{4}$ is at least $\frac{1}{2}$
(the honest strategy followed by random guessing achieves $\frac{1}{2}$), this
concludes the proof of Lemma 30, and hence that the optimal winning
probability in $H_{0}$ is at most $\frac{1}{2}+\mathsf{negl}(\lambda)$. The
following are the hybrids.

$\widetilde{H}_{1}$: Instead of sampling $v\leftarrow\\{0,1\\}^{m}$ and
$\theta\leftarrow\\{0,1\\}^{m}$ at the beginning of the game, the lessor now
prepares an $\mathsf{EPR}$ pair on two registers $\mathsf{X}$ and
$\mathsf{Y}$, and sends the registers $\mathsf{YZ}$ of the state
$\ket{\phi^{+}}_{\mathsf{XY}}\otimes\ket{z}_{\mathsf{Z}}$ to $\mathcal{A}$.
Rather than running $\mathsf{SSL}.\mathsf{Verify}$ for verification and
measuring the register $\mathsf{Y}$, the lessor now measures both registers
$\mathsf{X}$ and $\mathsf{Y}$ in the $H^{\theta}$ basis for a random
$\theta\leftarrow\\{0,1\\}^{m}$, and checks if the outcomes result in the same
string, which we denote by $v$.

$\widetilde{H}_{2}$: This game is identical to the one before, except that we
change the verification procedure as follows. Instead of measuring each of the
registers $\mathsf{X}$ and $\mathsf{Y}$ in the $H^{\theta}$ basis, the lessor
now measures a bipartite projector $\Pi_{\theta}^{\mathsf{eq}}$ in order to
check if the registers $\mathsf{XY}$ yield the same outcome if measured in the
$H^{\theta}$ basis. We define the projector as follows:

${\Pi_{\theta}^{\mathsf{eq}}}=\sum_{v\in\\{0,1\\}^{m}}H^{\theta}\ket{v}\bra{v}_{\mathsf{X}}H^{\theta}\otimes
H^{\theta}\ket{v}\bra{v}_{\mathsf{Y}}H^{\theta}.$

Afterwards, the lessor measures register $\mathsf{X}$ in the $H^{\theta}$
basis to determine $v$.

We will denote these hybrids using a tilde to distinguish them from the
original sequence of hybrids.

######  Lemma 32.

$p(\widetilde{H}_{1})=p(\widetilde{H}_{0})$.

###### Proof.

The argument is fairly standard. We consider the following two statements:

  * •

sample $v\leftarrow\\{0,1\\}^{m}$, let $\theta\in\\{0,1\\}^{m}$, and output
$\bigotimes_{i=1}^{m}\ket{v_{i}^{\theta_{i}}}_{\mathsf{Y}}$.

  * •

create an $m$-qubit $\mathsf{EPR}$ pair $\ket{\phi^{+}}_{\mathsf{XY}}$,
measure $\mathsf{X}$ in the $H^{\theta}$ basis, and output register
$\mathsf{Y}$.

It is evident that the equivalence of the two statements implies that
$p(\widetilde{H}_{1})$ and $p(\widetilde{H}_{0})$ are identical. Note that we
omit the register $\ket{z}$ in the proof, since it is independent of the
$\mathsf{EPR}$ registers and thus does not affect the argument. Consider the
following family of projectors given by

$\\{\big{(}H^{\theta}\ket{v}\bra{v}H^{\theta}\otimes\mathds{1}_{\mathsf{Y}}\big{)}\\}_{v\in\\{0,1\\}^{m}}.$

We analyze the post-measurement state
$\ket{\psi_{v}}/\sqrt{\Braket{\psi_{v}}{\psi_{v}}}$, for
$\ket{\psi_{v}}=\big{(}H^{\theta}\ket{v}\bra{v}_{\mathsf{X}}H^{\theta}\otimes\mathds{1}_{\mathsf{Y}}\big{)}\ket{\phi^{+}}$:

$\displaystyle\ket{\psi_{v}}_{\mathsf{XY}}$
$\displaystyle=\big{(}H^{\theta}\ket{v}\bra{v}H^{\theta}\otimes\mathds{1}\big{)}\ket{\phi^{+}}_{\mathsf{XY}}$
$\displaystyle=\Big{(}\big{(}H^{\theta}\otimes\mathds{1}\big{)}\big{(}\ket{v}\bra{v}\otimes\mathds{1}\big{)}\big{(}H^{\theta}\otimes\mathds{1}\big{)}\Big{)}\ket{\phi^{+}}_{\mathsf{XY}}$
$\displaystyle=\Big{(}\big{(}H^{\theta}\otimes\mathds{1}\big{)}\big{(}\ket{v}\bra{v}\otimes\mathds{1}\big{)}\big{(}\mathds{1}\otimes
H^{\theta}\big{)}\Big{)}\ket{\phi^{+}}_{\mathsf{XY}}$ (Lemma 1)
$\displaystyle=2^{-m/2}\sum_{v^{\prime}\in\\{0,1\\}^{m}}\Big{(}\big{(}H^{\theta}\otimes\mathds{1}\big{)}\big{(}\ket{v}\bra{v}\otimes\mathds{1}\big{)}\big{(}\mathds{1}\otimes
H^{\theta}\big{)}\Big{)}\ket{v^{\prime}}_{\mathsf{X}}\otimes\ket{v^{\prime}}_{\mathsf{Y}}$
$\displaystyle=2^{-m/2}\sum_{v^{\prime}\in\\{0,1\\}^{m}}H^{\theta}\ket{v}_{\mathsf{X}}\Braket{v}{v^{\prime}}\otimes
H^{\theta}\ket{v^{\prime}}_{\mathsf{Y}}$
$\displaystyle=2^{-m/2}H^{\theta}\ket{v}_{\mathsf{X}}\otimes
H^{\theta}\ket{v}_{\mathsf{Y}}.$

This proves the claim, since the $\mathsf{Y}$ register of
$\ket{\psi_{v}}/\sqrt{\Braket{\psi_{v}}{\psi_{v}}}$ is identical to
$\bigotimes_{i=1}^{m}\ket{v_{i}^{\theta_{i}}}$. ∎

######  Lemma 33.

$p(\widetilde{H}_{2})=p(\widetilde{H}_{1})$

###### Proof.

The lemma is immediate as the measurement in $\tilde{H}_{2}$ is a coarse-
graining of the measurement in $\tilde{H}_{1}$, with the acceptance condition
remaining the same. ∎

In the remaining part of the proof, we will show that $p(\widetilde{H}_{2})$
is negligible. The following is an important technical lemma, which is
inspired by Lemma $16$ and Lemma $19$ in [Unr15].

######  Lemma 34.

$p(\widetilde{H}_{2})=\mathsf{negl}(\lambda)\,.$

###### Proof.

Let $\mathcal{A}$ be an adversary for $\widetilde{H}_{2}$. Denote by
$v^{\prime}$ the final guess returned by the adversary, and by $v$ the encoded
string. Let $\mathsf{ok}$ be a random variable for whether the verification
passes. Then, the winning probability of $\mathcal{A}$ in $\widetilde{H}_{2}$
is given by:

$\Pr\big{[}v^{\prime}=v\,\land\,\mathsf{ok}=1]\,.$

We show that, for any $t\in[m]$,

$\Pr\big{[}v^{\prime}=v\,\land\,\mathsf{ok}=1]\,\leq\,2^{-m}(m+1)^{2t}+2^{\frac{-t-1}{2}}.$
(61)

Picking $t\approx\sqrt{m}$ then gives the desired result, as the RHS becomes
negligible in $\lambda$.

Fix a basis choice $\theta\in\\{0,1\\}^{m}$. Let $\rho_{\theta}$ be the state
on registers $\mathsf{X},\mathsf{Y}$ and $\mathsf{R}$ in $\widetilde{H}_{2}$
after the verification, where $\mathsf{R}$ is the leftover register held onto
by $\mathcal{A}$ that also includes the challenge $\tau_{\theta}$ (where
$\tau_{\theta}$ was defined in Lemma 31) sent by the lessor after
verification.

In the analysis that follows, it is convenient to approximate $\rho_{\theta}$
by an ideal state that is diagonal in a basis for the image of
$\Pi_{t}^{\mathsf{EPR}}\otimes\mathds{1}_{\mathsf{R}}$, where
$\Pi_{t}^{\mathsf{EPR}}$ is as defined in Lemma 25. Recall that
$\Pi_{t}^{\mathsf{EPR}}$ projects onto the subspace spanned by $\mathsf{EPR}$
pairs with up to $t$ Pauli errors, i.e. onto the space spanned by the
orthogonal basis states
$\big{\\{}\ket{\phi^{+}_{ab}}:a,b\in\\{0,1\\}^{m}\big{\\}}$, where

$\ket{\phi^{+}_{ab}}=\frac{1}{\sqrt{2^{m}}}\sum_{v\in\\{0,1\\}^{m}}\ket{v}\otimes
X^{a}Z^{b}\ket{v}.$ (62)

We can use Lemma 3 to argue that there exists such an ideal state
$\rho_{\theta}^{\mathsf{id}}$, and that the trace distance between the two
states satisfies:

$\mathsf{TD}(\rho_{\theta},\rho_{\theta}^{\mathsf{id}})\leq\sqrt{1-\mathrm{Tr}\big{[}\big{(}\Pi_{t}^{\mathsf{EPR}}\otimes\mathds{1}_{\mathsf{R}}\big{)}\,\rho_{\theta}\big{]}}\,.$

We can represent the adversary’s strategy in guessing $v$, after verification,
by a projective measurement $\\{\Pi_{v^{\prime}}\\}_{v^{\prime}}$.

We are now ready to bound the probability
$\Pr\big{[}v^{\prime}=v\,\land\,\mathsf{ok}=1]$. Let $\Theta$ be a random
variable for the basis choice made by the lessor. Then, by marginalizing over
$\Theta$, we get:

$\displaystyle\Pr\big{[}v^{\prime}=v\,\land\,\mathsf{ok}=1\big{]}$
$\displaystyle=\sum_{\theta\in\\{0,1\\}^{m}}2^{-m}\cdot\Pr\big{[}v^{\prime}=v|\,\mathsf{ok}=1\,\land\,\Theta=\theta\big{]}\cdot\Pr[\mathsf{ok}=1|\Theta=\theta]$
$\displaystyle\leq\sum_{\theta\in\\{0,1\\}^{m}}2^{-m}\cdot\Pr\big{[}v^{\prime}=v|\,\mathsf{ok}=1\,\land\,\Theta=\theta\big{]}$
$\displaystyle=\mathbb{E}_{\theta}\Pr[v^{\prime}=v\,|\,\mathsf{ok}=1\,\land\,\Theta=\theta].$
(63)

Fix any $\theta$. Using Lemma 23 and Lemma 25 we obtain:

$\displaystyle\Pr\big{[}v^{\prime}=v\,|\,\mathsf{ok}=1\land\Theta=\theta\big{]}$
$\displaystyle\leq
2^{-m}(m+1)^{2t}+\mathsf{TD}(\rho_{\theta},\rho_{\theta}^{\mathsf{id}})$
$\displaystyle\leq
2^{-m}(m+1)^{2t}+\sqrt{1-\mathrm{Tr}\big{[}\big{(}\Pi_{t}^{\mathsf{EPR}}\otimes\mathds{1}_{\mathsf{R}}\big{)}\,\rho_{\theta}\big{]}}\,.$
(64)

Now, averaging over $\theta$ in the above inequality gives:

$\displaystyle\mathbb{E}_{\theta}\Pr[v^{\prime}=v\,|\,\mathsf{ok}=1\land\Theta=\theta]$
$\displaystyle\leq
2^{-m}(m+1)^{2t}+\mathbb{E}_{\theta}\sqrt{1-\mathrm{Tr}\big{[}\big{(}\Pi_{t}^{\mathsf{EPR}}\otimes\mathds{1}_{\mathsf{R}}\big{)}\,\rho_{\theta}\big{]}}$
$\displaystyle\leq
2^{-m}(m+1)^{2t}+\sqrt{\mathbb{E}_{\theta}\mathrm{Tr}\Big{[}\Big{(}\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\otimes\mathds{1}_{\mathsf{R}}\Big{)}\,\rho_{\theta}\Big{]}}\,.$
(65)

where the last inequality follows from Jensen’s inequality. We will proceed to
bound the above term
$\mathbb{E}_{\theta}\mathrm{Tr}\big{[}\big{(}\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\otimes\mathds{1}_{\mathsf{R}}\big{)}\,\rho_{\theta}\big{]}$
by $2^{-t-1}$. Let us first show that for any $a,b\in\\{0,1\\}^{m}$:

$\displaystyle
p_{ab}\overset{\text{def}}{=}\sum_{\theta\in\\{0,1\\}^{m}}2^{-m}\mathrm{Tr}\big{[}\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\Pi_{\theta}^{\mathsf{eq}}\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}}_{\mathsf{XY}}\big{]}\,\,\leq\,2^{-t-1}.$
(66)

This follows from considering the following two cases:

  * •

$w(a),w(b)\leq t$: Using Lemma 24 we find that one of the following is true.
Depending on $\theta$, either
$\Pi_{\theta}^{\mathsf{eq}}\ket{\phi^{+}_{ab}}=0$ or
$\Pi_{\theta}^{\mathsf{eq}}\ket{\phi^{+}_{ab}}=\ket{\phi^{+}_{ab}}$. We also
get that
$\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\ket{\phi^{+}_{ab}}=0$, since
$\Pi_{t}^{\mathsf{EPR}}\ket{\phi^{+}_{ab}}=\ket{\phi^{+}_{ab}}$, and thus it
follows that $p_{ab}=0$.

  * •

$\max\big{(}w(a),w(b)\big{)}\geq t+1$: Here, Lemma 24 implies that there are
at most $2^{m}/{2^{t+1}}$ many values of $\theta$ for which it holds that
$\Pi_{\theta}^{\mathsf{eq}}\ket{\phi^{+}_{ab}}\neq 0$, and thus $p_{ab}\leq
2^{-m}\cdot 2^{m}/{2^{t+1}}\,=\,2^{-t-1}$.

Observe now that $\Pi_{t}^{\mathsf{EPR}}$ and
$\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}}$ are diagonal in the Bell basis, hence
they commute. Lemma 24 implies that the same is also true for the projector
$\Pi_{\theta}^{\mathsf{eq}}$. For any fixed $\theta\in\\{0,1\\}^{m}$, we
express $\rho_{\theta}$ as a generic density operator on registers
$\mathsf{X}$, $\mathsf{Y}$ and $\mathsf{R}$ such that, for a finite index set
$I^{\theta}$, coefficients $q_{ij}$ and an orthogonal basis
$\\{\ket{\Psi^{i,\theta}}\,:\,i\in I^{\theta}\\}$ the registers $\mathsf{X}$
and $\mathsf{Y}$:

$\displaystyle{\rho_{\theta}}=\sum_{i,j\in
I^{\theta}}q_{ij}\,\ket{\Psi^{i,\theta}}\bra{\Psi^{j,\theta}}_{\mathsf{XY}}\otimes{\sigma_{\mathsf{R}}^{i,j,\theta}},$
(67)

where $\sigma^{i,j,\theta}$ are matrices for indices $i,j\in I^{\theta}$.
Since we assumed that $\rho_{\theta}$ is the state conditioned on the
verification being successful for some $\theta$, we have the property that

$\big{(}\Pi_{\theta}^{\mathsf{eq}}\otimes\mathds{1}_{\mathsf{R}}\big{)}{\rho_{\theta}}\big{(}\Pi_{\theta}^{\mathsf{eq}}\otimes\mathds{1}_{\mathsf{R}}\big{)}={\rho_{\theta}},\quad\quad\forall\theta\in\\{0,1\\}^{m}.$
(68)

In other words, $\rho_{\theta}$ on is invariant under the action of the
projector $\Pi_{\theta}^{\mathsf{eq}}\otimes\mathds{1}_{\mathsf{R}}$. Then,

$\displaystyle\mathbb{E}_{\theta}\mathrm{Tr}\Big{[}\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\otimes\mathds{1}_{\mathsf{R}}\,{\rho_{\theta}}\Big{]}$
$\displaystyle=\sum_{\theta\in\\{0,1\\}^{m}}2^{-m}\mathrm{Tr}\big{[}\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\otimes\mathds{1}_{\mathsf{R}}\,{\rho_{\theta}}\big{]}$
$\displaystyle=\sum_{\theta\in\\{0,1\\}^{m}}2^{-m}\mathrm{Tr}\big{[}\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\otimes\mathds{1}_{\mathsf{R}}\,\big{(}\Pi_{\theta}^{\mathsf{eq}}\otimes\mathds{1}_{\mathsf{R}}\big{)}{\rho_{\theta}}\big{(}\Pi_{\theta}^{\mathsf{eq}}\otimes\mathds{1}_{\mathsf{R}}\big{)}\big{]}\quad\quad\quad\quad\quad(\text{Eq.}~{}\eqref{eq:invariant})$
$\displaystyle=\sum_{\theta\in\\{0,1\\}^{m}}2^{-m}\mathrm{Tr}\Big{[}\Big{(}\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\Pi_{\theta}^{\mathsf{eq}}\otimes\mathds{1}_{\mathsf{R}}\Big{)}\,{\rho_{\theta}}\Big{]}$
$\displaystyle=\sum_{\theta\in\\{0,1\\}^{m}}2^{-m}\mathrm{Tr}\Big{[}\Big{(}\sum_{a,b\in\\{0,1\\}^{m}}\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}}\Big{)}\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\Pi_{\theta}^{\mathsf{eq}}\otimes\mathds{1}_{\mathsf{R}}\,{\rho_{\theta}}\Big{]}$
$\displaystyle=\sum_{\theta\in\\{0,1\\}^{m}}\sum_{a,b\in\\{0,1\\}^{m}}2^{-m}\,\mathrm{Tr}\Big{[}\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}}\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\Pi_{\theta}^{\mathsf{eq}}\otimes\mathds{1}_{\mathsf{R}}\,{\rho_{\theta}}\Big{]}$
$\displaystyle=\sum_{\theta\in\\{0,1\\}^{m}}\sum_{a,b\in\\{0,1\\}^{m}}2^{-m}\,\mathrm{Tr}\Big{[}\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\Pi_{\theta}^{\mathsf{eq}}\otimes\mathds{1}_{\mathsf{R}}\,\big{(}\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}}\otimes\mathds{1}_{\mathsf{R}}\big{)}{\rho_{\theta}}\big{(}\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}}\otimes\mathds{1}_{\mathsf{R}}\big{)}\Big{]}$

In the third to last line, we inserted the complete set
$\sum_{a,b}\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}}=\mathds{1}$. Then, using the
definition of $\rho$ in Eq.(67), we can continue to expand the expression
above as follows:

$\displaystyle\sum_{\theta\in\\{0,1\\}^{m}}\sum_{a,b\in\\{0,1\\}^{m}}2^{-m}\,\mathrm{Tr}\Big{[}\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\Pi_{\theta}^{\mathsf{eq}}\otimes\mathds{1}_{\mathsf{R}}\,\big{(}\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}}\otimes\mathds{1}_{\mathsf{R}}\big{)}{\rho_{\theta}}\big{(}\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}}\otimes\mathds{1}_{\mathsf{R}}\big{)}\Big{]}$
$\displaystyle=\sum_{\theta\in\\{0,1\\}^{m}}\sum_{a,b\in\\{0,1\\}^{m}}2^{-m}\sum_{i,j\in
I^{\theta}}q_{ij}\,\mathrm{Tr}\Big{[}\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\Pi_{\theta}^{\mathsf{eq}}\,\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}}\big{(}\ket{\Psi^{i,\theta}}\bra{\Psi^{j,\theta}}_{\mathsf{XY}}\big{)}\ket{\phi^{+}_{ab}}\bra{\phi^{+}_{ab}}\otimes{\sigma_{\mathsf{R}}^{i,j,\theta}}\Big{]}$
$\displaystyle=\sum_{a,b\in\\{0,1\\}^{m}}\sum_{i,j\in
I^{\theta}}p_{ab}\,q_{ij}\bra{\phi^{+}_{ab}}\big{(}\ket{\Psi^{i,\theta}}\bra{\Psi^{j,\theta}}_{\mathsf{XY}}\big{)}\ket{\phi^{+}_{ab}}\,\,\mathrm{Tr}\big{[}{\sigma_{\mathsf{R}}^{i,j,\theta}}\big{]}\quad\quad\quad\quad\,\,\,\,(\text{by
def.})$ $\displaystyle\leq\,2^{-t-1}\sum_{i,j\in
I^{\theta}}q_{ij}\sum_{a,b\in\\{0,1\\}^{m}}\bra{\phi^{+}_{ab}}\big{(}\ket{\Psi^{i,\theta}}\bra{\Psi^{j,\theta}}_{\mathsf{XY}}\big{)}\ket{\phi^{+}_{ab}}\,\mathrm{Tr}\big{[}{\sigma_{\mathsf{R}}^{i,j,\theta}}\big{]}\quad\quad\quad\,\,\,(\text{Eq.}~{}\eqref{eq:pab_bound})$
$\displaystyle=\,2^{-t-1}\sum_{i,j\in
I^{\theta}}q_{ij}\mathrm{Tr}\big{[}\ket{\Psi^{i,\theta}}\bra{\Psi^{j,\theta}}_{\mathsf{XY}}\big{]}\,\mathrm{Tr}\big{[}{\sigma_{\mathsf{R}}^{i,j,\theta}}\big{]}\quad=\quad
2^{-t-1}\,\mathrm{Tr}\big{[}{\rho_{\theta}}\big{]}\quad=\quad 2^{-t-1}.$

In the last line, we used that
$\big{\\{}\ket{\phi^{+}_{ab}}:a,b\in\\{0,1\\}^{m}\big{\\}}$ is an orthogonal
basis for $\mathsf{XY}$. Thus, we get

$\mathbb{E}_{\theta}\mathrm{Tr}\Big{[}\big{(}\mathds{1}-\Pi_{t}^{\mathsf{EPR}}\big{)}\otimes\mathds{1}_{\mathsf{R}}\,{\rho_{\theta}}\Big{]}\,\,\leq\,\,2^{-t-1}.$

Plugging this bound in (65) and then into (7.2) gives

$\Pr\big{[}v^{\prime}=v\,\land\,\mathsf{ok}=1\big{]}\leq
2^{-m}(m+1)^{2t}+2^{\frac{-t-1}{2}}\,.$ (69)

Choosing $t\approx\sqrt{m}$ makes the RHS negligible. ∎

######  Corollary 5.

$p(\widetilde{H}_{0})=\mathsf{negl}(\lambda)$.

As we argued earlier, this concludes the proof of Lemma (30), and thus of
Theorem 7.

###  7.3 Extension to compute-and-compare programs

In this section, we show that an $\mathsf{SSL}$ scheme for point functions,
which is secure with respect to the appropriate program and challenge
ensembles, implies an $\mathsf{SSL}$ scheme for compute-and-compare programs
with the same level of security, with respect to apppropriate program and
challenge ensembles. The idea is the same as in Section 6: to lease the
compute-and-compare program $\mathsf{CC}[f,y]$, we first lease the point
function $P_{y}$, and then hand out the function $f$ in the clear.

Let
$(\mathsf{SSL}\mbox{-}\mathsf{PF.Gen},\mathsf{SSL}\mbox{-}\mathsf{PF.Lease},\mathsf{SSL}\mbox{-}\mathsf{PF.Eval},\mathsf{SSL}\mbox{-}\mathsf{PF.Verify})$
be any $\mathsf{SSL}$ scheme for point functions. The compute-and-compare
program scheme is defined as follows:

######  Construction 6 ($\mathsf{SSL}$ scheme for compute-and-compare
programs).

The $\mathsf{SSL}$ scheme for compute-and-compare programs
$(\mathsf{SSL}\mbox{-}\mathsf{CC.Gen},\mathsf{SSL}\mbox{-}\mathsf{CC.Lease},\mathsf{SSL}\mbox{-}\mathsf{CC.Eval},\mathsf{SSL}\mbox{-}\mathsf{CC.Verify})$
is defined by:

  * •

$\mathsf{SSL}\mbox{-}\mathsf{CC.Gen}(1^{\lambda})$: Takes as input the
security parameter $\lambda$. Then,

    * –

Let $\mathsf{sk}\leftarrow\mathsf{SSL}\mbox{-}\mathsf{PF.Gen}(1^{\lambda})$.
Output $\mathsf{sk}$.

  * •

$\mathsf{SSL}\mbox{-}\mathsf{CC.Lease}(1^{\lambda},\mathsf{sk},(f,y))$: Takes
as input a security parameter $\lambda$, a secret key $sk$, and a compute-and-
compare program $\mathsf{CC}[f,y]$, specified succinctly by $f$ and $y$. Then,

    * –

Let $\rho=\mathsf{SSL}\mbox{-}\mathsf{PF.Lease}(1^{\lambda},\mathsf{sk},y))$.
Output $(f,\rho)$.

  * •

$\mathsf{SSL}\mbox{-}\mathsf{CC.Eval}(1^{\lambda},(f,\rho);x)$: Takes as input
a security parameter $\lambda$, an alleged program copy $(f,\rho)$, and a
string $x\in\\{0,1\\}^{n}$ (where $n$ is the size of the inputs to $f$). Then,

    * –

Compute $y^{\prime}=f(x)$.

    * –

Let $b\leftarrow\mathsf{SSL}\mbox{-}\mathsf{PF.Eval}(\rho;y^{\prime})$. Output
$b$.

  * •

$\mathsf{SSL}\mbox{-}\mathsf{CC.Verify}(1^{\lambda},\mathsf{sk},(f,\rho);\sigma)$:

    * –

Let
$b^{\prime}\leftarrow\mathsf{SSL}\mbox{-}\mathsf{PF.Verify}(1^{\lambda},\mathsf{sk},y;\sigma)$.
Output $b^{\prime}$.

Recall the definition of the class of distributions over compute-and-compare
programs $\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{UNP}}$ in Section 6. We
recall it here for convenience.

  * •

$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{UNP}}$. We refer to this class as the
class of unpredictable compute-and-compare programs. This consists of
ensembles $D=\\{D_{\lambda}\\}$ where $D_{\lambda}$ is a distribution over
compute-and-compare programs such that $\mathsf{CC}[f,y]\leftarrow
D_{\lambda}$ satisfies $\mathbf{H}_{\min}(y|f)\geq\lambda^{\epsilon}$ for some
$\epsilon>0$, and where the input length of $f$ is $\lambda$ and the output
length is bounded by some polynomial $t(\lambda)$.

We also define the following class of distributions over input challenges:

  * •

$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{Chall}\mbox{-}\mathsf{SSL}}$. An
ensemble $D=\\{D_{f,y}\\}$, where each $D_{f,y}$ is a distribution over the
domain of $f$, belongs to the class
$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{Chall}\mbox{-}\mathsf{SSL}}$ if there
exists an efficiently sampleable family $\\{X_{\lambda}\\}$ of distributions
over $\\{0,1\\}^{\lambda}$ with
$\mathbf{H}_{\min}(X_{\lambda})\geq\lambda^{\epsilon}$, for some $\epsilon>0$,
and an efficiently sampleable family $\\{Z_{f,y}\\}$, where $Z_{f,y}$ is a
distribution over the set $f^{-1}(y)$, such that $D_{f,y}$ is the following
distribution (where $\lambda$ is the size of inputs to $f$):

    * –

with probability $1/2$, sample $z\leftarrow Z_{f,y}$ and output $z$.

    * –

with probability $1/2$, sample $x\leftarrow X_{\lambda}$, and output $x$.

We say the ensemble $D$ is _specified_ by the families $\\{X_{\lambda}\\}$ and
$\\{Z_{f,y}\\}$.

Similarly to Section 6, we also define two classes of distributions over pairs
of programs and challenges for compute-and-compare programs.

  * •

$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}\mbox{-}\mathsf{SSL}}.$
This consists of pairs of ensembles
$\left(D=\\{D_{\lambda}\\},D^{\prime}=\\{D^{\prime}_{f,y}\\}\right)$ where
$D\in\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{UNP}}$ and
$D^{\prime}\in\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{Chall}\mbox{-}\mathsf{SSL}}$
satisfying the following. Let $D^{\prime}$ be specified by the families
$\\{X_{\lambda}\\}$ and $\\{Z_{f,y}\\}$, and denote by
$\mathsf{MarkedInput}\left(D_{\lambda},\\{Z_{f,y}\\}\right)$ the distribution
over $\\{0,1\\}^{\lambda}$ induced by $D_{\lambda}$ and $\\{Z_{f,y}\\}$, i.e.:

    * –

Sample $(f,y)\leftarrow D_{\lambda}$, then output $z\leftarrow Z_{f,y}$.

For any fixed $f_{*}$ with domain $\\{0,1\\}^{\lambda}$ such that
$(f_{*},y_{*})$ is in the support of $D_{\lambda}$ for some $y_{*}$, denote by
$\mathsf{MarkedInput}(D_{\lambda},\\{Z_{f,y}\\})|_{f_{*}}$, the distribution
$\mathsf{MarkedInput}(D_{\lambda},\\{Z_{f,y}\\})$ conditioned on $D_{\lambda}$
sampling $f_{*}$. Then, we require that, for any sequence
$\\{f_{*}^{(\lambda)}\\}$ (where, for all $\lambda$,
$(f_{*}^{(\lambda)},y_{*})$ is in the support of $D_{\lambda}$ for some
$y_{*}$) the families $\\{X_{\lambda}\\}$ and
$\\{\mathsf{MarkedInput}(D_{\lambda},\\{Z_{f,y}\\})|_{f_{*}^{(\lambda)}}\\}$
are statistically indistinguishable.

  * •

$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{comp}\mbox{-}\mathsf{SSL}}.$
This is defined in the same way as
$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}\mbox{-}\mathsf{SSL}}$,
except that we only require $\\{X_{\lambda}\\}$ and
$\\{\mathsf{MarkedInput}(D_{\lambda},\\{Z_{f,y}\\})|_{f_{*}^{(\lambda)}}\\}$
to be _computationally_ indistinguishable.

######  Theorem 8.

Let
$(\mathsf{SSL}\mbox{-}\mathsf{PF.Gen},\mathsf{SSL}\mbox{-}\mathsf{PF.Lease},\mathsf{SSL}\mbox{-}\mathsf{PF.Eval},\mathsf{SSL}\mbox{-}\mathsf{PF.Verify})$
be an $\mathsf{SSL}$ scheme for point functions that is $\delta$-secure with
respect to all pairs
$(D,D^{\prime})\in\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}\mbox{-}\mathsf{SSL}}$
($\in\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{comp}\mbox{-}\mathsf{SSL}}$).
Then, the scheme of Construction 6 is a $\delta$-secure $\mathsf{SSL}$ scheme
for compute-and-compare programs with respect to all pairs
$(D,D^{\prime})\in\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}\mbox{-}\mathsf{SSL}}$
($\in\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{comp}\mbox{-}\mathsf{SSL}}$).
The same conclusion holds relative to any oracle, i.e. when all algorithms
have access to the same oracle, with respect to query-bounded (computationally
bounded) adversaries.

The proof of Theorem 8 uses a similar reduction to the point function security
game as in the copy-protection variant in Theorem 6. The main difference is
that the reduction between the $\mathsf{SSL}$ games now involves a
verification step. We add the proof for completeness.

###### Proof of Theorem 8.

We prove the claim for
$\left(\\{D_{\lambda}\\},\\{D_{f,y}\\}\right)\in\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}\mbox{-}\mathsf{SSL}}$
only, since the case of
$\left(\\{D_{\lambda}\\},\\{D_{f,y}\\}\right)\in\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{comp}\mbox{-}\mathsf{SSL}}$
is virtually identical. Let $t(\lambda)$ be the length of strings in the range
of $f$’s sampled from $D_{\lambda}$ and let the ensemble $\\{D_{f,y}\\}$ be
specified by $\\{X_{\lambda}\\}$ and $\\{Z_{f,y}\\}$ (using the notation
introduced above for ensembles in
$\mathcal{D}_{\mathsf{CC}\mbox{-}\mathsf{Chall}\mbox{-}\mathsf{SSL}}$).

Let $\mathcal{A}$ be an adversary for the compute-and-compare $\mathsf{SSL}$
scheme of Construction 6 with respect to ensembles $\\{D_{\lambda}\\}$ and
$\\{D_{f,y}\\}$ who wins at the $\mathsf{SSL}$ security game with probability
$p(\lambda)>0$. It then follows that for each $\lambda$ there exists
$f_{*}^{(\lambda)}$ such that $(f_{*}^{(\lambda)},y)$ is in the support of
$D_{\lambda}$ for some $y$, and such that the probability that $\mathcal{A}$
wins is at least $p(\lambda)$, conditioned on $f_{*}^{(\lambda)}$ being
sampled. We will construct an adversary $\mathcal{A}^{\prime}$ that wins with
probability $p(\lambda)-\mathsf{negl}(\lambda)$ in the point function security
game with respect to the distributions $\\{D^{\prime}_{t(\lambda)}\\}$ and
$\\{D^{\prime}_{y}\\}$, defined as follows:

  * •

$D^{\prime}_{t(\lambda)}$: sample $x\leftarrow X_{\lambda}$ and output the
point function $P_{f^{(\lambda)}_{*}(x)}$.

  * •

$D^{\prime}_{y}$: sample $x\leftarrow D_{f_{*}^{(\lambda)},y}$ and output
$f_{*}^{(\lambda)}(x)$.

The adversary $\mathcal{A}^{\prime}$ against the point function $\mathsf{SSL}$
game acts as follows:

  * •

$\mathcal{A}^{\prime}$ receives a state $\rho$ from the lessor, and then
forwards $(f_{*}^{(\lambda)},\rho)$ to adversary $\mathcal{A}$.

  * •

$\mathcal{A}$ returns a supposed program copy $\sigma$ for the point function
to $\mathcal{A}^{\prime}$ who then sends it back to the lessor for
verification.

  * •

Conditioning on the verification being successful, the lessor replies with a
challenge input $x\leftarrow D^{\prime}_{y}$. $\mathcal{A}^{\prime}$ then
samples $x^{\prime}\leftarrow Z_{f,x}$, and runs $\mathcal{A}$ with input
challenge $x^{\prime}$.

  * •

Let $b$ be the bit returned by $\mathcal{A}$. The adversary
$\mathcal{A}^{\prime}$ replies with the same $b$ to the lessor.

It is straightforward to check that the game “simulated” by
$\mathcal{A}^{\prime}$ for $\mathcal{A}$ is statistically indistinguishable
from a security game with respect to $\\{D_{\lambda}\\}$ and $\\{D_{f,y}\\}$,
conditioned on $f^{(\lambda)}_{*}$. Thus, we deduce, by hypothesis, that
$\mathcal{A}$ passes verification and returns the correct bit with probability
at least $p(\lambda)-\mathsf{negl}(\lambda)$, and thus $\mathcal{A}^{\prime}$
wins with probability at least $p(\lambda)-\mathsf{negl}(\lambda)$. Crucially,
note that
$\left(\\{D^{\prime}_{t(\lambda)}\\},\\{D^{\prime}_{y}\\}\right)\in\mathcal{D}_{\mathsf{PF}\mbox{-}\mathsf{pairs}\mbox{-}\mathsf{stat}\mbox{-}\mathsf{SSL}}$.
It follows that if the $\mathsf{SSL}$ is $\delta$-secure, then the compute-
and-compare scheme must also be $\delta$-secure.

The proof of the theorem statement relative to any oracle is analogous. ∎

## References

  * [Aar05] Scott Aaronson.  Limitations of quantum advice and one-way communication.  Theory of Computing, 1(1):1–28, 2005.
  * [Aar09] Scott Aaronson.  Quantum copy-protection and quantum money.  In 2009 24th Annual IEEE Conference on Computational Complexity, pages 229–242. IEEE, 2009.
  * [AF16] Gorjan Alagic and Bill Fefferman.  On quantum obfuscation.  CoRR, abs/1602.01771, 2016.
  * [AHU19] Andris Ambainis, Mike Hamburg, and Dominique Unruh.  Quantum security proofs using semi-classical oracles.  In Annual International Cryptology Conference, pages 269–295. Springer, 2019.
  * [ALP20] Prabhanjan Ananth and Rolando L La Placa.  Secure software leasing.  arXiv preprint arXiv:2005.05289, 2020.
  * [ALZ20] Scott Aaronson, Jiahui Liu, and Ruizhe Zhang.  Quantum copy-protection from hidden subspaces.  arXiv preprint arXiv:2004.09674, 2020.
  * [AMRS20] Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song.  Quantum-access-secure message authentication via blind-unforgeability.  In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, pages 788–817, Cham, 2020. Springer International Publishing.
  * [BBBV97] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani.  Strengths and weaknesses of quantum computing.  SIAM J. Comput., 26(5):1510–1523, October 1997.
  * [BDF+11] Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry.  Random oracles in a quantum world.  In International Conference on the Theory and Application of Cryptology and Information Security, pages 41–69. Springer, 2011.
  * [BGI+12] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang.  On the (im) possibility of obfuscating programs.  Journal of the ACM (JACM), 59(2):1–48, 2012.
  * [BHH+19] Nina Bindel, Mike Hamburg, Kathrin Hövelmanns, Andreas Hülsing, and Edoardo Persichetti.  Tighter proofs of cca security in the quantum random oracle model.  In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography, pages 61–90, Cham, 2019. Springer International Publishing.
  * [BL19] Anne Broadbent and Sébastien Lord.  Uncloneable quantum encryption via random oracles.  arXiv preprint arXiv:1903.00130, 2019.
  * [BR93] Mihir Bellare and Phillip Rogaway.  Random oracles are practical: A paradigm for designing efficient protocols.  In Proceedings of the 1st ACM Conference on Computer and Communications Security, CCS ’93, page 62–73, New York, NY, USA, 1993. Association for Computing Machinery.
  * [CGH04] Ran Canetti, Oded Goldreich, and Shai Halevi.  The random oracle methodology, revisited.  J. ACM, 51(4):557–594, July 2004.
  * [CKVW10] Ran Canetti, Yael Tauman Kalai, Mayank Varia, and Daniel Wichs.  On symmetric encryption and point obfuscation.  In Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010. Proceedings, volume 5978 of Lecture Notes in Computer Science, pages 52–71. Springer, 2010.
  * [CMSZ19] Jan Czajkowski, Christian Majenz, Christian Schaffner, and Sebastian Zur.  Quantum lazy sampling and game-playing proofs for quantum indifferentiability.  arXiv preprint arXiv:1904.11477, 2019.
  * [EPR35] A. Einstein, B. Podolsky, and N. Rosen.  Can quantum-mechanical description of physical reality be considered complete?  Phys. Rev., 47:777–780, May 1935.
  * [ES20] Edward Eaton and Fang Song.  A note on the instantiability of the quantum random oracle.  In Jintai Ding and Jean-Pierre Tillich, editors, Post-Quantum Cryptography, pages 503–523, Cham, 2020. Springer International Publishing.
  * [GKW17] Rishab Goyal, Venkata Koppula, and Brent Waters.  Lockable obfuscation.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 612–621. IEEE, 2017.
  * [Got03] Daniel Gottesman.  Uncloneable encryption.  Quantum Information & Computation, 3(6):581–602, 2003.
  * [HI19] Akinori Hosoyamada and Tetsu Iwata.  4-round luby-rackoff construction is a qprp.  In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology – ASIACRYPT 2019, pages 145–174, Cham, 2019. Springer International Publishing.
  * [KRS09] Robert König, Renato Renner, and Christian Schaffner.  The operational meaning of min- and max-entropy.  IEEE Trans. Inf. Theor., 55(9):4337–4347, September 2009.
  * [KSS+20] Veronika Kuchta, Amin Sakzad, Damien Stehlé, Ron Steinfeld, and Shi-Feng Sun.  Measure-rewind-measure: Tighter quantum random oracle model proofs for one-way to hiding and cca security.  In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, pages 703–728, Cham, 2020. Springer International Publishing.
  * [NC11] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, USA, 10th edition, 2011.
  * [Reg05] Oded Regev.  On lattices, learning with errors, random linear codes, and cryptography.  In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, page 84–93, New York, NY, USA, 2005. Association for Computing Machinery.
  * [SW13] Amit Sahai and Brent Waters.  How to use indistinguishability obfuscation: Deniable encryption, and more.  Cryptology ePrint Archive, Report 2013/454, 2013.  https://eprint.iacr.org/2013/454.
  * [TFKW13] Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, and Stephanie Wehner.  A monogamy-of-entanglement game with applications to device-independent quantum cryptography.  New Journal of Physics, 15(10):103002, 2013.
  * [Unr12] Dominique Unruh.  Quantum proofs of knowledge.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 135–152. Springer, 2012.
  * [Unr15] Dominique Unruh.  Revocable quantum timed-release encryption.  J. ACM, 62(6), December 2015.
  * [Wat06] John Watrous.  Zero-knowledge against quantum attacks, 2006.
  * [Wie83] Stephen Wiesner.  Conjugate coding.  SIGACT News, 15(1):78–88, January 1983.
  * [Wil13] Mark M. Wilde.  Quantum Information Theory.  Cambridge University Press, USA, 1st edition, 2013.
  * [Win99] A. Winter.  Coding theorem and strong converse for quantum channels.  IEEE Transactions on Information Theory, 45(7):2481–2485, 1999\.
  * [WZ17] D. Wichs and G. Zirdelis.  Obfuscating compute-and-compare programs under lwe.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 600–611, 2017.
  * [Zha12] Mark Zhandry.  How to construct quantum random functions.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 679–687. IEEE, 2012.
  * [Zha17] Mark Zhandry.  Quantum lightning never strikes the same state twice.  CoRR, abs/1711.02276, 2017.
  * [Zha19] Mark Zhandry.  How to record quantum queries, and applications to quantum indifferentiability.  In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, pages 239–268, Cham, 2019. Springer International Publishing.

##  Appendix A Appendix

###  A.1 Proof of Lemma 7

###### Proof.

For any $x\in\\{0,1\\}^{\lambda}$, define
$V_{x}^{H}=\left(UO^{H}(I-\ket{x}\bra{x})\right)^{q}$ and let
$W_{x}^{H}=UO^{H}-V_{x}^{H}$. Then,

$\displaystyle\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\|\Pi^{0}(UO^{H})^{q}\left(\ket{H(x)}\otimes\ket{\psi_{x}}\right)\|^{2}+\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{1}(UO^{H})^{q}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{0}(UO^{H_{x,z}})^{q}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}+\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{1}(UO^{H})^{q}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{0}(V_{x}^{H_{x,z}}+W_{x}^{H_{x,z}})\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}+\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{1}(V_{x}^{H}+W_{x}^{H})\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{0}V_{x}^{{H_{x,z}}}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}+\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{1}V_{x}^{H}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}$
$\displaystyle+$
$\displaystyle\frac{1}{2}(3q+2)q\,\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\mathbb{E}_{k}\|\ket{x}\bra{x}(UO^{{H_{x,z}}})^{k}\ket{z}\otimes\ket{\psi_{x}}\|$
$\displaystyle+$
$\displaystyle\frac{1}{2}(3q+2)q\,\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\mathbb{E}_{k}\|\ket{x}\bra{x}(UO^{H})^{k}\ket{z}\otimes\ket{\psi_{x}}\|$
$\displaystyle=$
$\displaystyle\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{0}V_{x}^{{H_{x,z}}}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}+\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{1}V_{x}^{H}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}$
$\displaystyle+$ $\displaystyle(3q+2)q\,M\,$ (70)

where the first equality uses Lemma 5, and the inequality uses Lemma 18 in
[BL19].

In order to prove the desired inequality, it is sufficient to show that

$\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{0}V_{x}^{{H_{x,z}}}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}+\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{1}V_{x}^{H}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}\leq\frac{1}{2}\,.$
(71)

Notice that $V_{x}^{H_{x,z}}=V_{x}^{H}$, since $V_{x}^{H}$ projects onto the
subspace orthogonal to $x$ before every query to $H$. This implies that the
LHS simplifies as

$\displaystyle\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{0}V_{x}^{{H_{x,z}}}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}+\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{1}V_{x}^{H}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{0}V_{x}^{H}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}+\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\in
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{1}V_{x}^{H}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}$
$\displaystyle=$ $\displaystyle\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\in
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|V_{x}^{H}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}$
$\displaystyle\leq$ $\displaystyle\frac{1}{2}\,\,,$ (72)

where to get the third line, we used the fact that $\Pi^{0},\Pi^{1}$ are a
complete pair of orthogonal projectors, and to get the last line we exploited
properties of the Euclidean norm.

Combining (70) and (72) gives the desired inequality.

With a little extra work, one can show that $M$ is negligible if and only if

$\frac{1}{2}\mathbb{E}_{H}\mathbb{E}_{x\leftarrow
X}\mathbb{E}_{z\leftarrow\\{0,1\\}^{m}}\|\Pi^{1}V_{x}^{H}\left(\ket{z}\otimes\ket{\psi_{x}}\right)\|^{2}$

is negligible. We refer the reader to the proof of Theorem 3 in [AHU19] for
the full details. ∎

###  A.2 Proof of Lemma 11

We continue the proof of Lemma 11, using the notation we introduced in the
main text. In what follows, $\mathcal{P}$, $\mathcal{F}_{1}$,
$\mathcal{F}_{2}$ always have access to a uniformly random oracle $H$, but we
omit writing this. We have

$\displaystyle\Pr[(\mathcal{P}^{\prime},\mathcal{F}_{1}^{\prime},\mathcal{F}_{2}^{\prime})\text{
win }H_{1}]$
$\displaystyle=\frac{1}{3}\Pr\Big{[}\mathcal{F}_{1}^{\hat{G}_{x_{1}^{\prime},w_{1}}}(\textsf{A},x_{1}^{\prime})=0\,\,\,\land\,\,\,\mathcal{F}_{2}^{\hat{G}_{x_{2}^{\prime},w_{2}}}(\textsf{B},x_{2}^{\prime})=0$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,:\textsf{AB}\leftarrow\rho,\,\,\,\rho\leftarrow\mathcal{P}^{\hat{G}}\left(\ket{v^{G(y)}},H(v)\right),P_{y}\leftarrow
D_{y},v\leftarrow\\{0,1\\}^{m(\lambda)},$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,w_{1},w_{2}\leftarrow\\{0,1\\}^{m(\lambda)},x_{1}^{\prime},x_{2}^{\prime}\leftarrow
X_{\lambda}\,,\,G\leftarrow\text{Bool}(n,m(\lambda))\,,\,\hat{G}\leftarrow\text{Bool}(n,m(\lambda))\Big{]}$
$\displaystyle\,\,\,\,+\frac{1}{3}\Pr\Big{[}\mathcal{F}_{1}^{\hat{G}_{x_{1}^{\prime},w_{1}}}(\textsf{A},x_{1}^{\prime})=1\,\,\,\land\,\,\,\mathcal{F}_{2}^{\hat{G}_{x_{2}^{\prime},w_{2}}}(\textsf{B},x_{2}^{\prime})=0$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,:\textsf{AB}\leftarrow\rho,\,\,\,\rho\leftarrow\mathcal{P}^{\hat{G}}\left(\ket{v^{G(y)}},H(v)\right),P_{y}\leftarrow
D_{y},v\leftarrow\\{0,1\\}^{m(\lambda)},$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,w_{1}\leftarrow
G(y),w_{2}\leftarrow\\{0,1\\}^{m(\lambda)},x_{1}^{\prime},x_{2}^{\prime}\leftarrow
X_{\lambda}\,,\,G\leftarrow\text{Bool}(n,m(\lambda))\,,\,\hat{G}\leftarrow\text{Bool}(n,m(\lambda))\Big{]}$
$\displaystyle\,\,\,\,+\frac{1}{3}\Pr\Big{[}\mathcal{F}_{1}^{\hat{G}_{x_{1}^{\prime},w_{1}}}(\textsf{A},x_{1}^{\prime})=0\,\,\,\land\,\,\,\mathcal{F}_{2}^{\hat{G}_{x_{2}^{\prime},w_{2}}}(\textsf{B},x_{2}^{\prime})=1$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,:\textsf{AB}\leftarrow\rho,\,\,\,\rho\leftarrow\mathcal{P}^{\hat{G}}\left(\ket{v^{G(y)}},H(v)\right),P_{y}\leftarrow
D_{y},v\leftarrow\\{0,1\\}^{m(\lambda)},$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,w_{1}\leftarrow\\{0,1\\}^{m(\lambda)},w_{2}\leftarrow
G(y),x_{1}^{\prime},x_{2}^{\prime}\leftarrow
X_{\lambda}\,,\,G\leftarrow\text{Bool}(n,m(\lambda))\,,\,\hat{G}\leftarrow\text{Bool}(n,m(\lambda))\Big{]}\,.$
(73)

For the next step, the key observation is that $\mathcal{P}$ only queries the
oracle at $x_{1}^{\prime}$ and $x_{2}^{\prime}$ with negligible weight.
Likewise, $\mathcal{F}_{1}$ only queries $x_{2}^{\prime}$ with negligible
weight, and $\mathcal{F}_{2}$ only queries $x_{1}^{\prime}$ with negligible
weight. The reason why this is true in this case is that, if it were true, $P$
could be used to construct an adversary that guesses a string sampled from
$X_{\lambda}$ with non-negligible probability. But $X_{\lambda}$ has
polynomial min-entropy. Thus, by an application of the one-way-to-hiding
lemma, one can replace the current oracle accesses of $\mathcal{P}$,
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ with oracle access to the function
$\hat{G}_{(x_{1}^{\prime},w_{1}),(x_{2}^{\prime},w_{2})}$. Hence, we have, up
to negligible quantities,

$\displaystyle\eqref{eq: 23}$
$\displaystyle=\frac{1}{3}\Pr\Big{[}\mathcal{F}_{1}^{\hat{G}_{(x_{1}^{\prime},w_{1}),(x_{2}^{\prime},w_{2})}}(\textsf{A},x_{1}^{\prime})=0\,\,\,\land\,\,\,\mathcal{F}_{2}^{\hat{G}_{(x_{1}^{\prime},w_{1}),(x_{2}^{\prime},w_{2})}}(\textsf{B},x_{2}^{\prime})=0$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,:\textsf{AB}\leftarrow\rho,\,\,\,\rho\leftarrow\mathcal{P}^{\hat{G}_{(x_{1}^{\prime},w_{1}),(x_{2}^{\prime},w_{2})}}\left(\ket{v^{G(y)}},H(v)\right),P_{y}\leftarrow
D_{y},v\leftarrow\\{0,1\\}^{m(\lambda)},$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,w_{1},w_{2}\leftarrow\\{0,1\\}^{m(\lambda)},x_{1}^{\prime},x_{2}^{\prime}\leftarrow
X_{\lambda}\,,\,G\leftarrow\text{Bool}(n,m(\lambda))\,,\,\hat{G}\leftarrow\text{Bool}(n,m(\lambda))\Big{]}$
$\displaystyle\,\,\,\,+\frac{1}{3}\Pr\Big{[}\mathcal{F}_{1}^{\hat{G}_{(x_{1}^{\prime},w_{1}),(x_{2}^{\prime},w_{2})}}(\textsf{A},x_{1}^{\prime})=1\,\,\,\land\,\,\,\mathcal{F}_{2}^{\hat{G}_{(x_{1}^{\prime},w_{1}),(x_{2}^{\prime},w_{2})}}(\textsf{B},x_{2}^{\prime})=0$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,:\textsf{AB}\leftarrow\rho,\,\,\,\rho\leftarrow\mathcal{P}^{\hat{G}_{(x_{1}^{\prime},w_{1}),(x_{2}^{\prime},w_{2})}}\Big{(}\ket{v^{w_{1}}},H(v)\Big{)},y\leftarrow\\{0,1\\}^{\lambda},v\leftarrow\\{0,1\\}^{m(\lambda)},$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,w_{1}\leftarrow
G(y),w_{2}\leftarrow\\{0,1\\}^{m(\lambda)},x_{1}^{\prime},x_{2}^{\prime}\leftarrow
X_{\lambda}\,,\,G\leftarrow\text{Bool}(n,m(\lambda))\,,\,\hat{G}\leftarrow\text{Bool}(n,m(\lambda))\Big{]}$
$\displaystyle\,\,\,\,+\frac{1}{3}\Pr\Big{[}\mathcal{F}_{1}^{\hat{G}_{(x_{1}^{\prime},w_{1}),(x_{2}^{\prime},w_{2})}}(\textsf{A},x_{1}^{\prime})=0\,\,\,\land\,\,\,\mathcal{F}_{2}^{\hat{G}_{(x_{1}^{\prime},w_{1}),(x_{2}^{\prime},w_{2})}}(\textsf{B},x_{2}^{\prime})=1$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,:\textsf{AB}\leftarrow\rho,\,\,\,\rho\leftarrow\mathcal{P}^{\hat{G}_{(x_{1}^{\prime},w_{1}),(x_{2}^{\prime},w_{2})}}\Big{(}\ket{v^{w_{2}}},H(v)\Big{)},P_{y}\leftarrow
D_{y},v\leftarrow\\{0,1\\}^{m(\lambda)},$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,w_{1}\leftarrow\\{0,1\\}^{m(\lambda)},w_{2}\leftarrow
G(y),x_{1}^{\prime},x_{2}^{\prime}\leftarrow
X_{\lambda}\,,\,G\leftarrow\text{Bool}(n,m(\lambda))\,,\,\hat{G}\leftarrow\text{Bool}(n,m(\lambda))\Big{]}$
(74)

For the second and third terms, it is convenient to further reprogram the
oracle $\hat{G}$ at $y$, assigning as output a fresh uniformly random value in
$\\{0,1\\}^{m(\lambda)}$. We can do this since none of the algorithms queries
at $y$ with non-negligible weight. In this way, we are able to rewrite (74)
more concisely, up to negligible terms, as:

$\displaystyle\frac{1}{3}\Pr\Big{[}\mathcal{F}_{1}^{G}(\textsf{A},x_{1}^{\prime})=0\,\,\,\land\,\,\,\mathcal{F}_{2}^{G}(\textsf{B},x_{2}^{\prime})=0$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,:\textsf{AB}\leftarrow\rho,\,\,\,\rho\leftarrow\mathcal{P}^{G}\left(\ket{v^{G(y)}},H(v)\right),P_{y}\leftarrow
D_{y},v\leftarrow\\{0,1\\}^{m(\lambda)},$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,x_{1}^{\prime},x_{2}^{\prime}\leftarrow
X_{\lambda}\,,\,G\leftarrow\text{Bool}(n,m(\lambda))\Big{]}$
$\displaystyle\,\,\,\,+\frac{1}{3}\Pr\Big{[}\mathcal{F}_{1}^{G}(\textsf{A},x_{1}^{\prime})=1\,\,\,\land\,\,\,\mathcal{F}_{2}^{G}(\textsf{B},x_{2}^{\prime})=0$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,:\textsf{AB}\leftarrow\rho,\,\,\,\rho\leftarrow\mathcal{P}^{G}\left(\ket{v^{G(x^{\prime}_{1})}},H(v)\right),v\leftarrow\\{0,1\\}^{m(\lambda)},$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,x_{1}^{\prime},x_{2}^{\prime}\leftarrow
X_{\lambda}\,,\,G\leftarrow\text{Bool}(n,m(\lambda))\Big{]}$
$\displaystyle\,\,\,\,+\frac{1}{3}\Pr\Big{[}\mathcal{F}_{1}^{G}(\textsf{A},x_{1}^{\prime})=1\,\,\,\land\,\,\,\mathcal{F}_{2}^{G}(\textsf{B},x_{2}^{\prime})=0$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,:\textsf{AB}\leftarrow\rho,\,\,\,\rho\leftarrow\mathcal{P}^{G}\left(\ket{v^{G(x^{\prime}_{2})}},H(v)\right),v\leftarrow\\{0,1\\}^{m(\lambda)},$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,x_{1}^{\prime},x_{2}^{\prime}\leftarrow
X_{\lambda}\,,\,G\leftarrow\text{Bool}(n,m(\lambda))\Big{]}$ (75)

Finally, notice that

$\displaystyle\eqref{eq: 200}=$
$\displaystyle\,\frac{1}{3}\Pr(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{
win }H_{0}|\,\,\text{0-input, 0-input}]$ $\displaystyle+$
$\displaystyle\,\frac{1}{3}\Pr(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{
win }H_{0}|\,\,\text{1-input, 0-input}]$ $\displaystyle+$
$\displaystyle\,\frac{1}{3}\Pr(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})\text{
win }H_{0}|\,\,\text{0-input, 1-input}]$ $\displaystyle=$
$\displaystyle\,p\,,$ (76)

which yields the desired result.