[110]. It is mostly required for our theoretical bounds and even so, we
parameterised the deviation from perfect randomness or identical distribution
with the randomness parameter of CPUF, although we require that the encoded
qubits are independent..

  2. 2.

The output distributions $\\{p^{f}_{x}(y)\\}_{y\in\\{0,1\\}^{4m}}$ for all the
inputs $x$ are independent and identically distributed (i.i.d).

##### Universal Unforgeability of HPUF

Intuitively the security of our HPUF comes from the indistinguishability
property of the non-orthogonal quantum states. First we show that the HPUFs
are at least as secure as the underlying CPUFs.

######  Theorem 44.

Let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{2m}$ be a classical PUF. If there is
no QPT weak adversary who can win the universal unforgeability game for CPUF
with a non-negligible probability in the security parameter, then the HPUF
constructed from $f$ according to Construction 4, is also universally
unforgeable.

###### Proof.

We show the contrapositive statement that if you can break HPUF you can also
break underlying CPUF. Here we give the proof for $m=1$, and it can easily be
generalised for any arbitrary integer $m>0$. Suppose for the HPUF, a $q$-query
weak-adversary win the unforgeability game with a non-negligible probability
$P(m=1,p,q)$. This implies, given a database of $q$ random challenge response
from the HPUF, the adversary can produce $\ket{\psi_{f(x^{*})}}$ corresponding
to a random challenge $x^{*}\in\\{0,1\\}^{n}$ with a non-negligible
probability $P(m=1,p,q)$. Note that, for the deterministic adversarial
strategy, the adversary can produce multiple copies of the forged state
$\ket{\psi_{\tilde{f}(x^{*})}}$ for a random challenge $x^{*}$. For the random
adversaries we can produce the multiple copies of the same forged state
$\ket{\psi_{\tilde{f}(x^{*})}}$ just by fixing the internal randomness
parameter of the adversarial strategy. Hence, both the random and
deterministic adversary can produce multiple copies of the forged state
$\ket{\psi_{\tilde{f}(x^{*})}}$ for a random challenge $x^{*}$. From the
multiple (say $K$) such copies of $\ket{\psi_{\tilde{f}(x^{*})}}$, the
adversary will extract $\tilde{f}(x^{*})$ using the following strategy.

Algorithm 3 Algorithm to Forge CPUF from HPUF

$K\geqslant 2$-copies of the forged state $\ket{\psi_{\tilde{f}(x^{*})}}$

\- Measure the $1$-st copy of the state $\ket{\psi_{\tilde{f}(x^{*})}}$ in
$\\{\ket{0},\ket{1}\\}$-basis.

\- Let $z_{1}\in\\{0,1\\}$ be the measurement outcome.

for  _$i=2$ ; $i\leqslant(K-1)$; $i++$_ do

Measure the $i$-th copy of the state $\ket{\psi_{\tilde{f}(x^{*})}}$ in
$\\{\ket{0},\ket{1}\\}$-basis.

Let $z_{i}\in\\{0,1\\}$ be the measurement outcome.

if  _$z_{i}\neq z_{i-1}$_ then

break $\triangleright$ Implies
$\ket{\psi_{\tilde{f}(x^{*})}}\in\\{\ket{+},\ket{-}\\}$.

if  _$i=K$_ then

Return $\tilde{f}(x^{*})=(0,z_{i})$

else

Measure the $i+1$-th copy in $\\{\ket{+},\ket{-}\\}$-basis.

Let $z_{i+1}$ be the measurement outcome.

Return $\tilde{f}(x^{*})=(1,z_{i+1})$.

If $\ket{\psi_{f(x^{*})}}=\ket{\psi_{\tilde{f}(x*)}}\in\\{\ket{0},\ket{1}\\}$
then in Algorithm 3 all the measurement outcomes $z_{i}$ (for $1\leqslant
i\leqslant K$) would be the same, and $\tilde{f}(x^{*})=f(x^{*})$. However, if
$\ket{\psi_{f(x^{*})}}=\ket{\psi_{\tilde{f}(x*)}}\in\\{\ket{+},\ket{-}\\}$
then we $\tilde{f}(x^{*})\neq f(x^{*})$ if and only if all the measurement
outcomes $z_{i}$ are equal ($1\leqslant i\leqslant K$). This happens with
probability $\frac{1}{2^{K}}$. Therefore, we get

$\Pr_{x^{*}}[\tilde{f}(x^{*})=f(x^{*})||\psi_{f(x^{*})}\rangle=|\psi_{\tilde{f}(x*)}\rangle]\geqslant
1-\frac{1}{2^{K}}.$ (6.72)

If the adversary successfully forges the HPUF with a non-negligible
probability $P(m=1,p,q)$ then from Eq. (6.72) we get that the adversary
manages the CPUF with probability at least $P(m=1,p,q)=1-\frac{1}{2^{K}}$,
that is an overwhelming probability. Therefore, if an adversary successfully
wins the unforgeability game for the HPUF with a non-negligible probability,
then using the same forging strategy it can also win the unforgeability game
for the corresponding CPUF with a non-negligible probability. This implies,
that if no QPT weak adversary can win the universal unforgeability game with a
non-negligible probability for the CPUF then no QPT adversary can win the
universal unforgeability game with a non-negligible probability for the
corresponding HPUF. This concludes the proof. ∎

The above theorem is an intuitive result that shows HPUF is stronger or at
least as strong as the underlying CPUF. Although we want to prove a more
powerful and explicit statement regarding HPUFs by quantifying how much the
hybrid construction will boost the security. In fact, we want to show that one
can construct a secure unforgeable HPUF against a quantum adversary even if
the underlying CPUF is breakable (with a certain probability) against the
classical forger. To this end, we compare the success probability of a QPT
adversary in breaking the HPUF in the universal unforgeability game, with the
success probability of the adversary who breaks the CPUF with a certain non-
negligible probability, in a fixed query setting. This, allows us to show that
some of the weak and considerably broken CPUFs can still be used to construct
an asymptotically secure HPUF against stronger quantum adversaries since the
quantum encoding drastically decreases the success probability. Before giving
our main theorem, we need to prove two lemmas. In the first one, we give an
upper bound on the adversary’s guessing probability of the response $f(x_{i})$
corresponding to a challenge $x_{i}$ and a single copy of the quantum response
state $\ket{\psi_{f(x_{i})}}$.

######  Lemma 4.

Let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{4m}$ be a CPUF with the following
property, $\forall~{}~{}x_{i}\in\\{0,1\\}^{n},\forall~{}~{}1\leqslant
j\leqslant 4m,~{}~{}p^{f}_{x_{i}}(y_{i,j}=0)=\frac{1}{2}+\delta_{r},$ (6.73)
with a biased distribution $p=\frac{1}{2}+\delta_{r}$ where
$0\leqslant\delta_{r}\leqslant\frac{1}{2}$, and $\mathcal{E}_{f}$ be a HPUF
corresponding to $f$ that we construct using Construction 3. Let a quantum
adversary $\mathcal{A}$ extract the value $y_{i,(2j-1)}$ out of
$(y_{i,(2j-1)},y_{i,2j})$ from quantum state
$\ket{\psi^{i,j}_{out}}\bra{\psi^{i,j}_{out}}$ corresponding to a random
challenge $x_{i}$. If all the output bits of the CPUF are independent and
identically distributed, then for any quantum adversary $\mathcal{A}$, and
$\forall~{}x_{i}\in\\{0,1\\}^{n}$ then, $\displaystyle
p_{\text{guess}}:=\Pr[\mathcal{A}$
$\displaystyle(x_{i},\ket{\psi^{i,j}_{out}}\bra{\psi^{i,j}_{out}})=y_{i,(2j-1)}]$
$\displaystyle\leqslant p(1+\sqrt{p^{2}+(1-p)^{2}})$ $\displaystyle\leqslant
p(1+\sqrt{2}p)$ (6.74)

###### Proof.

According to Construction 4, for a given $x_{i}$, we use the $2j$-th bit
$y_{i,2j}\in\\{0,1\\}$ of the outcome of the CPUF to choose the basis (either
$\\{\ket{0},\ket{1}\\}$-basis or $\\{\ket{+},\ket{-}\\}$-basis) of the $j$-th
qubit output of the HPUF. Further we use the $y_{i,(2j-1)}\in\\{0,1\\}$ to
choose a state from the chosen basis. Here, if $y_{i,(2j-1)}=0$ then from an
adversarial point of view, the output state is
$\rho_{0}=(\frac{1}{2}+\delta_{r})\ket{0}\bra{0}+(\frac{1}{2}-\delta_{r})\ket{+}\bra{+}$.
Similarly, if $y_{i,(2j-1)}=1$ then from an adversarial point of view, the
output state is
$\rho_{1}=(\frac{1}{2}+\delta_{r})\ket{1}\bra{1}+(\frac{1}{2}-\delta_{r})\ket{-}\bra{-}$.
For the adversary, the probability of correctly guessing $y_{i,(2j-1)}$ is the
same as distinguishing the two states $\rho_{0},\rho_{1}$. Here
$Pr[\mathcal{A}(x_{i},\ket{\psi^{i,j}_{out}}\bra{\psi^{i,j}_{out}})=y_{i,(2j-1)}]$
denotes the optimal probability of guessing the basis correctly. From the
Holevo-Helstorm bound [218] (see Section 2.2) we get,

$\displaystyle\Pr[\mathcal{A}(x_{i},\ket{\psi^{i,j}_{out}}\bra{\psi^{i,j}_{out}})=y_{i,(2j-1)}]$
$\displaystyle\leqslant p[1+\max_{E}\mathsf{Tr}[E(\rho_{0}-\rho_{1})]]$
$\displaystyle=p[1+\frac{1}{2}|\\!|\rho_{0}-\rho_{1}|\\!|_{1}].$
$\displaystyle=p(1+\sqrt{p^{2}+(1-p)^{2}})$ $\displaystyle\leqslant
p(1+\sqrt{2}p)$ (6.75)

This concludes the proof. ∎

The next lemma shows that the adversary needs to extract the classical
information $f(x)$ that is encoded in the quantum state $\ket{\psi_{f(x)}}$
for the forgery of the HPUFs. This will be a key step in our proof, since
using this lemma we can put bounds on the maximum amount of information the
adversary can extract from the overall response state using quantum
information tools we have presented in the preliminaries, in Section 2.1.5.

######  Lemma 5.

Let
$\ket{D_{q}}=\bigotimes_{i=1}^{q}\left(\ket{x_{i}}_{C}\otimes\ket{\psi_{f(x_{i})}}_{R}\right)$
denotes the adversary’s database of $q$ random CRPs that are generated from a
HPUF $\mathcal{E}_{f}:\\{0,1\\}^{n}\rightarrow(\mathcal{H}^{2})^{\otimes m}$.
Let $E(D_{q})$ denote the optimal measurement strategy for forging the HPUF
with probability $p_{\text{forge}}$ using the database $D_{q}$, then the
following measure-then-forge strategy can optimally forge the HPUF with the
same probability $p_{\text{forge}}$. • Adversary extracts the classical
encoding $\\{f(x_{i})\\}_{1\leqslant i\leqslant q}$ from $\ket{D_{q}}$. Let
$\\{\tilde{f}(x_{i})\\}_{1\leqslant i\leqslant q}$ denotes the extracted
classical string. • The QPT adversary applies a forging strategy using the
extracted data set $\\{\tilde{f}(x_{i})\\}_{1\leqslant i\leqslant q}$.

###### Proof.

For a successful forgery, the adversary needs to win the universal
unforgeability game that we define in Game 2 in Chapter 3. This implies, using
the measurement strategy $E(D_{q})$ the adversary needs to produce a quantum
state $\ket{\psi_{f(x^{*})}}$ corresponding to a challenge
$x^{*}\in_{R}\\{0,1\\}^{n}$ that is chosen uniformly at random. Without loss
of generality we can write the measurement strategy as a POVM with two
outcomes
$E(D_{q})=\\{E_{\text{forge}}(D_{q},x^{*}),E_{\text{fail}}(D_{q},x^{*})\\}$,
where $E_{\text{forge}}(D_{q},x^{*}),E_{\text{fail}}(D_{q},x^{*})$ denote the
measurement operators corresponding to the successful forgery and the failure
forgery respectively. Therefore, we can write the successful forging
probability $p_{\text{forge}}$ as follows.

$p_{\text{forge}}=\mathsf{Tr}[E_{\text{forge}}(D_{q},x^{*})\rho_{D_{q}}^{x^{*}}],$
(6.76)

where
$\rho_{D_{q}}^{x^{*}}:=\ket{D_{q}}\bra{D_{q}}\otimes\ket{x^{*}}\bra{x^{*}}\otimes\ket{0^{m}}_{out}\bra{0^{m}}$.
Here the $out$ register would contain the forged state. If we write
$E_{\text{forge}}(D_{q},x^{*})=M^{\dagger}_{\text{forge}}(D_{q},x^{*})M_{\text{forge}}(D_{q},x^{*})$,
then we can rewrite the post-measurement state corresponding to the successful
forgery as follows:

$\frac{M_{\text{forge}}(D_{q},x^{*})\ket{D_{q}}\otimes\ket{x^{*}}\otimes\ket{0^{m^{\prime}}}_{out}}{\sqrt{p_{\text{forge}}}}=\frac{\ket{\tilde{D}_{q}}_{R}\otimes\ket{x^{*}}\otimes\ket{\psi_{f(x^{*})}}_{out}\otimes\ket{\tilde{a}}_{out}}{\sqrt{p_{\text{forge}}}},$
(6.77)

where $|\tilde{D}_{q}\rangle_{R}$ denotes the post-measurement database state,
and $\ket{\tilde{a}}_{out}$ is the post-measurement state of the ancillary
system which is a $(m^{\prime}-m)$ dimensional state while as
$\ket{\psi_{f(x^{*})}}_{out}$ is $m$ dimensional. As
$\bigotimes_{i=1}^{q}|x_{i}\rangle_{C}$ is a classical state, in the rest of
the proof we don’t write them in the expressions.

Using the _Neimark’s theorem_ 888The version of Neimark’s theorem, is similar
but more genral than the one we introduced in Section 2.2. we can replace the
POVM measurement strategy $E(D_{q})$ with the combination of a unitary acting
on an extended system including an ancilla $\ket{anc}_{A}$, followed by a
projective measurement. Let us denote the unitary as $U^{x^{*}}_{D_{q}}$ which
couples the input state $\ket{D_{q}}\otimes\ket{0^{m^{\prime}}}_{out}$ with
the ancillary system $|anc\rangle_{A}$, and let $\\{|v\rangle\\}$ be the basis
on which the projective measurement is applied to the ancilla. We first
rewrite the impact of the unitary $U^{x^{*}}_{D_{q}}$ on the input state:

$\displaystyle
U^{x^{*}}_{D_{q}}\left(\bigotimes_{i=1}^{q}\ket{\psi_{f(x_{i})}}_{R}\otimes\ket{0}_{out}\otimes\ket{anc}_{A}\right)$
$\displaystyle=U^{x^{*}}_{D_{q}}\left(\ket{\Psi^{q}_{f}}_{R}\otimes\ket{0}_{out}\otimes\ket{anc}_{A}\right)$
$\displaystyle=\sum_{v}\sqrt{p_{v}}\ket{\Psi^{q}_{v}}_{R}\otimes\ket{\tilde{\psi}_{v}}_{out}\otimes\ket{v}_{A}.$
(6.78)

where in the second line we have rewritten everything after applying the
unitary in the $\\{\ket{v}\\}$-basis. Now, the adversary performs a projective
measurement on the state Eq. (6.4.5) in this basis. Suppose for the correct
forgery, the ancilla is projected into the $\ket{v_{\text{forge}}}_{A}$ state.
Therefore we can rewrite the expression of $p_{\text{forge}}$ as follows:

$p_{\text{forge}}=\sum_{v:v=v_{\text{forge}}}p_{v}|\bra{v_{\text{forge}}}v\rangle|^{2}.$
(6.79)

Overall, following this strategy, the purification of the adversary’s post-
measurement state with an optimal POVM measurement, can be written as the
following:

$\frac{\ket{\tilde{D}_{q}}_{R}\otimes\ket{x^{*}}\otimes\ket{\psi_{f(x^{*})}}_{out}\otimes\ket{v_{\text{forge}}}_{A}}{\sqrt{p_{\text{forge}}}},$
(6.80)

where $\ket{\tilde{D}_{q}}$ denotes the post-measurement database state. Note
that, due to Neimark’s theorem the post-measurement database states in
Equation Eq. (6.77), and Eq. (6.80) are the same, if the same ancillary
systems has been assumed after the purification and POVM, _i.e._ if
$\ket{v_{\text{forge}}}_{A}=\ket{\tilde{a}}_{out}$.

Now, let us use the unitary $U^{x^{*}}_{D_{q}}$ and the measurement basis
$\\{\ket{v}\\}$ to construct a _measure-then-forge_ strategy. As the unitary
$U^{x^{*}}_{D_{q}}$ only depends on the input $x^{*}$ and $D_{q}$, we can
rewrite it in the basis that is diagonalised with respect to the states
$\\{\ket{\Psi^{q}_{v},v}\\}_{v}$. For the post-measurement state
$\ket{v_{\text{forge}}}$, of the ancilla, the adversary applies
$U^{x,x^{*}}_{D_{q},\Psi^{q}_{\text{forge}},v_{\text{forge}}}$ on the
$\ket{0}_{out}$ register. Note that, the adversary doesn’t have any
information about the $\\{f(x_{i})\\}_{1\leqslant i\leqslant q}$ before
measuring the ancillary sub-system in the $\\{\ket{v}\\}$-basis. Hence, the
measurement basis $\\{\ket{v}\\}$ choice only depends on the classical
challenges $x_{i}$’s and $x^{*}$. Therefore, the adversary can use the same
information to find the $\\{\ket{v}\\}$-basis, and first performs the
measurement on the $RA$ register in $\\{\ket{\Psi^{q}_{v},v}\\}$-basis, and
obtains the state $\ket{\Psi^{q}_{\text{forge}},v_{\text{forge}}}$ with the
same probability $p_{\text{forge}}$. After the measurement, the adversary
applies the unitary
$U^{x^{*}}_{D_{q},\Psi^{q}_{\text{forge}},v_{\text{forge}}}$ on
$\ket{0}_{out}$, and get the forged state $\ket{\psi_{f(x^{*})}}$. Therefore,
with this strategy the adversary also win the unforgeability game with the
probability $p_{\text{forge}}$.

Note that, there always exists a unitary $U$ such that
$U(\bigotimes_{i=1}^{q}\ket{\tilde{f}(x_{i})})\otimes\ket{anc}=\ket{\Psi^{q}_{\text{forge}},v_{\text{forge}}}$,
where $\tilde{f}(x_{i})$ denotes the extracted information about $f(x_{i})$’s
from the encoded database $\ket{D_{q}}$. Therefore, from any generalised
measurement strategy $E(D_{q})$ we can construct a strategy for the measure-
then-forge protocol that can win the universal unforgeability game with the
same probability $p_{\text{forge}}$. This concludes the proof. ∎

Lemma 5 suggests that an optimal strategy of the adversary including general
POVM strategies, is equivalent to optimally extracting the classical
information from the database (state $\ket{D_{q}}$) and then performing the
most optimal forgery strategy on the measurement results. In general, if the
extracted classical information $\\{\tilde{f}(x_{i})\\}_{1\leqslant i\leqslant
q}$ from the database state $\ket{D_{q}}$ is very far from the original
encoded string $\\{f(x_{i})\\}_{1\leqslant i\leqslant q}$ then the forgery
will not perform well and the overall forgery attack will have a low
probability. Based on this, we now bound the overall amount of information
that can be extracted from the outputs of HPUF, using the information
quantities such as min-entropy and we will show how much the quantum encoding
will contribute to reducing the success probability.

######  Theorem 45.

Let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{4m}$ be a classical PUF with
$p$-randomness, where $p=\frac{1}{2}+\delta_{r}$. Let
$p^{\text{classic}}_{\text{forge}}(m,p,q)$ denote the optimal success
probability of any $q$-query weak quantum adversary to wins the universal
unforgeability game for the CPUF $f$. Then a $q$-query weak quantum adversary
can win the universal unforgeability game for the HPUF $\mathcal{E}_{f}$ at
most the following probability
$p_{\text{forge}}^{\text{quant}}(m,p,q)=p_{\text{forge}}^{\text{classic}}(m,p,q)\times(p(1+\sqrt{2}p))^{2mq}$
(6.81)

###### Proof.

We want to quantify the success probability of the QPT adversary in attacking
HPUF, in comparison with the QPT adversary who attacks the classical PUF with
a fixed number of queries. Let $\mathcal{A}_{c}$ be the QPT adversary
attempting to forge CPUF, where they produce a classical forgery $f(x^{*})$
for a randomly selected challenge $x^{*}$, from a classical database
consisting of $q$ pairs of $\\{(x_{i},f(x_{i}))\\}^{q}_{i=1}$ input-outputs of
CPUF with probability $p^{\text{classic}}_{\text{forge}}(m,p,q)$. Note that in
general the success probability, is a function of the CPUF’s randomness
parameter $p$, the output size $m$ and the number of queries $q$. Let
$\mathcal{A}_{h}$ be a quantum adversary who plays the unforgeability game
against the HPUF. $\mathcal{A}_{h}$ has access to $q$ queries of HPUF included
in the database state $\ket{D_{q}}$. The goal of $\mathcal{A}_{h}$ is to
produce a valid forgery $\ket{\psi_{f(x^{*})}}$ for a random challenge
$x^{*}$. Let $p_{\text{forge}}^{\text{quant}}$ be the optimal success
probability of any adversary in successfully doing so.

Now, for the purpose of the proof, we introduce another intermediate quantum
adversary $\mathcal{B}$ who plays the same version of the unforgeability game
as $\mathcal{A}_{h}$, although has access to a combined database of
$\mathcal{A}_{h}$ and $\mathcal{A}_{c}$ _i.e._ the triplet
$\\{(x_{i},f(x_{i}),\ket{\psi_{f(x_{i})}})\\}^{q}_{i=1}$, and will output a
valid forgery of the form $\ket{\psi_{f(x^{*})}}$ for a random challenge
$x^{*}$. We show that the adversaries $\mathcal{A}_{c}$ and $\mathcal{B}$ are
equivalent in the success probability up to a negligible factor. First, note
that $\mathcal{B}$ is obviously at least as strong as $\mathcal{A}_{c}$ since
has an extended database, and can simply ignore the quantum encoded detest and
run $\mathcal{A}_{c}$ as a subroutine so we have
$p_{\mathcal{B}}(m,p,q)\geqslant p^{\text{classic}}_{\text{forge}}(m,p,q)$.
But on the other hand, $\mathcal{A}_{c}$ can also locally construct the third
column of the database $\ket{\psi_{f(x_{i})}}$ easily and run $\mathcal{B}$ as
a subroutine. Then $\mathcal{A}_{c}$ can use this to produce polynomial many
copies of $\ket{\psi_{f(x^{*})}}$ and measure them with the optimal POVM
measurement and get $f(x^{*})$ with very high probability (See the proof of
Theorem 44). Also note that by definition of the unforgeability game,
$\mathcal{B}$ produces the forgery with non-negligible success probability,
meaning that the $\ket{\psi_{f(x^{*})}}$ is close to the actual BB84 encoding
of $f(x^{*})$ (in terms of fidelity). Thus $\mathcal{B}$ has at most a
negligible advantage over $\mathcal{A}_{c}$ and we can conclude:
$p_{\mathcal{B}}(m,p,q)\approx p^{\text{classic}}_{\text{forge}}(m,p,q)$.

Now we have two adversaries who produce quantum state as a forgery and we can
compare the success probability of $\mathcal{A}_{h}$ with $\mathcal{B}$, which
are both QPT adversaries producing the same quantum forgery while having
access to different input databases since $\mathcal{B}$ has the underlying
classical information $f(x_{i})$ for each encoded quantum query, while
$\mathcal{A}_{h}$ has only access to the encoded states in the form of
$\ket{\psi_{f(x_{i})}}$. We compare the success probability of these two
adversaries by comparing the accessible amount of information via entropy
inequalities. First we note that according to Lemma 5, the optimal forgery for
a quantum adversary includes optimally extracting the classical information
then applying the forgery (which is equivalent to the classical forgery on the
classical database). This exactly quantifies the relation between the success
probabilities of $\mathcal{A}_{h}$ with $\mathcal{B}$ which will give us the
reduction to the problem of extracting information from the quantum-classical
database of $\mathcal{A}_{h}$.

To do so, we reformulate the forging probability (the success probability of
the adversary in the unforgeability game) in terms of quantum processing. We
consider $\mathcal{B}$ as a CPTP map over a database of size $N$, denoted as
$\rho^{\mathcal{B}^{N}}$, where each input
$\rho^{\mathcal{B}}_{i}=\ket{x_{i}}\bra{x_{i}}\otimes\ket{f(x_{i})}\bra{f(x_{i})}\otimes\ket{\psi_{f(x_{i})}}\bra{\psi_{f(x_{i})}}$
is a classical-quantum state. Adversary $\mathcal{A}_{h}$ can be defined
directly from $\mathcal{B}$ through another CPTP map which we denote by
$\Lambda_{h}$. For each record we have
$\rho^{\mathcal{A}_{h}}_{i}=\Lambda_{h}(\rho^{\mathcal{B}}_{i})$. Assuming the
queries to be i.i.d and the way we have defined these two adversaries, The
overall action of the CPTP map $\mathcal{A}_{h}$ is captured by the density
matrix $\rho^{\mathcal{A}_{h}^{N}}=\Lambda_{h}^{\otimes
N}(\rho^{\mathcal{B}^{N}})$. Also, let $F$ represent the random variable of
getting the correct output of the PUF, over the uniform choice of the input
$x^{*}$, by processing the given input database.

We now use the inequality for conditional min-entropy to relate the above
success probability. Using Lemma 5 stating that the optimal strategy is
equivalent to extracting the underlying classical information (optimal state
discrimination) and then run an optimal forgery algorithm that depends on the
extracted information. Thus we can write the success probability of
$\mathcal{A}_{h}$ in terms of the extraction probability as follows:

$p_{\text{forge}}^{\text{quant}}(m,p,q)=p_{\text{extract}}\times
p_{\mathcal{B}}(m,p,q)=2^{-H_{min}(F|C^{N})}$ (6.82)

where $C^{N}$ denotes $\rho^{\mathcal{A}_{h}^{N}}$ as the full quantum system
of $\mathcal{A}_{h}$ and also let $C$ denotes $\rho^{\mathcal{A}_{h}}$ which
is the single-qubit database of $\mathcal{A}_{h}$. We can rewrite the success
probability of forgery for adversary $\mathcal{B}$, in terms of the min-
entropy as follows:

$p_{\mathcal{B}}(m,p,q)=p^{\mathcal{B}}_{\text{forge}}=2^{-H_{min}(F|B^{N})}$
(6.83)

Where $B^{N}$ represent the full system of $\mathcal{B}^{N}$ _i.e._
$\rho^{\mathcal{B}^{N}}$ for short. Now for the single-qubit database, the
following relation holds:

$H_{min}(F|C)\geqslant H_{min}(\tilde{Y}|C)+H_{min}(F|\tilde{Y})$ (6.84)

Where $\tilde{Y}$ denotes the random variable of the estimated output $Y=f(X)$
which is the 2-bit fraction of the output of CPUF. We also note that
$H_{min}(F|\tilde{Y})\geqslant H_{min}(F|B)$, and the equality is when the
$\tilde{Y}$ is arbitrarily close to $Y$. As a result we have999This inequality
in fact gives and improvement to the data processing inequality (introduced in
Section 2.1.5) for our specific case. Since according to the data-processing
inequality we have that the entropy min-entropy increases via any CPTP channel
acting on the joint state of the system, which results in
$H_{min}(F|B)\leqslant H_{min}(F|C)$ which denotes that the success
probability of adversary $\mathcal{B}$ who has access to additional classical
output is higher than $\mathcal{A}_{h}$. The new inequality quantifies the
bound on the difference.:

$H_{min}(F|C)\geqslant H_{min}(\tilde{Y}|C)+H_{min}(F|B)$ (6.85)

Extending to $N$-fold database we have:

$H_{min}(F|C^{N})\geqslant H_{min}(\tilde{Y}^{N}|C^{N})+H_{min}(F|B^{N})$
(6.86)

Next, we need to relate the first term of the right-hand side, which denoted
the min-entropy of extracting information from all $N$ given qubits to the
min-entropy quantity $H_{min}(\tilde{Y}|C)$. For that, we use the quantum-
classical AEP that we have introduced in Theorem 4 as follows:

$H^{\varepsilon}_{min}(\tilde{Y}^{N}|C^{N})\geqslant
N(H(\rho_{\tilde{Y}C})-H(\rho_{C}))-N\eta$ (6.87)

where
$\eta:=(2H_{max}(\rho_{F})+3)\sqrt{\frac{\log(\frac{1}{\varepsilon})}{N}+1}$,
is a function of the smoothing parameter $\varepsilon$ and $N$. Here we select
the smoothing parameter $\varepsilon$ such that $N\eta$ becomes a negligible
function in the security parameter. Given that
$H(\tilde{Y}|C)=H(\rho_{\tilde{Y}C})-H(\rho_{C})$ and the fact that
$H_{min}(\tilde{Y}|C)\leqslant H(\tilde{Y}|C)$, we have:

$H^{\varepsilon}_{min}(\tilde{Y}|C^{N})\geqslant NH_{min}(\tilde{Y}|C)$ (6.88)

By substituting the above inequality back into 6.86, we can conclude the
following:

$H_{min}(F|C^{N})\geqslant NH_{min}(\tilde{Y}|C)+H_{min}(F|B^{N})$ (6.89)

The final step is to determine $N$. We note that there exist $q$ number of
i.i.d queries in each database, but each query itself consists of a $2m$
number of qubits in tensor product form. Although the effective size or the
amount of information included in these $2m$ qubits depends on the bias of the
PUF. In general, using quantum data compression inequality, the effective size
of such $2m$ tensor product states is given by $2mS(\rho_{f})$, where
$S(\rho_{f})$ is the von-Neumann entropy of each encoded state $\rho_{f}$
given as follows concerning the HPUF construction and the PUF bias:

$\rho_{f}=(\frac{1}{2}+\delta_{r})^{2}\ket{0}\bra{0}+(\frac{1}{4}-\delta_{r}^{2})(\ket{1}\bra{1}+\ket{+}\bra{+})+(\frac{1}{2}-\delta_{r})^{2}\ket{-}\bra{-}$
(6.90)

We can then calculate $S(\rho_{f})$ which gives the following result while we
are discarding $\mathcal{O}(\delta^{3})$ and higher:

$S(\rho_{f})=1-(\frac{1}{2}-\delta_{r})\log(1-2\delta_{r})-(\frac{1}{2}+\delta_{r})\log(1+2\delta_{r})$
(6.91)

Let us call
$g(\delta_{r})=(\frac{1}{2}-\delta_{r})\log(1-2\delta_{r})+(\frac{1}{2}+\delta_{r})\log(1+2\delta_{r})$
Thus we have $N\approx 2mq-2mqg(\delta_{r})$. Also, for small enough values of
$\delta_{r}$, we have $g(\delta_{r})\approx 0$. Let us also denote
$H_{min}(\tilde{Y}|C)=-\log(p^{1}_{\text{extract}})$. Where
$p^{1}_{\text{extract}}$ is the probability of extracting the classical
information from a single qubit. We can then conclude the following relations
between the success probabilities:

$p_{\text{forge}}^{\text{quant}}(m,p,q)\leqslant
p_{\mathcal{B}}(m,p,q)\times(p^{1}_{\text{extract}})^{2mq-2mqg(\delta_{r})}$
(6.92)

For our given construction
$p^{1}_{\text{extract}}=p_{\text{guess}}=p(1+\sqrt{2}p)$ according to the
optimal discrimination probability given in Lemma 4. Thus we can rewrite the
above equation as:

$\begin{split}p_{\text{forge}}^{\text{quant}}(m,p,q)&\leqslant
p_{\text{forge}}^{\text{classic}}(m,p,q)\times(p(1+\sqrt{2}p))^{2mq-2mqg(\delta_{r})}\\\
&\approx
p_{\text{forge}}^{\text{classic}}(m,p,q)\times(p(1+\sqrt{2}p))^{2mq}\end{split}$
(6.93)

which is the bound we wanted to prove, and we have also used that
$p_{\text{forge}}^{\text{classic}}(m,p,q)\approx p_{\mathcal{B}}(m,p,q)$. As a
final remark, we note that the optimal probability is a function of the number
of queries, thus we can show that the optimal overall probability is achieved
given the adversary optimises on the number of queries used for extracting the
information for the forgery. Analysing the upper bound of the probability as a
function of $q$, one can see that the first term is a non-decreasing function
of $q$ while the second term is always strictly decreasing with $q$. As a
result, the combined function has necessary an extremum over $q$, which we
denote by $q_{opt}$. Assuming the two cases where the given number of queries
is smaller or larger than $q_{opt}$, we have the following bounds:

$\begin{split}&p_{\text{forge}}^{\text{quant}}\leqslant
p_{\text{forge}}^{\text{classic}}(m,p,q)\times(p_{\text{guess}})^{2mq(1-g(\delta_{r}))}\quad\quad\quad\quad
q<q_{opt}\\\ &p_{\text{forge}}^{\text{quant}}\leqslant
p_{\text{forge}}^{\text{classic}}(m,p,q_{opt})\times(p_{\text{guess}})^{2mq_{opt}(1-g(\delta_{r}))}\quad\quad
q\geqslant q_{opt}\end{split}$ (6.94)

Summarizing the above cased and given that $g(\delta_{r})$ is small we have:

$p_{\text{forge}}^{\text{quant}}\leqslant\sup_{q}[p_{\text{forge}}^{\text{classic}}(m,p,q)\times(p_{\text{guess}})^{2mq}]$
(6.95)

which concludes the proof.101010In the latest version of the paper [110], we
have given an alternative version of this proof which does not use the AEP,
and instead relies on giving the bound on the forgery probability over a noisy
database where the bound is slightly different although very similar. The
exponential decay in the probability happens in both cases. In that proof, one
no longer needs to give an optimality argument over the number of queries.
However, since proving the result, in this way seemed more intuitive and used
a rather nice quantum information tools, we have decided to present this proof
in the thesis. The reader can refer to the paper for the other result. ∎

Finally, let us present the following corollary that ensures the universal
unforgeability of an HPUF constructed from a CPUF that does not provide
suitable security, yet is not totally broken with overwhelming probability.

######  Corollary 8.

Let the success probability of any QPT weak-adversary in the universal
unforgeability game with a CPUF $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{4m}$
with $p$-randomness, be at most $p^{\text{classic}}_{\text{forge}}$, where
$0\leqslant p^{\text{classic}}_{\text{forge}}\leqslant 1-\text{non-negl}(2m)$.
Then, the success probability of any QPT adversary in the universal
unforgeability game for the HPUF $\mathcal{E}_{f}$, is at most
$\varepsilon(2m)$, which is a negligible function in the security parameter.
Hence such HPUFs are universally unforgeable.

###### Proof.

This directly follows from Theorem 45 where
$p^{\text{classic}}_{\text{forge}}=p_{\text{forge}}^{\text{classic}}(m,p,q)$
for any $q=poly(m)$ is a value between $0$ and $1$, and not negligibly close
to $1$. As shown in the proof of Theorem 45 the second term of the
probability, becomes negligibly small (in $2m$) and hence the overall
probability becomes a negligible function $\varepsilon(2m)$. ∎

##### Universal Unforgeability of HLPUF

So far, we have analysed the security of the HPUFs only against weak
adversaries. In the next theorem, we show that if the HPUF is secure against
weak adversaries, then using the locking mechanism, we can make the HLPUF
secure against adaptive adversaries.

######  Theorem 46.

Let $\mathcal{E}_{f}:\\{0,1\\}^{n}\rightarrow(\mathcal{H}^{2})^{\otimes
m}\otimes(\mathcal{H}^{2})^{\otimes m}$ be a hybrid PUF that we construct from
a classical PUF $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{2m}\times\\{0,1\\}^{2m}$
and let $\mathcal{E}^{L}_{f}:\\{0,1\\}^{n}\times(\mathcal{H}^{2})^{\otimes
m}\rightarrow(\mathcal{H}^{2})^{\otimes m}$ denotes the HLPUF that we
construct from $\mathcal{E}_{f}$ using the Construction 4. If
$\mathcal{E}_{f}=\mathcal{E}_{f_{1}}\otimes\mathcal{E}_{f_{2}}$ and if each of
the mappings $\mathcal{E}_{f_{1}},\mathcal{E}_{f_{2}}$ has
$(\varepsilon,m)$-universal unforgeability against the $q$-query weak
adversaries, then the corresponding HLPUF $\mathcal{E}^{L}_{f}$ is
$(\varepsilon,m)$-secure against the $q$-query adaptive adversaries.

###### Proof.

At the $i$-th round, the HLPUF $\mathcal{E}^{L}_{f}$ receives the queries of
the form $(x_{i},\tilde{\rho}_{1})$, where the classical string
$x_{i}\in\\{0,1\\}^{n}$, and $\tilde{\rho}_{1}\in(\mathcal{H}^{2})^{\otimes
m}$. The HLPUF returns $\mathcal{E}_{f_{2}}(x_{i})$ if
$\texttt{Ver}(\tilde{\rho}^{i}_{i},\mathcal{E}_{f_{1}}(x_{i}))=1$, otherwise
it returns an abort state $\ket{{\perp}}\bra{\perp}$ corresponding to $\perp$.
Hence, to avoid getting state $\ket{\perp}$ from the HLPUF, the adaptive
adversaries $\mathcal{A}_{ad}$ need to produce a query of the form
$(x_{i},\mathcal{E}_{f_{1}}(x_{i}))$. As the adversary doesn’t have any direct
access to the mapping $\mathcal{E}_{f_{1}}$, the only way it can get any
information about $\mathcal{E}_{f_{1}}(x_{i})$ by intercepting the challenges
that are sent by the server to the client. Suppose that the adaptive adversary
has access to a set of $q$ queries $X_{[q]}:=\\{X_{i}\\}_{1\leqslant
i\leqslant q}$ and the corresponding responses
$\Psi_{[q]}:=\\{\mathcal{E}_{f_{1}}(x_{i})\\}_{1\leqslant i\leqslant q}$. Here
each $X_{i}$ follows a uniform distribution over the challenge set
$\\{0,1\\}^{n}$. Hence, for the mapping $\mathcal{E}_{f_{1}}$ the power of the
adaptive adversary reduces to the power of a weak adversary. As
$\mathcal{E}_{f_{1}}$ has the universal unforgeability property against any
$q$-query weak adversary, hence we get, for any random challenge $X\not\in
X_{[q]}$,

$\Pr_{X,X_{[q]}}[1\leftarrow\mathcal{G}^{\mathcal{E}_{f_{1}}}(\mathcal{A}_{ad},m,X,X_{[q]})]=\Pr_{X,X_{[q]}}[1\leftarrow\mathcal{G}^{\mathcal{E}_{f_{1}}}(\mathcal{A}_{weak},m,X,X_{[q]})]\leqslant\varepsilon(m).$
(6.96)

This implies, that using the set of challenges $X_{[q]}$ and responses
$\Psi_{[q]}$ the adversary cannot produce the response corresponding to a
random challenge $X\not\in X_{[q]}$. Suppose from the query set $X_{[q]}$ and
the responses, the adaptive adversary successfully generates a set
$X^{\prime}_{[q^{\prime}]}$ of $q^{\prime}$ adaptive queries, and
corresponding responses $\Psi_{[q^{\prime}]}$ for the HLPUF
$\mathcal{E}^{L}_{f}$. Without any loss of generality we assume that for all
of the queries $X^{\prime}_{i}\in X^{\prime}_{[q^{\prime}]}$ the HLPUF returns
a non-abort state. We assume that the adaptive adversary wins the universal
unforgeability game using the query set $X_{\text{ad}}=X_{[q]}\cap
X^{\prime}_{[q^{\prime}]}$. This implies,

$\Pr_{X,X^{\mathcal{E}_{L}}_{[q]_{\text{ad}}}}[1\leftarrow\mathcal{G}^{\mathcal{E}^{L}_{f}}(\mathcal{A}_{ad},m,X,X_{\text{ad}})]\geqslant\text{non-
negl}(m).$ (6.97)

From the HLPUF Construction 4, we get that winning the universal
unforgeability game with the HLPUF $\mathcal{E}^{L}_{f}$ implies winning the
universal unforgeability with $\mathcal{E}_{f_{2}}$. Hence, we can rewrite Eq.
(6.97) in the following way,

$\Pr_{X,X_{\text{ad}}}[1\leftarrow\mathcal{G}^{\mathcal{E}_{f_{2}}}(\mathcal{A}_{ad},m,X,X_{\text{ad}})]\geqslant\text{non-
negl}(m).$ (6.98)

Note that, if the adaptive adversary manages to get non-abort outcomes from
the HLPUF corresponding to all $X^{\prime}_{i}\in X_{\text{ad}}$ then from the
Construction 4 we get,
$1\leftarrow\mathcal{G}^{\mathcal{E}_{f_{1}}}(\mathcal{A}_{ad},m,X^{\prime}_{i},X_{\text{ad}})$.
Due to the unforgeability assumption of Equation Eq. (6.96) we have,

$\Pr_{X,X_{[q]}}[1\leftarrow\mathcal{G}^{\mathcal{E}_{f_{1}}}(\mathcal{A}_{weak},m,X,X_{[q]})]=\Pr_{X,X_{\text{ad}}}[1\leftarrow\mathcal{G}^{\mathcal{E}_{f_{1}}}(\mathcal{A}_{ad},m,X,X_{\text{ad}})]\leqslant\varepsilon(m).$
(6.99)

Note that, the main difference between adaptive and weak adversaries lies in
the choice of the query set. If we fix the query set $X_{\text{ad}}$, then
both adaptive $\mathcal{A}_{ad}$ and a weak adversary can extract the same
amount of information from the responses corresponding to the query set
$X_{\text{ad}}$. Therefore, their winning probability of the universal
unforgeability game becomes equivalent. This implies, we can rewrite Equation
Eq. (6.99) in the following way,

$\Pr_{X,X_{\text{ad}}}[1\leftarrow\mathcal{G}^{\mathcal{E}_{f_{1}}}(\mathcal{A}_{ad},m,X,X_{\text{ad}})]=\Pr_{X,X_{\text{ad}}}[1\leftarrow\mathcal{G}^{\mathcal{E}_{f_{1}}}(\mathcal{A}_{weak},m,X,X_{\text{ad}})]\leqslant\varepsilon(m).$
(6.100)

By combining Equation Eq. (6.99) and Equation Eq. (6.100) we get, both the
random variables $X_{[q]}$ and $X_{\text{ad}}$ are equivalent. From the
universal unforgeability property of the PUF $\mathcal{E}_{f_{2}}$ against any
$q$-query weak adversary, we get

$\Pr_{X,X_{[q]}}[1\leftarrow\mathcal{G}^{\mathcal{E}_{f_{2}}}(\mathcal{A}_{weak},m,X,X_{[q]})]\leqslant\varepsilon(m).$
(6.101)

As both of the random variables $X_{[q]}$ and $X_{\text{ad}}$ are equivalent,
so we get,

$\begin{split}&\Pr_{X,X_{[q]}}[1\leftarrow\mathcal{G}^{\mathcal{E}_{f_{2}}}(\mathcal{A}_{weak},m,X,X_{[q]})]\\\
&=\Pr_{X,X_{\text{ad}}}[1\leftarrow\mathcal{G}^{\mathcal{E}_{f_{2}}}(\mathcal{A}_{weak},m,X,X_{\text{ad}})]\\\
&=\Pr_{X,X_{\text{ad}}}[1\leftarrow\mathcal{G}^{\mathcal{E}_{f_{2}}}(\mathcal{A}_{ad},m,X,X_{\text{ad}})]\leqslant\varepsilon(m).\end{split}$
(6.102)

The second equality follows from the fact that for a fixed query set
$X_{\text{ad}}$ the adaptive adversary $\mathcal{A}_{ad}$ and weak adversary
$\mathcal{A}_{weak}$ becomes equivalent. Note that, only one of Eq. (6.98) and
Eq. (6.102) is true. The Eq. (6.102) is true because of the unforgeability of
$\mathcal{E}_{f_{2}}$. Hence, our assumption of Eq. (6.98) is wrong.
Therefore, Eq. (6.97) is also not true. Hence, with conclude our proof by
contradiction. ∎

Apart from the theoretical results provided in this section, we have also
simulated the design of HPUF constructions with underlying silicon CPUFs
instantiated by _pypuf_ [409] which is a python-based emulator that features
different existing CPUFs. Furthermore, we simulate the situation where an
adversary acquires classical challenges and quantum-encoded responses from
HPUF and converts the response into classical bit string by measurement
behaviour. The adversary then performs some machine learning-based attacks
with CRPs to reproduce a model that accurately predicts enough the behaviours
of underlying CPUF. Such an adversary possibly forges the HPUF given
(exponentially in the security parameter) many CRPs. Our simulation results
assist to demonstrate the exponential gap in the security between CPUF and
HPUF in a regime outside the polynomial-size database and for classical PUFs
that are commercially available. Since the simulations have not been done by
the author, we have excluded them from this chapter. However, we refer the
reader to [110] for the full work, including the simulation results.

##### Security of the HLPUF-based authentication protocol:

We now have all the elements to be able to prove the completeness and security
(or soundness) of our HLPUF-based authentication protocol. Firstly, we define
the completeness and security property for Protocol 5. Then, in Theorem 47 we
will prove that they are satisfied. We start with the completeness:

######  Definition 48 (Completeness of HLPUF-based Authentication Protocol 5).

We say the HLPUF-based authentication Protocol 5 satisfies completeness if in
the absence of any adversary, an honest verifier and prover generating
$\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}}$ and
$\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}}$ with a valid HLPUF for
any selected challenge $x_{i}$, can pass the verification algorithms with
overwhelming probability:
$Pr[\texttt{Ver}(\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}},\tilde{\rho}_{1})=\texttt{Ver}(\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}},\tilde{\rho}_{2})=1]\geqslant
1-\varepsilon(\lambda)$ (6.103)

We also define the security of the protocol, in relation to the universal
unforgeability game as follows:

######  Definition 49 (Security of the HLPUF-based Authentication Protocol 5).

We say the HLPUF-based authentication Protocol 5 is secure if the success
probability of any QPT adaptive adversary $\mathcal{A}_{ad}$ in winning the
universal unforgeability game to forge an output of HLPUF according to
Construction 4, for any randomly selected challenge of the form
$\tilde{c}=(x,\ket{\psi_{f_{1}(x)}}\bra{\psi_{f_{1}(x)}})$ is at most
negligible in the security parameter:
$Pr[1\leftarrow\mathcal{G}^{HLPUF}(\mathcal{A}_{ad},\lambda)]\leqslant\varepsilon(\lambda)$
(6.104) where the verification algorithm of the universal unforgeability game
checks the adversary’s output $\sigma_{2}$, with the output of the HLPUF,
$\ket{\psi_{f_{2}(x)}}\bra{\psi_{f_{2}(x)}}$.

Through the following theorem, we can see that Protocol 5 satisfies both
completeness and security according to the above definitions.

######  Theorem 47.

If the HLPUF $\mathcal{E}^{L}_{f}$ is constructed from a hybrid PUF
$\mathcal{E}_{f}$ using Construction 4, then the HLPUF-based authentication
Protocol 5 satisfies both the completeness and security conditions.

###### Proof.

In Protocol 5 with hybrid PUF
$\mathcal{E}_{f}=\mathcal{E}_{f_{1}}\otimes\mathcal{E}_{f_{2}}$, the
verifier(server) chooses the classical input $x_{i}\in\mathcal{X}$, encodes
the quantum state corresponding to $2m$ bits of $f_{1}(x_{i})$ and issues the
joint state to the prover(client). If there is no adversary, the prover
receives the joint state and queries $\mathcal{E}_{f}$ with $x_{i}$ and
$\tilde{\rho}_{1}$, where
$\tilde{\rho}_{1}=\mathcal{E}_{f_{1}}(x_{i})=\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}}$
for the first $m$ qubits of $\mathcal{E}_{f}(x_{i})$. Hence we have:

$Pr\left[\texttt{Ver}(\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}},\tilde{\rho}_{1})=1\right]=1$
(6.105)

On the prover’s side, since the verification algorithm of HLPUF
$\mathcal{E}_{f}^{L}$ always passes with
$\texttt{Ver}(\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}},\tilde{\rho}_{1})=1$,
and they return the quantum state
$\mathcal{E}_{f_{2}}(x_{i})=\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}}$
corresponding to $2m$ bits of $f_{2}(x_{i})$ to the verifier. Without the
presence of adversary, the verifier always receives the state with
$\tilde{\rho}_{2}=\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}}$, and we
obtain the equation similarly to Eq. (6.105). Therefore, we can say the HLPUF-
based authentication protocol satisfies the completeness condition with

$\text{Pr}\left[\texttt{Ver}(\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}},\tilde{\rho}_{1})=\texttt{Ver}(\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}},\tilde{\rho}_{2})=1\right]=1$
(6.106)

On the other hand, for the security property, we rely on Theorem 46 that the
HLPUF $\mathcal{E}_{f}^{L}$ is $(\varepsilon,m)$-secure against any QPT
adaptive adversary (a $q$-query adaptive adversary for any $q$ polynomial in
the security parameter). For both $\mathcal{E}_{f_{1}}$ and
$\mathcal{E}_{f_{2}}$ of HPUF $\mathcal{E}_{f}$, we show that the power of an
adaptive adversary can be reduced to the power of a weak adversary, due to the
locking mechanism. Also since $\mathcal{E}_{f_{1}}$ has the universal
unforgeability against a weak adversary by definition, for any adaptive query
of the form $(x_{i},\sigma_{1})$ that an adaptive adversary issues to the
HLPUF, the following applies:

$\text{Pr}\left[\texttt{Ver}(\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}},\sigma_{1})=1\right]\leqslant\varepsilon(m)$
(6.107)

Where $\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}}$ is the correct
response constructed from CPUF according to HPUF construction. Thus the power
of the adaptive adversary reduces to the power of weak adversary and we have:

$Pr[1\leftarrow\mathcal{G}^{HLPUF}(\mathcal{A}_{ad},m)]\approx
Pr[1\leftarrow\mathcal{G}^{HLPUF}(\mathcal{A}_{weak},m)]$ (6.108)

Now given the fact that the adaptive adversary cannot boost from the weak-
learning phase to the HPUF, producing a forgery $\sigma_{2}$ for the HLPUF
that passes the verification
$\texttt{Ver}(\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}},\sigma_{2})$,
reduces to forging the HPUF $\mathcal{E}_{f_{2}}$. Again by assumption,
$\mathcal{E}_{f_{2}}$ has the universal unforgeability against weak adversary,
hence we have:

$Pr[1\leftarrow\mathcal{G}^{HLPUF}(\mathcal{A}_{ad},m)]=Pr[1\leftarrow\mathcal{G}^{HPUF}(\mathcal{A}_{weak},m)]\leqslant\varepsilon(m)$
(6.109)

This concludes the proof. ∎

Therefore, we have shown that Protocol 5, under certain reasonable assumptions
on the underlying classical PUF, is correct and achieves suitable security
against QPT adversaries.

####  6.4.6 Challenge re-usability

In any PUF-based protocol relying on the classical communication of challenges
and responses of the PUF, each challenge can only be used once as the
adversary can simply copy and record the challenges and responses and have a
perfect copy of the challenger’s database which later they can use to falsely
identify themselves. This is an important limitation of the classical PUFs
[367, 226]. Quantum communication can solve this issue due to the
unclonability of quantum states. In this section, we discuss how our hybrid
construction can allow for challenge states to be used several times during
the authentication, under the circumstances of previous successful
authentication rounds. This property will resolve an important practical issue
as the challenger can avoid storing a big database or renewing the database of
challenge responses frequently.

First, we need to clarify the conditions under which the challenge can be
reused. We assume the challenger’s database to only include $q$ number of
challenge-response pairs such that $q$ is polynomial in the security
parameter. We also need to recall that in our hybrid construction, the
challenges are still being sent as _classical_ bit-strings over the public
channel, hence the adversary, after polynomial rounds of communication, can
have the same challenge set as the server’s database. Due to this fact, we
should emphasize that the adversary does not get any physical access to the
internal classical PUF in the HLPUF construction during the authentication and
no query can be directly issued to the CPUF by the adversary. This condition
is satisfied using our locking mechanism. Thus, the adversary has access to
the following information: a pre-learnt polynomial-size local database of
challenge-responses of the CPUF, a set of classical challenges used during the
protocol, and the set of quantum states that encode either the first or second
half of the response, in the BB84 states.

It is a straightforward observation that the challenges for which the
verification test has failed should never be used again. A trivial attack, in
this case, would be that the adversary intercepts the communication and stores
the response state, and later when the same challenge has been queried again,
will re-send the stored correct response state to pass the verification. As a
result, all the challenges in the failed rounds should be discarded.

Nonetheless, we argue that in the events of successful authentication, the
challenges can be re-used. Here, by successful identification, we mean that
the received response state passes the verification on the client and server
sides and the prover identifies an honest party. Even though the events of
false identification of an adversary, is still possible (for example, if the
challenge is the same as one of the challenges that previously exists in the
adversary’s local database), the unforgeability of PUF and our security proof
for the hybrid construction, ensures that these events occur only with
negligible probability.

We are thus interested in the eavesdropping attacks by the adversary on the
first and second half of the response states that are of the form
$\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}}=\bigotimes_{j=1}^{m}\ket{\psi^{i,j}_{f_{1}(x_{i})}}\bra{\psi^{i,j}_{f_{1}(x_{i})}}$
and
$\ket{\psi_{f_{2}(x_{i})}}\bra{\psi_{f_{2}(x_{i})}}=\bigotimes_{j=1}^{m}\ket{\psi^{i,j}_{f_{2}(x_{i})}}\bra{\psi^{i,j}_{f_{2}(x_{i})}}$
Note that eavesdropping on the states which encode the first part of the
response will lead to breaking the locking mechanism while eavesdropping on
the second half will lead to an attack on the identification. Without loss of
generality, we only consider one of the cases where the adversary wants to
eavesdrop on the first (or second) half to break the protocol in the upcoming
rounds where the challenge is re-used. The arguments will hold equivalently
for both cases since the states and verification are symmetric.

Given all these considerations, the challenge re-usability problem will reduce
to the optimal probability of the eavesdropping attack on state
$\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}}$ which is in fact $m$
qubit states encoded in conjugate basis same as BB84 states. In the most
general case, the adversary can perform any arbitrary quantum operation on the
state
$\bigotimes_{j=1}^{m}|\psi^{i,j}_{f_{1}(x_{i})}\rangle\langle\psi^{i,j}_{f_{1}(x_{i})}|$
or separately on each qubit state $\ket{\psi^{i,j}_{f_{1}(x_{i})}}$, together
with a local ancillary system and sends a partial state of this larger state
to the verifier to pass the verification test, and keep the local state to
extract the encoded response bits. Let $\rho_{SEC}$ be the joint state of the
server, the eavesdropper and the client. Since the states used in the protocol
are from Mutually Unbiased Basis (MUB) states _i.e._ from either
$Z=\\{\ket{0},\ket{1}\\}$ or $X=\\{\ket{+},\ket{-}\\}$, in order to show the
optimal attack, we can rely on the entropy uncertainty relations that have
been used for the security proof of QKD. The measurements for verification are
also performed in the $\\{Z,X\\}$ bases accordingly. We use the entropy
uncertainty relations from [102] where the security criteria for QKD have been
given in terms of the conditional entropy for MUBs measurements. Using these
results we show that the entropy of Eve in guessing the correct classical bits
for the response is very high if the state sent to the verification algorithm
passes the verification with a high probability. Intuitively this is due to
the uncertainty that exists related to the commutation relation between $X$
and $Z$ operators in quantum mechanics. Hence we conclude that the success
probability of Eve in extracting information from the encoded halves of the
response is relatively low. Also, we show that this uncertainty increases
linearly with $m$ similar to the number of rounds for QKD. This argument
results in the following theorem. In proving this theorem, we have used the
entropic uncertainty relation introduced in Chapter 2, Section 2.1.5.

######  Theorem 48.

In Protocol 5, let $x$ be a challenge and $(y_{1},\dots,y_{2m})$ be the
response of a classical PUF used within the HPUF construction, with randomness
bias $p=(\frac{1}{2}+\delta_{r})^{2m}$ over the classical responses. If the
verification algorithm for a state $\tilde{\rho}$ passes with probability
$1-\varepsilon(m)$, then Eve’s conditional min-entropy $H_{min}^{Eve}$ in
terms of von Neumann entropy over the verifier/prover’s (server/client)
classical response, satisfies the following inequality:
$H_{min}^{Eve}=H_{min}(S^{m}|ER^{m})\geqslant m-\varepsilon(m)$ (6.110)

###### Proof.

We prove this theorem based on the first half of the state used in Protocol 5,
_i.e._ the state
$\ket{\psi_{f_{1}(x_{i})}}\bra{\psi_{f_{1}(x_{i})}}=\bigotimes_{j=1}^{m}|\psi^{i,j}_{f_{1}(x_{i})}\rangle\langle\psi^{i,j}_{f_{1}(x_{i})}|$
that is being sent by the verifier/server denoted by (S) and received and
measured by the prover/client denoted by (C). Nevertheless, we note that the
same proof applies for the second state due to the symmetry of the states and
the protocol.

Let $R^{m}=(R_{1},\dots,R_{m})$ be the randomness bitstring showing the choice
of the basis encoding of the response, $S^{m}=(S_{1},\dots,S_{m})$ be the
server’s bit encoded in the $R^{m}$ bases. Note that both $R^{m}$ and $S^{m}$
are produced according to the bitstring $(y_{1},\dots,y_{2m})$ which is the
first half of the response of CPUF to a given challenge $x$. Also, let
$C^{m}=(C_{1},\dots,C_{m})$ be the client’s correct bit string. We denote the
arbitrary joint state of three systems by $\rho_{S^{m}EC^{m}}$ where $E$
denotes any arbitrary quantum system held by the eavesdropper. Now, let the
the Client’s measurement outcomes, after the verification be
$\tilde{Y}^{m}=(\tilde{Y_{1}},\dots,\tilde{Y_{m}})$ which shows the estimated
bits by the Client. Now we can write the tripartite uncertainty principle, in
terms of the von Neumann entropy, for MUB measurements and MUB states as
follows:

$H(X_{1}X_{2}Z_{3}X_{4}\dots X_{m-1}Z_{m}|E)+H(Z_{1}Z_{2}X_{3}Z_{4}\dots
Z_{m-1}X_{m}|C)\geqslant\log_{2}(\frac{1}{c})^{m}$ (6.111)

where $c=\max_{x,z}c_{xz}$ and
$c_{xz}=\parallel\sqrt{M^{x}}\sqrt{N^{z}}\parallel^{2}$ for an arbitrary POVM
sets $M=\\{M^{x}\\}_{x}$ and $N=\\{N^{z}\\}_{z}$. We note that if the CPUF
creates perfect random bitstring for $R^{m}$ then states are perfect MUB
states and $c=\frac{1}{2}$. Nonetheless we consider a weaker CPUF with a
biased distribution of $p=(\frac{1}{2}+\delta_{r})^{2m}$ in creating $0$s and
$1$s in the response. Hence, we can translate this imperfectness into a
disturbance in the measurement bases. Let $M^{0}=\ket{0}\bra{0}$ and
$M^{1}=\ket{1}\bra{1}$ be the usual measurement in the computational basis but
let the $N$ measurements be a slightly shifted version of the measurements in
the $X$ basis. Consider the following states:

$\begin{split}&\ket{\psi_{N}}=\sqrt{\frac{1}{2}+\delta_{r}}\ket{0}+\sqrt{\frac{1}{2}-\delta_{r}}\ket{1}\\\
&\ket{\psi^{\perp}_{N}}=\sqrt{\frac{1}{2}-\delta_{r}}\ket{0}-\sqrt{\frac{1}{2}+\delta_{r}}\ket{1}\end{split}$
(6.112)

We define the new $N$ projective operators according to the following states
as $N^{0}=\ket{\psi_{N}}\bra{\psi_{N}}$ and
$N^{1}=\ket{\psi^{\perp}_{N}}\bra{\psi^{\perp}_{N}}$. Now we calculate the
operator norm for all the pairs of measurements and we have:

$\begin{split}&\parallel\sqrt{M^{0}}\sqrt{N^{0}}\parallel^{2}=\frac{1}{2}+\delta_{r},\quad\parallel\sqrt{M^{0}}\sqrt{N^{1}}\parallel^{2}=\frac{1}{2}-\delta_{r}\\\
&\parallel\sqrt{M^{1}}\sqrt{N^{0}}\parallel^{2}=\frac{1}{2}-\delta_{r},\quad\parallel\sqrt{M^{1}}\sqrt{N^{1}}\parallel^{2}=\frac{1}{2}+\delta_{r}\end{split}$
(6.113)

Thus we conclude that $c=\frac{1}{2}+\delta_{r}$ and the Equation Eq. (6.111)
can be re-written as follows:

$H(X_{1}X_{2}Z_{3}X_{4}\dots X_{m-1}Z_{m}|E)+H(Z_{1}Z_{2}X_{3}Z_{4}\dots
Z_{m-1}X_{m}|C)\geqslant m-m\log_{2}(1+2\delta_{r})$ (6.114)

Now, we use the data processing inequality [102], we have got the following
security criteria that show Eve’s uncertainty (in terms of the von Neumann
entropy) of the actual response bits $S^{m}$:

$H(S^{m}|ER^{m})+H(S^{m}|\tilde{Y}^{m})\geqslant m-m\log_{2}(1+2\delta_{r})$
(6.115)

We can get the same inequality in terms of smooth min and max entropy [102,
394] (see Section 2.1.5), which is more appropriate for ensuring the security
in the finite size, for min and max entropy we equivalently have:

$H^{\varepsilon}_{min}(S^{m}|ER^{m})\geqslant
m-H^{\varepsilon}_{max}(S^{m}|\tilde{Y}^{m})-m\log_{2}(1+2\delta_{r})$ (6.116)

To calculate the above bound we need to find the bound on the second term of
the right-hand side, _i.e._ $H^{\varepsilon}_{max}(S^{m}|\tilde{Y}^{m})$. Here
we use another result from [394] where it states that for any bitstring $X$ of
$n$ bit and the respective measurement outcome $X^{\prime}$, which at most a
fraction $\zeta$ of them disagree according to the performed statistical test,
then the smooth max entropy is bounded as follows:

$H^{\varepsilon}_{max}(X|X^{\prime})\leqslant nh(\zeta)$ (6.117)

where $h(.)$ denotes the classical binary Shannon entropy. Now we can use this
result and our assumption of successful verification together. Given the
assumption that the verification is passed with a probability
$1-\varepsilon(m)$, and the verification algorithm consists of measuring the
states in the $Z$ and $X$ bases, we can conclude that the final bits differ in
at most a fraction $\zeta=\varepsilon(m)$ where $\varepsilon(m)$ is a
negligible function. As a result, we have:

$H^{\varepsilon}_{max}(S^{m}|\tilde{Y}^{m})\leqslant mh(\zeta)\approx
m\varepsilon(m)$ (6.118)

Putting Equations Eq. (6.116) and Eq. (6.118) together, we have:

$H^{\varepsilon}_{min}(S^{m}|ER^{m})\geqslant
m-m\varepsilon(m)-m\log_{2}(1+2\delta_{r})$ (6.119)

On the right-hand side of the above inequality, the second term is still a
negligible function and the third term depends on the CPUF bias probability
distribution. We assume the CPUF satisfies $p$-randomness, as defined in the
Definition 47, thus the $\delta_{r}$ is a small value and hence the term
$(1+2\delta_{r})$ is negligibly close to $1$, which means that the third term,
is negligibly close to $0$ in the security parameter which is $m$. Finally, we
conclude that:

$H^{Eve}_{min}=H^{\varepsilon}_{min}(S^{m}|ER^{m})\geqslant
m-\varepsilon^{\prime}(m)$ (6.120)

where $\varepsilon^{\prime}(m)$ is a negligible function and the proof is
complete. ∎

Let us see how the abouve information-theoretic bound can be used to prove the
challenge-reusability of the Protocol 5. First, define the re-usability in
relation with the unforgeability game and then using Theorem 48, we prove the
challenge re-usability of our protocol.

######  Definition 50 (Challenge ($k$-)re-usability in the universal
unforgeability game).

Let $\mathcal{G}_{re}(\lambda,\mathcal{A},x_{k+1})$ be a special instance of
the universal unforgeability game, where a challenge $x$, picked uniformly at
random by the challenger, has been previously used $k$ times. We are
interested in the events where the same challenge is used in the $(k+1)$-th
round, which we denote by $x_{k+1}$. We say the challenge $x$ is ($k$-)re-
usable if the success probability of any QPT adversary in winning
$\mathcal{G}_{re}(\lambda,\mathcal{A},x_{k+1})$, i.e, in forging message
$x_{k+1}$, is negligible in the security parameter:
$p_{forge}(\mathcal{A},x_{k+1})=Pr[1\leftarrow\mathcal{G}_{re}(\lambda,\mathcal{A},x_{k+1})]\leqslant\varepsilon(\lambda)$
(6.121)

######  Theorem 49 (Challenge re-usability of HLPUF-based Authentication
Protocol 5).

A challenge $x$ can be reused $k$ times during the Protocol 5 as long as the
received respective response $\sigma$ for each round passes the (client’s or
server’s) verification with overwhelming probability. In other words, given
the successful verification, the success probability of any quantum adversary
in passing the $(k+1)$-th round with the same challenge $x$ is bounded as
follows: $p_{forge}(\mathcal{A},x_{k+1})\leqslant
k2^{-m}\approx\varepsilon(m).$ (6.122)

###### Proof.

To prove this theorem, we use Theorem 48 directly. First, we assume that $x$
has been used one time before in a previous round. Given the assumption that
the verification is passed with probability $1-\varepsilon(m)$, and this
theorem, we conclude that the uncertainty of the adversary in guessing the
encoded response of the HLPUF is larger than $m-\varepsilon(m)$. In our case,
the joint quantum state between the server and the adversary is a classical-
quantum state (server has the classical description of $f(x)$, and the
adversary has the quantum state $\ket{\psi_{f(x)}}$). For such states, Eve’s
uncertainty, $H_{min}^{Eve}$ is same as $-\log p_{guess}^{Eve}$, where
$p_{guess}^{Eve}$ is Eve’s guessing probability of the classical information
encoded in the quantum state [257]. Therefore,

$\begin{split}p_{guess}^{Eve}&=2^{-H_{min}^{Eve}}\\\ &\leqslant
2^{-m+\varepsilon(m)}\end{split}$ (6.123)

This probability is negligible in the security parameter, which means that
after performing any arbitrary quantum operations, the adversary’s local state
includes at most, a negligible amount of information on the response of $x$,
each round that the state $x$ is reused. Now, we can use the union bound (See
Preliminaries, LABEL:sec:) to show that this success probability only linearly
scales with $k$:

$p_{guess}^{Eve,k}=Pr(\bigcup^{k}_{i=1}E_{guess}^{i})\leqslant\sum^{k}_{i=1}p(E_{guess}^{i})\approx
k2^{-m}$ (6.124)

where $E_{guess}^{i}$ are the events where Eve correctly guesses the response
and where $p(E_{guess}^{i})=(p_{guess}^{Eve})^{i}$ is the success probability
of Eve in guessing in the $i$-th round. Finally, let the success probability
of an adversary in the universal unforgeability game for the HLPUF be upper-
bounded by $\varepsilon_{1}(m)$ which is a negligible function in the security
parameter since we assume that the HLPUF satisfies the universal
unforgeability. This is the same as the success probability of the adversary
in passing the verification for a new challenge, chosen at random from the
database. Now in the $(k+1)$-th round, where the same $x$ is reused, the
success probability is at most boosted by the guessing probability over the
previous $k$-th rounds, hence we will have:

$p_{forge}(\mathcal{A},x_{k+1})\leqslant\varepsilon_{1}(m)+k2^{-m}=\varepsilon(m)$
(6.125)

As long as $k$ is polynomial in the security parameter, the second term is
also a negligible function and since the sum of two negligible probabilities
will be also negligible. This concludes the proof. ∎

###  6.5 Discussion and conclusions

We have proposed three different identification protocols based on quantum
PUFs and Hybrid classical-quantum PUFs which provide exponential (or
relatively exponential) security against any QPT adversary by exploiting
physical unclonability (both in the quantum and classical sense) as a hardware
assumption instead of the usual cryptographic assumptions. The first two
protocols use full quantum PUFs and the last one combines a classical PUF with
quantum encoding to give rise to our hybrid construction. Our primary
classification in the first two protocols has come about from the practical
scenarios in a network, _i.e._ parties with varying capabilities should be
able to run a secure identification protocol. The first protocol, hrv-id, is
proposed to be suited more in the mobile-like device settings _i.e._ provers
having low resources would want their device to be correctly identified by a
high resource verifier. This protocol can be used as a subroutine for many
other applications, specifically in a quantum internet or a quantum network
with _star-like_ architecture [121, 332, 271], where a server (central node)
can use this protocol to identify each of the clients. Also, since the
identification protocol requires multi-round communication between the prover
and the verifier, we have proposed efficient quantum equality-testing
verification to reduce the communication overhead requirement.

Our second protocol, lrv-id, is suited to the quantum verification setting
_i.e._ a low-resource and classical-like verifier would want to verify the
identity of a high resource quantum device, like a quantum cloud server. The
advantage of this protocol is that a purely classical verification algorithm
is sufficient to verify the prover’s device with provable security. lrv-id is
based on the idea of trapification, where the verifier inserts random trap
states in between the communication rounds which facilitates a secure
delegation of the quantum testing to the prover. This allows the verifier to
simply run a classical algorithm on the quantum test outcomes to perform
successful identification. We have also shown an extension of the lrv-id
protocol that generalises it to an arbitrary distribution of traps instead of
randomly inserting them in half of the positions as proposed in the current
version of the protocol. With this generalisation on hiding the trap
distribution, one hopes for further enhancement in security against a QPT
adversary. We draw non-trivial conclusions from this generalisation, including
the worsening of security to polynomial in the number of communication rounds
(instead of exponential as our current protocol) when the number of trap
positions is chosen uniformly over the total positions. We also remark that
some distributions provide a polynomial enhancement over the current
exponential security bound, thus justifying the need for hiding the number of
trap positions. We also believe that this generalisation provides a potential
use case of a similar protocol for a certain degree of verification and
certification of quantum devices using embedded quantum PUFs. We see this
direction as an engaging future subject of study since qPUFs provide natural
and physical randomness, which combined with more enhanced trapification
techniques, can potentially lead to a new class quantum
verification/certification protocols.

An important future direction regarding the practicality of the presented
protocols is to study the effect of noise and robustness of the protocols
under honest noise. So far, the protocols have been studied in the noiseless
setting, and the requirements of verification are strictly rigid (for
instance, all rounds of verification have to be successfully passed), however,
both protocols can be made more robust by relaxing some of these requirements
and allowing for a tolerance parameter while remaining secure. We leave the
study of the robustness and security properties of the protocol in the noisy
setting for future work.

Then, we have used our result regarding efficient universal unforgeability, to
reduce the Haar-random sampling of our proposed protocols to pseudorandom
quantum states that are efficient to generate, as a result, introducing a more
implementation-friendly version of our qPUF-based protocols. Quantum
pseudorandomness is yet a very young field of research, and we believe the
advancement in this field can assist the qPUF constructions and the protocols
based on them to become more and more practical.

Finally, in our latest proposal, we have exploited one of the main sources of
security in the quantum information world, namely the concept of conjugate
coding [91], to propose a new construction that uses an internal (and almost
weak) classical PUF and enhances its unpredictability to a high degree using
this quantum encoding. Nonetheless, this enhancement is only against non-
adaptive adversaries. For security against our usual QPT adversary that is in
general adaptive, we use an additional technique, namely the locking mechanism
that provides us with our HLPUF construction used in our proposed
authentication protocol. An important property of the new construction is the
combination of classical challenges and quantum responses, which harnesses the
power of quantum information over an untrusted quantum channel while the
verifier does not need to store the responses quantumly, which fully removes
the quantum-memory requirement. As a result, the implementation of hybrid PUF
is practical nowadays with quantum communication technology. Another advantage
of the HLPUF-based protocol is that each challenge-response pair used for a
successful authentication round can be used several times for authentication
due to the unclonability and other fundamental quantum mechanical properties
of the response quantum states. Therefore, with our solution, a server can
continue the client authentication protocol for a longer period without
exhausting its CRP database. This result overcomes the fundamental drawbacks
of the existing classical PUF-based authentication protocols and offers a
novel use case, not only for our construction but also for quantum
communication in general.

However, there are several thought-provoking questions, yet to be explored. In
bounding the success probability of a QPT adversary against HPUF in Theorem
45, we have established a connection between unforgeability and the
learnability of a classical function (in our case CPUF’s evaluation function)
from a quantumly encoded random set of data, using quantum informatics
approaches. Despite the current proof being specific to our construction, we
believe that most of the techniques we have used are fairly general and can be
used to formally establish a link between cryptographic properties and
learning problems, using quantum information theory. Furthermore, if the same
result can be generalised to bound the success probability of a QPT adversary
respective to a classical PPT adversary, for learning a classical function
from a general quantum encoding, then one can relate the problem to the open
question of the advantage of _supervised learning_ with quantum models [387,
370]. The use of quantum information theory in learning theory has recently
led to influential results regarding the comparison between classical and
quantum machine learning [217]. Therefore, we conjecture that further
expanding this connection to cryptography and quantum-information-based
cryptography can provide new insights into these very challenging and exciting
problems.

We finally discuss the experimental requirement of our HLPUF-based proposal.
We note that by selecting the quantum encoding to be BB84 states, the protocol
can be implemented with resources similar to quantum key distribution. QKD
technology is one of the most mature quantum technologies. The long-distance
QKD networks are already implemented and used in many different countries like
the USA, UK, China, EU, Japan, [369, 379, 341, 402, 129] etc. Many
commercially available QKD infrastructures provide almost $300$kb/s secret key
rate over optical fibre links of length $120$km [179]. Moreover, the
availability of the mature QKD on-chip technology [368, 386, 81] makes all the
proposed constructions in this work implementable inside the IoT devices.
Given all these available technologies, our proposal can solve almost all of
the shortcomings of the device authentication problem. To further study the
feasibility and practicality of hybrid PUF constructions, an important future
direction would be toward the experimental implementation of our proposal and
the HLPUF-based authentication protocol. Furthermore, we believe that due to
the matching of required resources and the strong security guarantee of our
protocol, it can be easily incorporated with the QKD itself as a promising
solution for providing the authenticated channel that is required for QKD
[366]. Hence an immediate and important future research direction would be the
usage of the protocol for the task of message authentication and the
composition of this protocol with QKD. Furthermore, since QKD has been proven
composable secure [87, 352, 391, 265], an important future direction would be
to study the security of the proposed protocol within the existing composable
frameworks such as universal composability framework [100] or abstract
cryptography framework [284, 285].

##  Chapter 7 Variational Quantum Cloning: A New Cryptanalysis Toolkit

“Everything in this world is magic, except to the magician.”

– Robert Ford, Westworld (S1.Ep2: Chestnut)

###  7.1 Introduction

We have set out on a long journey to understand new aspects of
‘Unclonability’, from a foundational point of view in discovering its
relationship to randomness and learnability, all the way to introducing new
applications in quantum cryptography. The three past chapters navigate around
the concept of physical unclonability. In this chapter, we come back to the
more familiar notion of quantum unclonability, that is, the no-cloning theorem
and unclonability of quantum states.

In Chapter 2 (Section 2.3), we have covered the no-cloning theorem and the
concept of approximate cloning. We have seen that it is both possible to
create _imperfect_ copies of unknown quantum states (approximate cloning) or
to have a quantum operation that only _sometimes_ gives you two perfectly
similar copies of general quantum states (probabilistic cloning). Among these
two categories, approximate cloning is particularly interesting for us since
it somehow matches the idea that we have pursued in this thesis in
understanding the fundamental relation between unclonability, learnability and
the level of _unknownness_. Intuitively we focus on the amount of information
that exists prior to performing the cloning mechanism, about the entity that
one aims to clone. As we have seen in Section 3.2 and Section 3.3.1. This
specific prior information leads to different classes of cloners with the
ability to clone the particular family of states corresponding to that
information, where the quality (or more technically, fidelity) of these clones
is higher than the universal cloner. To roughly summarise this argument, the
more you know (or learn) about the states you want to copy, the better you can
copy them. Having this inherent relation in mind, now we move to the field of
quantum cryptography, where no-cloning is at the heart of the security of many
quantum protocols (QKD, coin-flipping, verifiable blind quantum computing,
etc.). Here, the following question arises:

_‘In what ways the ability to clone a specific family of states with partial
prior information can affect the security of quantum protocols?’_

Despite the fact that the study of approximate cloning was born many years ago
with the remarkable discovery of _Buzeh and Hillery_ [40], and despite the
existence of a rich literature on the subject, there are still very limited
classes of states that are known how to be cloned approximately with optimal
fidelity [373, 182]. More importantly, even for some of these known classes of
cloning, the unitary circuits (or circuit decompositions) of these cloners are
not known. Having these circuits and unitaries explicitly is not only
important for practical applications of quantum cloning machines, but also a
very relevant problem to quantum compilation. Notably, in touching on quantum
cryptanalysis, this ‘prior information’ becomes much more general and can
include cases where our knowledge about the cloning machines (for the specific
problem of interest) is narrow. Moreover, if cloning based on a specific
family of the state is to be used as an attack model, the complexity of the
circuit and technological feasibility of performing those cloners will be
considerable factors, which once again calls for being able to have an
explicit form of the cloning machines.

Quantum cloning has been previously considered as an attack model for some
quantum protocols such as QKD. It turns out that in some cases, these types of
attacks are in fact, optimal [373]. In cases where they are not, cloning
provides a means to determine lower bounds on the strategies of an adversary
[420]. However, _implementing_ such cloning-based attacks might be non-trivial
in practice due to the difficulties mentioned above. Also, the effect of
decoherence and errors in NISQ devices makes the production of high-quality
clones out of reach for the adversary, which limits the power of practical
quantum cryptanalysis in the NISQ era. On the other hand, there has been much
interest in implementing quantum cloning and cryptographic attacks on
protocols via specific and tailored experiments (for example [268, 176, 137,
80, 42]), but these may not be easily reconfigurable or generalizable to other
scenarios. In summary, finding and constructing quantum cloning circuits for
preparing high fidelity clones on NISQ hardware is challenging.

All the arguments given above, motivate us to seek a new approach to
efficiently produce optimal cloning machines and their circuits for specific
classes of states. We are in particular interested in the ones that are
implementable efficiently on NISQ devices. We also note that existing
approaches in the literature are by no means optimal if one wants to
generalise this question in order to target applications, especially targeting
applications in cryptanalysis given the everyday-expanding variety of quantum
protocols. The known analytical approaches proceed as follows: Firstly, the
most general unitary for the cloning machine has been considered. Secondly, by
imposing the symmetries and conditions on the specified family of states, the
output fidelity of the machine has been optimised, irrespective of the
characterisation of the unitary. Thirdly, one should try to find a unitary
matrix that achieves that maximum fidelity, which is often a non-trivial and
challenging task. Some inspiring alternative approaches have also been given
for the case of equatorial states111We recall that we have defined these
states in Chapter 2, Section 2.3.1 [123], which exploit the symmetries in a
much more intriguing way than the previous formalism for cloning. However,
these approaches do not seem generalisable to other classes of cloning.

The approach we propose here takes a very different path. We start with the
idea of _letting a quantum machine learn how to clone_ a specific given family
of quantum states. We give a novel algorithm: ‘Variational Quantum Cloning’
($\operatorname{\textsf{VarQlone}}$) which uses quantum machine learning (QML)
[405, 96, 254, 382, 383] techniques to _learn_ how to clone quantum states in
an end-to-end manner. $\operatorname{\textsf{VarQlone}}$ is made possible by
recent advances and techniques in the field of _variational_ quantum
algorithms (VQAs) [304, 70, 170, 405, 99]. VQAs are intentionally tailored to
be useful on NISQ devices, which are limited in scale and noisy to implement
‘coherent’ algorithms with speedups, such as factoring large prime numbers
[372]. However, such devices are capable of performing tasks which cannot be
simulated by any classical device in reasonable time [1, 432, 125]. This
motivates the search for dedicated applications for a topic of likely
practical relevance.

Variational quantum algorithms have been proposed and used for various
applications, including quantum chemistry [338] and combinatorial optimization
[174]. The core quantum component is typically a parameterised quantum circuit
(PQC) [151] (as mentioned in Section 2.6.4). When VQAs are applied to machine-
learning problems, they have come to be seen as quantum neural networks (QNNs)
[82, 237]. This is because they can achieve many of the same tasks as
classical neural networks, [294, 184] and can outperform them in certain cases
[412, 128, 105]. Furthermore, machine learning techniques, both quantum [309,
249, 229, 225, 88, 419, 211] and classical [250, 297, 327, 321, 413] have
proven to be useful in _discovering_ and providing insights into quantum
algorithms and subroutines. This line of study even extends to the foundations
of quantum mechanics. We refer the reader to this paper [6] about variational
consistent histories.

$\operatorname{\textsf{VarQlone}}$ is different from other variational
algorithms in that it can be viewed as the first step into a new area of
applications, _variational quantum cryptanalysis_. Specifically, by using QML
techniques to learn to clone quantum states,
$\operatorname{\textsf{VarQlone}}$ can discover unique ways to attack quantum
protocols, in particular those whose underlying security can be reduced to
quantum cloning. Furthermore, in developing such techniques more generally, we
can determine the relationship between classical machine learning and deep
learning, with classical cryptography [27, 299, 339, 20].

We believe this new approach for approximate cloning is reasonably general and
can be used to deepen and widen our understanding of approximate cloning.
However, as a concrete case study and proof of concept of our new approach to
cryptanalysis, we map two well-known families of approximate cloning machines,
_i.e._ _phase-covariant cloning_ [47] and _fixed-overlap state-dependent
cloning_ [50, 85] to two well-known families of quantum protocols, namely
_quantum key distribution_ and _quantum coin flipping_ respectively [308, 33].
The latter is probably more exciting since, to the best of our knowledge, this
is the first time such a connection has been revealed in the case of state-
dependent cloning. One can also see this work as an attempt to uncover the
core ingredient of security of different quantum protocols from the
perspective of the family of states they rely on.

As part of our research in developing this algorithm, we define suitable cost
functions which depend on the symmetries used in the cloning problem, and we
use them to prove theoretical guarantees for them (including notions of
faithfulness [249]). As we have discussed in Section 2.6.4 since VQAs are
heuristic techniques, usually being able to provide such theoretical
guarantees is rare in the field (also one of the reasons we have started the
chapter with ’everything in this world is magic, except to the magician’!) and
this work is one of the few exceptions.

Finally, to underline the practical potential of our approach we implemented
it on the Rigetti Aspen quantum computer and show how
$\operatorname{\textsf{VarQlone}}$ can learn to clone states with a higher
fidelity on this device than previously known ‘analytic’ quantum circuits,
highlighting the flexibility of our approach. Furthermore, the nature of
$\operatorname{\textsf{VarQlone}}$ allows us to improve cloning fidelities
generically, on quantum computers available through the cloud [263], without
requiring significant tweaking and custom-built experimental hardware.

####  7.1.1 Structure of the chapter

First, in Section 7.2 we introduce how different classes of cloning can be
used as a cryptanalysis toolkit to attack protocols that benefit from using
certain classes of states. For our case study we introduce cloning attacks on
the BB84 protocol in 7.2.1 in relation to phase covariant cloning, and two
different quantum coin-flipping protocols in Section 7.2.2 in connection to
state-dependent cloning. We present our cloning-based attacks based on an
optimal cloner which we then replace with the cloning machines learned through
our variational algorithm. In Section 7.3 we introduce some theoretical
aspects and specifications of $\operatorname{\textsf{VarQlone}}$ such as cost
functions (Section 7.3.1), gradient of the proposed cost functions (Section
7.3.2) and more importantly, theoretical guarantees for our algorithm based on
the proposed cost function (Section 7.3.3). Finally, in Section 7.4 we present
both simulation and experimental results based on
$\operatorname{\textsf{VarQlone}}$, including the circuits found for our
specified problems and the probability analysis of the attacks based on them.

###  7.2 Quantum cryptanalysis based on different classes of cloning

In the first part of this chapter, and before introducing our machine learning
algorithm, we want to establish the theoretical ground for our cryptanalysis
based on different types of cloning with _partial prior information_ about the
states. Here, we only look at cryptanalysis using approximate quantum cloning,
and we do not study the use-cases and relevance of probabilistic cloners.
Using cloning as an attack strategy has been considered previously only in
limited settings, for instance, regarding the QKD protocol, where it has been
shown that there exists an optimal cloning-based attack on the BB84 protocol
[373]. Nevertheless, here we take a more methodologic approach. Keeping in
mind that approximate cloning is categorised into different classes
characterised by _specific_ families of states, we look for quantum protocols
that use the same state families for which we have a cloning machine.

Among different types of cloning, universal cloning does not seem very
thrilling for this purpose, as it is state-agnostic. Moreover, as we have
seen, restricting the class of states that one wants to clone,_i.e._ having
prior information about the states leads to higher fidelity clones. In
cryptanalysis, we ever optimise over all the adversarial strategies, which in
this case includes using the best cloning strategy given the protocol’s
characteristics.

We choose two main families of approximate cloning for our purpose, namely
_phase-covariant cloning_ (see Section 2.3.1) and _fixed-overlap state-
dependent cloning_ (see Section 2.3.1). For the former, our target example
protocol is QKD, where we will explain the optimal cloning-based attack. This
analysis serves as an important tool as we use the calculations later for our
variational cloning attacks. The latter class of approximate cloning, on the
other hand, has never been used before for the purpose of cryptanalysis to the
best of our knowledge. We notice that the specific family of states used in
this type of cloning matches the class of states used in quantum coin-
flipping. Hence, we introduce, for the first time, cloning-based attacks on
two different quantum coin-flipping protocols.

Finally, we emphasise that the purpose of this study is mostly the
illustrations of applications of variational cloning based techniques, for
practical cryptanalysis.222To clarify, let us take QKD as an example. This
protocol has been proven information-theoretic secure, so we do not intend to
break it using variational attacks as it seems pointless. But rather QKD will
serve as an example of phase-covariant cloning attacks in general. Moreover,
as we will see it is not the case for all the coin-flipping protocols we study
in this chapter. Nonetheless, the attacks we present in this section either
saturate the optimal bounds, where there exists a rigorous security proof or
even lead to a complete novel security attack, in the absence of such strong
proof.

####  7.2.1 Cryptanalysis based on phase-covariant cloning

Let us begin with phase-covariant cloning and the quantum key distribution
protocols by focusing on the BB84 protocol [34, 35]. In this protocol, one
honest party, Alice, sends single-qubit states in two orthogonal bases (for
instance, the eigenstates of the Pauli $\mathsf{X}$ and Pauli $\mathsf{Y}$
matrices, $\ket{\pm}$ and $\ket{\pm i}$) to a second honest party, Bob, via a
quantum channel that is susceptible to an eavesdropping adversary, Eve. Eve’s
goal is to extract the secret information exchanged between Alice and Bob,
encoded in the states. It turns out that the optimal ‘individual’ (or
incoherent) Eve’s attack [373] on this protocol is given by cloning so-called
_phase-covariant_ [47] states of the form:

$\ket{\psi_{xy}(\eta)}=\frac{1}{\sqrt{2}}\left(\ket{0}+e^{i\eta}\ket{1}\right)$
(7.1)

For these states, some _analytic_ circuits are given in [40, 180, 182]. For
this family of states, Eve can construct a cloning machine with fidelity
$F_{\mathsf{L},\text{opt}}^{\text{PC},\mathrm{E}}\approx 0.85$.

There are different families of attacks considered on such protocols. The
simplest attack by Eve is a so-called ‘incoherent’ or individual attack, where
Eve attacks each quantum state individually before the reconciliation phase of
the protocol. The security of this protocol relies on the information-
theoretic bounds on the information shared between Alice and Bob as compared
to the information that Eve was able to extract from the key. In the
incoherent attacks, the security condition states that a secret key can only
be extracted as long as the amount of Eve’s information is less than what Bob
has received. Thus, one key parameter in the protocol is what is called the
_critical error rate_ , $D_{\text{crit}}$, which defines the threshold above
which Alice and Bob abort the protocol and conclude that the channel is
insecure.

For incoherent attacks, the optimal error rate for the ideal incoherent attack
is
$D_{\text{crit}}^{\text{incoh}}=1-F_{\mathsf{L},\text{opt}}^{\text{PC},\mathrm{E}}\approx
14.6\%$ [373].

However, as discussed in [373], this is not the best way of analysing the
cloning-based attacks against this protocol, since it does not allow for a
comparison between a cloning machine that uses the ancilla, and one that does
not. The importance of this comparison is that the cloning machine with
ancillary inputs may provide Eve with extra information about both parties. A
more appropriate way of calculating the key rate which generalises the
strategies is via the Holevo quantity, denoted as $\chi$ which is defined as
follows from von Neumann entropy:

$\chi(Q:E):=S(\rho_{E})-\frac{1}{2}S(\rho^{0}_{E})-\frac{1}{2}S(\rho^{1}_{E})$
(7.2)

In Eq. (7.2), $\rho_{E}$ denotes the mixed state of Eve over all of the
combinations of Alice’s choice of input, and $\rho^{0}_{E}$ and $\rho^{1}_{E}$
denote the states of Eve for the random variables that encode $0$ and $1$ in
the protocol respectively.

Combining mutual information with Holevo quantity gives a concrete and simple
method for calculating the key rate in QKD protocols. The key rate for QKD can
be defined as follows:

$R=I(A:B)-\min\\{\chi(A:E_{Q}),\chi(B:E_{Q})\\}$ (7.3)

where $I(A:B)$ denotes the mutual information between Alice and Bob and the
index $Q$ denotes that Eve may employ general quantum strategies. Intuitively,
Eq. (7.3) states that no key can be extracted at $R=0$ which is when Alice and
Bob’s mutual information is the minimum value between Alice and Eve and Bob
and Eve. At any point after that, Eve has increased the correlation to the
key, to the point that the key is compromised.

For calculating the quantity $D_{\text{crit}}$, one needs to calculate the
Holevo quantity for Eve, set $R=0$, compute the mutual information,
$I(A:B)=1-H(D_{\text{crit}})$ and finally solve the resulting equation for
$D_{\text{crit}}$. For the ideal incoherent attack, this value is again proven
to be $D_{\text{crit}}^{\text{incoh}}\approx 14.6\%$. We go back to this
calculation in Section 7.4.1 where we will show that the cloning
transformations we learn using our variational cloning algorithm give an
approximately close critical error rate while being experimentally superior to
the ideal proposed circuits.

####  7.2.2 Cryptanalysis based on state-dependent cloning

Now, let us examine the class of states used in _state-dependent_ cloning,
which are states with fixed and known overlap. Non-orthogonal quantum states
are among the elements that are often present in quantum cryptography since
they can encode information that is not easily decodable for an adversary who
does not know the basis. The most famous example is, of course, conjugate
coding [406]. But despite the generality of the state-dependent cloning
framework, it is surprising that this type of cloning machine has not been
studied as a concrete attack model, and to the best of our knowledge, this is
the first time we use state-dependent cloning as a cryptanalysis tool. A
concrete example of the protocols that exploit such states is the family of
_quantum coin-flipping_ protocols. Coin-flipping is a cryptographic task where
two mutually distrustful parties, who are usually spatially separated and want
to agree on a common random bit (see Section 2.5.7 for more details about
coin-flipping). Classical and quantum coin-flipping have a vast literature,
but here for our case study, we focus on two specific _strong quantum coin-
flipping_ protocols. The two protocols we consider are that of Mayers et al.
[307], and that of Aharonov et al. [33]. First, let us introduce the common
aspect of these protocols as well as the states used in the protocols.

##### Quantum coin flipping states

Let us first introduce quantum coin flipping in more detail. The task of the
quantum coin flipping is similar to the classical one, only the parties can
have quantum capabilities. We say the coin is ‘biased’ when one outcome is
more likely to occur than the other, for example, with the following
probabilities:

$\begin{split}\Pr(y=0)=1/2+\varepsilon\\\ \Pr(y=1)=1/2-\varepsilon\end{split}$
(7.4)

where $y$ is the output bit. The above coin is an $\varepsilon$-biased coin
with a bias towards the outcome $0$. In contrast, a fair coin would correspond
to $\varepsilon=0$.

We recall from Section 2.5.7 that it is impossible in an information-theoretic
manner, to achieve a perfectly secure (with zero bias $\varepsilon=0$) strong
coin-flipping protocol in both the classical and quantum setting [83, 264,
307]. Several protocols have been proposed for $\varepsilon$-biased strong
coin flipping [307, 33, 35, 36], the states used by these protocols share a
common structure. Here we introduce a more general form of these states, which
will be useful for our purpose. The following set of states (illustrated in
Fig. 7.1) have been used in the protocols that we will investigate:

$\ket{\phi_{x,a}}=\begin{cases}\ket{\phi_{x,0}}=\cos\phi\ket{0}+(-1)^{x}\sin\phi\ket{1}\\\
\ket{\phi_{x,1}}=\sin\phi\ket{0}+(-1)^{x\oplus 1}\cos\phi\ket{1}\end{cases}$
(7.5)

where $x\in\\{0,1\\}$, and the angle $\phi$ determines the overlap between the
pairs of states.

Figure 7.1: States used for quantum coin-flipping. The first bit represents
the _basis_ , while the other represents one of the two orthogonal states.

Additionally, these protocols share the following shared structure: One of the
parties, or sometimes both, will encode some random classical bits into the
above states and then exchange some classical/quantum information as part of
the protocol. The attack of the malicious party who is trying to bias the coin
is then, reduced to the ability to learn the encoded classical bit, from the
state (or in some cases, to prepare states deviating from the perfect ones).
To see why this is the case, we need to look at the impossibility of the
classical coin-flipping task [83]. The intuitive reason behind this
impossibility lies in the _order_ or asymmetry between the two parties. In
other words, since the outcome has to be determined after a certain number of
communication rounds in the protocol consisting of sending some messages, one
can always find a message such that, before the message is sent, the outcome
is not yet determined, but once the message has been sent it becomes
determined. This means that the party who receives this ‘extra’ information
first can always bias the protocol. This limitation cannot be overcome in the
classical world. Therefore, there is no value of $\varepsilon<0.5$ for which,
the protocol can be secure. However, using non-orthogonal quantum states gives
the parties the ability to ‘hide’ their choice of the random bit before the
other party also flips a coin. Therefore the existence of quantum coin-
flipping protocols with a certain degree of bias is closely related to the
fact that an adversary, is fundamentally bounded by quantum mechanics, in
performing the task of distinguishing non-orthogonal quantum states.

Now, going back to our selected protocols, we have the two following cases:

  1. 1.

The protocol of Mayers et. al. [307] (denoted by $\mathcal{P}_{1}$) in which
the states, $\\{\ket{\phi_{0,0}},\ket{\phi_{1,0}}\\}$ are used (which have a
fixed overlap $s=\cos\left(2\phi\right)$).

  2. 2.

The protocol of Aharonov et. al. [33] (denoted by $\mathcal{P}_{2}$), which
uses the full set of states, _i.e._ $\\{\ket{\phi_{x,a}}\\}$.

This set of states is conveniently related through a reparameterisation of the
angle $\phi$ [86], which makes them easier to deal with mathematically.

In general for the security analysis of strong quantum coin-flipping
protocols, one considers both cases where Alice or Bob are being dishonest.
Here, for simplicity of comparison and since our goal is to demonstrate
cloning-based attacks, we only focus on a dishonest Bob who tries to bias the
bit by cloning the non-orthogonal states sent by Alice.

In the following two subsections, the biases are computed assuming access to
the _ideal_ cloning machine (_i.e._ the one which clones the input states with
the optimal, analytical fidelities). Later, we compare these ideal biases with
those achievable using the quantum cloning machines learned by our variational
quantum cloner.

##### Cloning attack on 2-state quantum coin flipping protocol

The Mayers’ protocol was incidentally one of the first protocols proposed for
strong quantum coin-flipping. Here, Alice utilizes the states333Since the
value of the overlap is the only relevant quantity, the different
parameterisation of these states compared to the ones in Eq. (7.5) does not
make a difference for our purposes. However, we note that explicit cloning
unitary would be different in both cases. $\ket{\phi_{0}}:=\ket{\phi_{0,0}}$
and $\ket{\phi_{1}}:=\ket{\phi_{1,0}}$ such that the angle between them is
$\phi:=\frac{\pi}{18}\implies s:=\cos(\frac{\pi}{9})$. In the following, we
describe the general version of the protocol with $k$ rounds (of quantum
communication). We also discuss the proposed attack in more detail and prove
the relevant theorems for fixed-overlap state-dependent cloning attacks.

######  Protocol 6 ($\mathcal{P}_{1}$ with $k$ rounds).

During the protocol, each party sends multiple copies of either
$\ket{\phi_{0}}\otimes\ket{\phi_{1}}$ or $\ket{\phi_{1}}\otimes\ket{\phi_{0}}$

  1. 1.

Alice and Bob now choose $k$ random bits, $\\{a_{1},\dots,a_{k}\\}$ and
$\\{b_{1},\dots,b_{k}\\}$ respectively. The final bit is now equal to the XOR
of input bits over all $k$ rounds _i.e._ ,

$x=\bigoplus_{j}a_{j}\oplus\bigoplus_{j}b_{j}$ (7.6)

  2. 2.

Each round has $n$ steps identified by $i$: In each round $j=1,\dots,k$ of the
protocol, and for every step $i=1,\dots,n$ within each round, Alice uniformly
picks a random bit $c_{i,j}$ and sends the state
$\ket{\phi_{c}^{i,j}}:=\ket{\phi_{c_{i,j}}}\otimes\ket{\phi_{\overline{c_{i,j}}})}$
to Bob (where $\overline{c_{i,j}}$ denotes the complement of $c_{i,j}$).

  3. 3.

Bob uniformly picks a random bit $d_{i,j}$ and sends the state
$\ket{\phi_{d}^{i,j}}:=\ket{\phi_{d_{i,j}}}\otimes\ket{\phi_{\overline{d_{i,j}}}}$
to Alice.444Note that if $c_{i,j}$ and $d_{i,j}$ are chosen independently of
$a_{j}$ and $b_{j}$, no information about the primary bits has been
transferred.

  4. 4.

For each $j$ and $i$, Alice announces the value $a_{j}\oplus c_{i,j}$.

  5. 5.

If $a_{j}\oplus c_{i,j}=0$, Bob returns the second state of the pair $(i,j)$
back to Alice, and sends the first state otherwise.

  6. 6.

Bob announces $b_{j}\oplus d_{i,j}$.

  7. 7.

Alice returns one of the states back to Bob accordingly (similar to step 5).

  8. 8.

$a$ and $b$ are announced by both sides.

  9. 9.

Alice measures the remaining states with the projectors,
$(E_{b},E^{\perp}_{b})$ and the returned states by Bob with
$(E_{\overline{a}},E^{\perp}_{\overline{a}})$ (Eq. (7.7)). She aborts the
protocol if the measurement result corresponds to $\perp$, and declares Bob as
being dishonest555The similar verification measurement is performed by Bob to
verify Alice, however here we skip that part since we are only interested in
half of the protocol, _i.e._ dishonest Bob.

Considering steps (5) to (7) of the protocol, we argue that it is sufficient
to only consider a single round in the protocol from the point of view of a
cloning attack. This is because a dishonest Bob can bias the protocol if he
learns about Alice’s bit $a_{j}$ (for any choice of $j$), which he can do by
guessing $c_{i,j}$ with probability better than $1/2$. With this knowledge,
Bob only needs to announce a single false $b_{j}\oplus d_{i,j}$ to cheat, and
so this strategy can be deferred to the final round [307]. Hence a single
round of the protocol is sufficient for analysis, and we herein drop the $j$
index.

In the last phase of the protocol, after $a$ and $b$ are announced by both
sides (so $x$ can be computed by both sides), Alice performs the measurements
$(E_{b},E^{\perp}_{b})$ and $(E_{\overline{a}},E^{\perp}_{\overline{a}})$ on
the remaining states. (as defined in Eq. (7.7)) for checking whether Bob has
cheated or not. In this sense, the use of quantum states in this protocol is
purely for cheat-detection.

$\displaystyle E_{l}$ $\displaystyle=\ket{\phi_{l}}\bra{\phi_{l}}^{\otimes n}$
(7.7) $\displaystyle E_{l}^{\perp}$
$\displaystyle=\mathds{1}-\ket{\phi_{l}}\bra{\phi_{l}}^{\otimes n},\qquad
l\in\\{0,1\\}$ (7.8)

A Cloning Attack on $\mathcal{P}_{1}$: Next, we present the explicit attack
and calculation that can be implemented by Bob on $\mathcal{P}_{1}$. Without
loss of generality, we assume that Bob wishes to bias the bit towards $x=0$.
For clarity, we give the attack for when Alice only sends one copy of the
state ($n=1$), but we discuss the general case later:

######  Attack 1 (Cloning Attack on $\mathcal{P}_{1}$ with $k=1$).

The goal is to bias the bit towards $0$, _i.e._ $p(x=0)>1/2$ Inputs. Random
bit for Alice ($a\overset{\$}{\leftarrow}\\{0,1\\}$) and Bob
($b\overset{\$}{\leftarrow}\\{0,1\\}$). Bob receives a state
$\ket{\phi_{c}^{i}}$ from Alice.
The attack:

  1. 1.

for $i=1,\dots,n$:

    1. (a)

Step 1: Alice announces $a\oplus c_{i}$. If $a\oplus c_{i}=0$, Bob sends the
second qubit of $\ket{\phi_{c}^{i}}$ to Alice, otherwise he sends the first
qubit.

    2. (b)

Step 2: Bob runs a $1\rightarrow 2$ state-dependent cloner on the qubit he has
to return to Alice, producing $2$ approximate clones. He sends her one clone
and keeps the other.

    3. (c)

Step 3: Bob runs an optimal state discrimination on the remaining qubit (and
any other auxiliary output of the cloner, if exists), and finds $c_{1}$ with a
maximum success probability
$P^{\mathrm{opt}}_{\mathrm{disc},\mathcal{P}_{1}}$. He then guesses a bit
$a^{\prime}$ such that
$P_{\mathrm{succ},\mathcal{P}_{1}}(a^{\prime}=a):=P^{\mathrm{opt}}_{\mathrm{disc},\mathcal{P}_{1}}$.

    4. (d)

Step 4: If $a^{\prime}\oplus b=0$ he continues the protocol honestly and
announces $b\oplus d_{1}$, otherwise he announces $a^{\prime}\oplus d_{1}$.
The remaining qubit on Alice’s side is $\ket{\phi^{i}_{a}}$.

Now, we find the success probability of the above attack:

######  Theorem 50.

[Bias of ideal cloning attack on $\mathcal{P}_{1}$] Bob can achieve a bias of
$\varepsilon\approx 0.27$ using an ideal state-dependent cloning attack on the
protocol $\mathcal{P}_{1}$ using a single copy of Alice’s state.

###### Proof.

As mentioned in the previous section, the final measurements performed by
Alice on her remaining $n$ states, plus the $n$ states returned to her by Bob
allow her to detect his nefarious behaviour. If he performed a cloning attack,
the $\perp$ outcomes would be detected by Alice with some probability. We must
compute both probabilities: the probability of guessing the value of Alice’s
bit $a$ (by guessing the value of the bit $c_{1}$), and the probability of
being detected by Alice. This would provide us with Bob’s final success
probability in cheating, hence the bias probability.

At the start of the attack, Bob has a product state of either
$\ket{\phi_{0}}\otimes\ket{\phi_{1}}$ or $\ket{\phi_{1}}\otimes\ket{\phi_{0}}$
(but he does not know which). After the announcement stage, depending on
Alice’s announced bit, Bob proceeds to clone one of the qubits, sends one copy
to Alice and keeps the other to himself. Without loss of generality, we assume
that Alice’s announced bit is $0$. In this case, at this point of the attack,
he has one of the following pairs:
$\ket{\phi_{0}}\bra{\phi_{0}}\otimes\rho^{1}_{c}$ or
$\ket{\phi_{1}}\bra{\phi_{1}}\otimes\rho^{0}_{c}$, where $\rho^{1}_{c}$ and
$\rho^{0}_{c}$ are leftover clones (the second state of the cloner together
with any existing ancillary systems) for $\ket{\phi_{1}}$ and $\ket{\phi_{0}}$
respectively.

Bob must now discriminate between the following density matrices:

$\displaystyle\rho_{1}$
$\displaystyle=\ket{\phi_{0}}\bra{\phi_{0}}\otimes\ket{\phi_{1}}\bra{\phi_{1}}$
(7.9) $\displaystyle\textrm{ and }\qquad\rho_{2}$
$\displaystyle=\ket{\phi_{1}}\bra{\phi_{1}}\otimes\rho^{0}_{c}$ (7.10)

Alternatively, if Alice announced $a\oplus c_{i}=1$, he would have:

$\displaystyle\rho_{1}$
$\displaystyle=\ket{\phi_{1}}\bra{\phi_{1}}\otimes\ket{\phi_{0}}\bra{\phi_{0}},$
(7.11) $\displaystyle\textrm{ and }\qquad\rho_{2}$
$\displaystyle=\ket{\phi_{0}}\bra{\phi_{0}}\otimes\rho^{1}_{c}$ (7.12)

In either case, we have that the minimum discrimination error for two density
matrices is given by the Holevo-Helstrom bound [218, 212] (also see Section
2.2 for more information) bound as follows666This also is because we assume a
symmetric cloning machine for both $\ket{\phi_{0}}$ and $\ket{\phi_{1}}$. If
this is not the case, the guessing probability is instead the average of the
discrimination probabilities of both cases.:

$P^{\mathrm{opt}}_{\mathrm{disc}}=\frac{1}{2}+\frac{1}{4}|\\!|\rho_{1}-\rho_{2}|\\!|_{\mathsf{Tr}}=\frac{1}{2}+\frac{1}{2}d_{\text{Tr}}(\rho_{1},\rho_{2})$
(7.13)

The ideal symmetric cloning machine for these states will have an output of
the form:

$\rho_{c}=\alpha\ket{\phi_{0}}\bra{\phi_{0}}+\beta\ket{\phi_{1}}\bra{\phi_{1}}+\gamma(\ket{\phi_{0}}\bra{\phi_{1}}+\ket{\phi_{1}}\bra{\phi_{0}})$
(7.14)

where $\alpha,\beta$ and $\gamma$ are functions of the overlap
$s=\bra{\phi_{0}}\phi_{1}\rangle=\cos{\frac{\pi}{9}}$. Now, using Eq. (7.9),
$\rho_{2}$ can be written as follows:

$\begin{split}\rho_{2}=&\alpha\ket{\phi_{1}}\bra{\phi_{1}}\otimes\ket{\phi_{0}}\bra{\phi_{0}}+\beta\ket{\phi_{1}}\bra{\phi_{1}}\otimes\ket{\phi_{1}}\bra{\phi_{1}}\\\
&+\gamma(\ket{\phi_{1}}\bra{\phi_{1}}\otimes\ket{\phi_{0}}\bra{\phi_{1}}+\ket{\phi_{1}}\bra{\phi_{1}}\otimes\ket{\phi_{1}}\bra{\phi_{0}})\end{split}$
(7.15)

Finally, by plugging in the values of the coefficients in Eq. (7.14) for the
optimal local cloning machine [50] and finding the eigenvalues of
$\sigma:=(\rho_{1}-\rho_{2})$, we can calculate the corresponding value for
Eq. (7.13), and recover the following minimum error probability:

$P_{\mathrm{fail},\mathcal{P}_{1}}=P^{\mathrm{er}}_{\mathrm{disc},\mathcal{P}_{1}}=1-P^{\mathrm{opt}}_{\mathrm{disc},\mathcal{P}_{1}}\approx
0.214$ (7.16)

This means that Bob can successfully guess $c_{1}$ with
${P}^{1}_{\textrm{succ},\mathcal{P}_{1}}=78.5\%$ probability.

Now we look at the probability of a cheating Bob being detected by Alice. We
note that whenever Bob guesses $a$ successfully, the measurements
$(E_{b},E^{\perp}_{b})$ will be passed with probability $1$, hence we use
$(E_{\overline{a}},E^{\perp}_{\overline{a}})$ where the states sent by Bob
will be measured. Using Eq. (2.79) (in Section 2.3.1) with the value of
overlap $s=\cos\left(\pi/9\right)$, the optimal fidelity is
$F_{\mathsf{L}}\approx 0.997$ and so the probability of Bob getting caught is
at most $1\%$. Putting this together with Bob’s guessing probability for $a$
gives his overall success probability of $77.5\%$.

This implies that Bob is able to successfully create a bias of
$\varepsilon\approx 0.775-0.5=0.275$. ∎

We also have the following corollary, for a general number $n$ of exchanged
states, which shows the protocol can be completely broken and Bob can enforce
an arbitrary bias:

######  Corollary 9.

The probability of Bob successfully guessing Alice’s bit $a$, over $n$ rounds
and from all $n$ copies of the received stated, has the property:
$\lim\limits_{n\rightarrow\infty}{P}^{n}_{\mathrm{succ},\mathcal{P}_{1}}=1$
(7.17)

###### Proof.

If Bob repeats the above Attack 1 over all $n$ copies, he will guess $n$
different bits $\\{a^{\prime}_{i}\\}_{i=1}^{n}$. He can then take a majority
vote and announce $b$ such that $a^{*}\oplus b=0$, where we denote $a^{*}$ as
the bit he guesses in at least $\frac{n}{2}+1$ of the rounds.

If $n$ is even, he may have guessed $a^{\prime}$ to be $0$ and $1$ an equal
number of times. In this case, the attack becomes indecisive and Bob is forced
to guess at random. Hence we separate the success probability for even and odd
$n$ as follows:

$P^{n}_{\textrm{succ},\mathcal{P}_{1}}=\begin{cases}\sum\limits_{k=\frac{n+1}{2}}^{n}\binom{n}{k}(1-P_{\mathrm{fail}})^{k}P_{\mathrm{fail}}^{n-k}&n\text{
odd,}\\\
\sum\limits_{k=\frac{n}{2}+1}^{n}\binom{n}{k}(1-P_{\mathrm{fail}})^{k}P_{\mathrm{fail}}^{n-k}+\frac{1}{2}\binom{n}{n/2}(1-P_{\mathrm{fail}})^{\frac{n}{2}}P_{\mathrm{fail}}^{\frac{n}{2}}&n\text{
even}\\\ \end{cases}$ (7.18)

By substituting the value of $P_{\mathrm{fail}}$ one can see that the function
is uniformly increasing with $n$ so
$\lim\limits_{n\rightarrow\infty}{P}^{n}_{\textrm{succ},\mathcal{P}_{1}}=1$777Although,
as Bob’s success probability in guessing correctly increases with $n$, the
probability of his cheating strategy getting detected by Alice will also
increase, yet does not converge to 1 as fast. We also note that this strategy
is independent of $k$, the number of different bits used during the protocol..
This concludes the proof. ∎

##### Cloning attack on 4-state quantum coin flipping protocol

Another class of coin-flipping protocols are those which require all the four
states in Eq. (7.5). One such protocol was proposed by Aharonov et al. [33],
where the optimal $\phi$ is set as $\frac{\pi}{8}$ _i.e._ resulting in the
following states:

$\ket{\phi_{x,a}}=\begin{cases}\ket{{\frac{\pi}{8}}_{x,0}}=\cos\left(\frac{\pi}{8}\right)\ket{0}+(-1)^{x}\sin\left(\frac{\pi}{8}\right)\ket{1}\\\
\ket{{\frac{\pi}{8}}_{x,1}}=\sin\left(\frac{\pi}{8}\right)\ket{0}+(-1)^{x\oplus
1}\cos\left(\frac{\pi}{8}\right)\ket{1}\end{cases}$ (7.19)

In protocols of this form, Alice encodes her bit as ‘basis information’ of the
family of states. More specifically, her random bit is encoded in the state
$\ket{\phi_{x,a}}$. For instance, we can take
$\\{\ket{\phi_{0,0}},\ket{\phi_{1,0}}\\}$ to encode the bit $a=0$; and
$\\{\ket{\phi_{0,1}},\ket{\phi_{1,1}}\\}$ to encode $a=1$. The goal again is
to produce a final ‘coin flip’ $y=a\oplus b$, while ensuring that no party has
biased the bit $y$. A similar protocol has also been proposed using BB84
states [35] where
$\ket{\phi_{0,0}}:=\ket{0},\ket{\phi_{0,1}}:=\ket{1},\ket{\phi_{1,0}}:=\ket{+}$
and $\ket{\phi_{1,1}}:=\ket{-}$. In this case, the states (as well as some
protocol steps) are different but the angle between them is the same as with
the states in $\mathcal{P}_{2}$. A fault-tolerant version of $\mathcal{P}_{2}$
has also been proposed in Ref. [36], which uses a generalized angle as in Eq.
(7.5).

######  Protocol 7 ($\mathcal{P}_{2}$ (Aharonov’s coin flipping)).

The protocol uses all four possible states from Eq. (7.109).

  1. 1.

Alice selects two random bits $a\overset{\$}{\leftarrow}\\{0,1\\}$ and
$x\overset{\$}{\leftarrow}\\{0,1\\}$.

  2. 2.

Alice sends one of the states, $\ket{\phi_{x,a}}$ to Bob.

  3. 3.

Bob selects his random bit $b\overset{\$}{\leftarrow}\\{0,1\\}$ and sends to
Alice.

  4. 4.

One of two following things happens:

    1. (a)

(either) Alice will send the bits $x$ and $a$ to Bob, who measures the qubit
on a suitable basis to check if Alice was honest.

    2. (b)

(or) Bob is asked to return the qubit $\ket{\phi_{x,a}}$ to Alice, who
measures it and verifies if it is correct.

  5. 5.

If no party declares cheating, the final output bit, will be $c=a\oplus b$.

Now, we can discuss the cheating strategies of each of the players. Examples
of the cheating strategies for Alice include incorrect preparation of
$\ket{\phi_{x,a}}$ and giving Bob the wrong information about $(x,a)$, or Bob
trying to determine the bits $x,a$ from $\ket{\phi_{x,a}}$ before Alice has
revealed them classically. We again focus only on Bob’s strategies here to use
cloning arguments. We note that the information-theoretic achievable bias of
$\varepsilon=0.42$ proven in Ref. [33] applies only to Alice’s strategy since
she has greater control of the protocol (she prepares the original state). In
general, with a cloning based attack strategy, Bob will be able to achieve a
lower bias, as we show next. As mentioned above, Bob randomly selects his own
bit $b$ and sends it to Alice. He then builds a QCM to clone all 4 states in
Eq. (7.109).

We next sketch the two cloning attacks on Bob’s side of $\mathcal{P}_{2}$.
Again, as with the protocol, $\mathcal{P}_{1}$, Bob can cheat using as much
information as he can gain about $a$ and again, once Bob has performed the
cloning, his strategy boils down to the problem of state discrimination. In
both attacks, Bob will use a state-dependent cloning machine.

In the first attack model (which we denote I - see Fig. 7.6(a) in Section
7.4.2 where we introduce the variational cloning version of the attack) Bob
measures _all_ the qubits outputted from the cloner to guess $(x,a)$. As such,
it is the _global_ fidelity that will be the relevant quantity. This strategy
would be useful in the first possible challenge in the protocol, where Bob is
not required to send anything back to Alice. We will discuss how using cloning
in this type of attack can also reduce practical resources for Bob from a
general POVM to projective measurements, which may be of independent interest.
The main attack here boils down to Bob measuring the global output state from
his QCM using the projectors
$\\{\ket{v}\bra{v},\ket{v^{\perp}}\bra{v^{\perp}}\\}$, and from this
measurement, determines $a$. These projectors are constructed explicitly
relative to the input states using the Neumark theorem [75] (see Section 2.2).

The second attack model (which we denote II - see Fig. 7.6(a) in Section
7.4.2) is instead a _local_ attack and as such will depend on the optimal
local fidelity. It may also be more relevant in the scenario where Bob is
required to return a quantum state to Alice. We note that Bob could also apply
a global attack in this scenario but we do not consider this possibility here
to give more interesting and distinct examples. In what follows we explain the
attacks in detail. For simplicity, we compute a bias assuming he does not
return a state to Alice thus the bias will be equivalent to his discrimination
probability. The analysis could be tweaked to take a detection probability for
Alice into account as well. In this scenario, Bob again applies the QCM, but
now he only uses one of the clones to perform state discrimination (given by
the _Discriminator_ in Fig. 7.6(a)).

Attack I on $\mathcal{P}_{2}$:
We note that attack I, is a $4$ state _global_ attack on $\mathcal{P}_{2}$ and
that this attack model (_i.e._ based on cloning) can be considered a
constructive way of implementing the optimal discrimination strategy of the
states Alice is to send. To bias the bit, Bob needs to discriminate between
the four pure states in Eq. (7.5) or equivalently between the ensembles of
states encoding $a=\\{0,1\\}$, where the optimal discrimination is done via a
set of POVM measurements.

However, by implementing a cloning based attack, we can simplify the
implementation of optimal discrimination strategies. This is because the
symmetric state-dependent cloner (which is a unitary) has the interesting
feature that for either case ($a=0$ or $a=1$), the cloner’s output is a pure
state in the $2$-qubit Hilbert space. As such, the states (after going through
the QCM) can be optimally discriminated via a set of projective measurements
$\\{P_{v},P_{v^{\perp}}\\}$, rather than general POVMs. This may not seem very
important at this stage, but later we will see that it will relate a
theoretical bound to an implementational attack strategy. Especially when we
introduce the variational cloner that can learn to optimally clone these
states efficiently, which, in turn, will assist the benchmarking of existing
protocols. Let us now establish this bound and prove it.

######  Theorem 51.

[Ideal Cloning Attack (I) Bias on $\mathcal{P}_{2}$] Using a cloning attack on
the protocol, $\mathcal{P}_{2}$, (in attack model I) Bob can achieve a bias:
$\varepsilon^{\mathrm{I}}_{\mathcal{P}_{2},\mathrm{ideal}}\approx 0.35$ (7.20)

###### Proof.

The attack involves the global output state of the cloning machine. For this
attack we can use the fixed overlap $1\rightarrow 2$ cloner with the global
fidelity given by Eq. (2.80):

$F^{{\mathrm{FO},\textrm{opt}}}_{\mathsf{G}}(1,2)=\frac{1}{2}\left(1+s^{3}+\sqrt{1-s^{2}}\sqrt{1-s^{4}}\right)\approx
0.983$ (7.21)

where $s=\sin(2\phi)=\cos(\frac{\pi}{4})$ for $\mathcal{P}_{2}$. Also
alternatively we can use the 4-state cloner which clones the two states with a
fixed overlap plus their orthogonal set. For both of these cloners, we are
interested in the global state of the cloner which we denote as
$\ket{\psi_{x,a}^{1\rightarrow 2}}$ for an input state $\ket{\phi_{x,a}}$.

In order for Bob to guess $a$ he must discriminate between $\ket{\phi_{0,0}}$
(encoding $a=0$) and $\ket{\phi_{1,1}}$ (encoding $a=1$) or alternatively the
pair of states $\\{\ket{\phi_{0,1}},\ket{\phi_{1,0}}\\}$. This is due to the
pairs $\\{\ket{\phi_{0,0}},\ket{\phi_{0,1}}\\}$ being orthogonal and
$\\{\ket{\phi_{1,0}},\ket{\phi_{1,1}}\\}$ both encode $a=0$, so the only
choice is to discriminate between $\ket{\phi_{0,0}}$ and $\ket{\phi_{1,1}}$.
Due to the symmetry and without an ancilla, the cloner preserves the overlap
between each pairs _i.e._ $\bra{\psi_{0,0}^{1\rightarrow
2}}\psi_{1,1}^{1\rightarrow 2}\rangle=\bra{\phi_{0,0}}\phi_{1,1}\rangle=s$ (we
also have $\bra{\psi_{0,1}^{1\rightarrow 2}}\psi_{1,0}^{1\rightarrow
2}\rangle=s$).

Now we select the projective measurements $P_{v}=\ket{v}\bra{v}$ and
$P_{v^{\perp}}=\ket{v^{\perp}}\bra{v^{\perp}}$ such that
$\bra{v}v^{\perp}\rangle=0$. One can show that the discrimination probability
is optimal when $\ket{v}$ and $\ket{v^{\perp}}$ are symmetric with respect to
the target states according to the Neumark theorem. We have that
$\bra{v}v^{\perp}\rangle=0$ so
$2\theta+2\phi=\frac{\pi}{2}\Rightarrow\theta=\frac{\pi}{4}-\phi$. Finally,
writing the cloner’s states for $\\{\ket{\psi_{0,0}^{1\rightarrow
2}},\ket{\psi_{1,1}^{1\rightarrow 2}}\\}$ in the basis
$\\{\ket{v},\ket{v^{\perp}}\\}$ gives:

$\begin{split}&\ket{\psi_{0,0}^{1\rightarrow
2}}=\cos\left(\frac{\pi}{4}-\phi\right)\ket{v}+\sin\left(\frac{\pi}{4}-\phi\right)\ket{v^{\perp}},\\\
&\ket{\psi_{1,1}^{1\rightarrow
2}}=\cos\left(\frac{\pi}{4}-\phi\right)\ket{v}-\sin\left(\frac{\pi}{4}-\phi\right)\ket{v^{\perp}}\end{split}$
(7.22)

where it can be checked that $\bra{\psi_{0,0}^{1\rightarrow
2}}\psi_{1,1}^{1\rightarrow
2}\rangle=\cos\left(\frac{\pi}{2}-2\phi\right)=\sin\left(2\phi\right)=s$.
Hence $\ket{v}$ and $\ket{v^{\perp}}$ can be explicitly derived. Note that
these bases are also symmetric with respect to the other pair i.e
$\\{\ket{\psi_{0,1}^{1\rightarrow 2}},\ket{\psi_{1,0}^{1\rightarrow 2}}\\}$.
Finally, the success probability of this measurement is then given by:

$P^{\mathrm{opt},\mathrm{I}}_{\mathrm{disc},\mathcal{P}_{2}}=\frac{1}{2}+\frac{1}{2}\bra{\psi_{0,0}^{1\rightarrow
2}}\psi_{1,1}^{1\rightarrow
2}\rangle=\frac{1}{2}+\frac{1}{2}\sin{2\phi}=0.853$ (7.23)

which is the maximum cheating probability for Bob. From this, we derive the
bias as:

$\varepsilon^{\mathrm{I}}_{\mathcal{P}_{2},\mathrm{ideal}}=P^{\mathrm{opt},\mathrm{I}}_{\mathrm{disc},\mathcal{P}_{2}}-\frac{1}{2}=0.353$
(7.24)

which completes the proof. ∎

Attack II on $\mathcal{P}_{2}$:

Finally, we consider a second attack model (attack II) on the protocol,
$\mathcal{P}_{2}$, which is in the form of a ‘local’ attack. Here, we further
consider two scenarios:

  1. 1.

A cloning machine which is able to clone _all_ $4$ states
$\ket{\phi_{0,0}},\ket{\phi_{1,1}}$ _and_ $\ket{\phi_{0,1}},\ket{\phi_{1,0}}$,

  2. 2.

A cloning machine tailored for only the two states, $\ket{\phi_{0,0}}$ and
$\ket{\phi_{1,1}}$ (which Bob needs to discriminate between).

We focus on the former scenario since it connects in a more clear way to the
$\operatorname{\textsf{VarQlone}}$ clone fidelities, while the second scenario
enables a stronger attack (in the ideal scenario).

Scenario 1:

In this case, we can compute an exact discrimination probability, but it will
result in a non-optimal attack (smaller success probability compared to the
second one).

######  Theorem 52.

[Ideal Cloning Attack (II) Bias on $\mathcal{P}_{2}$ in Scenario $1$.] Using a
cloning attack on the protocol $\mathcal{P}_{2}$, (in attack model II with
$4$-states) Bob can achieve the following bias:
$\varepsilon^{\mathrm{II}}_{\mathcal{P}_{2},\mathrm{ideal}}=0.25$ (7.25)

###### Proof.

Considering the 4 states to be in the $\mathsf{X}-\mathsf{Z}$ plane of the
Bloch sphere, the density matrices of each state can be represented as:

$\rho_{ij}=\frac{1}{2}(\mathds{1}+m_{ij}^{x}\sigma_{x}+m_{ij}^{z}\sigma_{z})$
(7.26)

where $\sigma_{x}$ and $\sigma_{z}$ are Pauli matrices and $m_{ij}^{x}$ and
$m_{ij}^{z}$ are $3$ dimensional vectors given by:

$\begin{split}&m_{00}:=[\sin(2\phi),0,\cos(2\phi)]\\\
&m_{01}:=[-\sin(2\phi),0,-\cos(2\phi)]\\\
&m_{10}:=[-\sin(2\phi),0,\cos(2\phi)]\\\
&m_{11}:=[\sin(2\phi),0,-\cos(2\phi)]\end{split}$ (7.27)

After the cloning (in the ideal case), the density matrix of each clone will
become:

$\rho_{ij}^{c}=\frac{1}{2}(\mathds{1}+\eta_{x}m_{ij}^{x}\sigma_{x}+\eta_{z}m_{ij}^{z}\sigma_{z})$
(7.28)

where $\eta_{x}$ and $\eta_{z}$ are the shrinking factors in each direction
given as follows:

$\eta_{x}=\sin^{2}(2\phi)\sqrt{\frac{1}{\sin^{4}(2\phi)+\cos^{4}(2\phi)}},\quad\quad\eta_{z}=\cos^{2}(2\phi)\sqrt{\frac{1}{\sin^{4}(2\phi)+\cos^{4}(2\phi)}}$
(7.29)

For the states used in $\mathcal{P}_{2}$, we have $\phi=\frac{\pi}{8}$ and
hence $\eta_{x}=\eta_{z}:=\eta=\frac{1}{\sqrt{2}}$. Again, we can reduce the
problem to the discrimination probability between the two ensembles encoding
$a=0$ and $a=1$ in Eq. (7.32). Let us define $\rho^{c}$ to be the output clone
that Bob chooses to use ($c\in\\{1,2\\}$). We have:

$\begin{split}P^{\mathrm{opt},\mathrm{II}}_{\mathrm{disc},\mathcal{P}_{2}}&=\frac{1}{2}+\frac{1}{4}\left|\left|\rho_{(a=0)}-\rho_{(a=1)}\right|\right|_{\mathsf{Tr}}\\\
&=\frac{1}{2}+\frac{1}{4}\left|\left|\frac{1}{2}\left[(\rho_{00}^{c}-\rho_{11}^{c})+(\rho_{10}^{c}-\rho_{01}^{c}\right]\right|\right|_{\mathsf{Tr}}\\\
&=\frac{1}{2}+\frac{1}{4}\left|\left|\frac{\eta}{4}((m_{00}^{x}-m_{11}^{x}+m_{10}^{x}-m_{01}^{x})\sigma_{x}+(m_{00}^{z}-m_{11}^{z}+m_{10}^{z}-m_{01}^{z})\sigma_{z}\right|\right|_{\mathsf{Tr}}\\\
&=\frac{1}{2}+\frac{\eta\cos(2\phi)}{4}\left|\left|\sigma_{z}\right|\right|_{\mathsf{Tr}}\\\
&=\frac{1}{2}+\frac{\eta\cos(2\phi)}{2}=\frac{3}{4}\end{split}$ (7.30)

Computing the bias in the same way as above completes the proof. ∎

Scenario 2:

Here, we give a bound on the success probabilities of Bob in terms of the
local fidelities of the QCM where the cloning machine is only tailored to
clone two fixed-overlap states. We rely on the fact that Bob can discriminate
between the two ensembles of states (for $a=0$, $a=1$) with equal
probabilities.

######  Theorem 53.

The optimal discrimination probability for a cloning attack on the protocol
$P_{2}$, (in attack model II, with $2$ states) is: $0.619\leqslant
P^{\mathrm{opt},\mathrm{II}}_{\mathrm{disc},\mathcal{P}_{2}}\leqslant 0.823$
(7.31)

###### Proof.

For each of the input states, $\ket{\phi_{i,j}}$ in Eq. (7.109), we denote
$\rho_{ij}^{c}$ to be a clone outputted from the QCM. Due to symmetry, we only
need to consider one of the two output clones. We can now write the effective
states for each encoding ($a=0,a=1$) as:

$\rho_{(a=0)}:=\frac{1}{2}(\rho_{00}^{c}+\rho_{10}^{c}),\qquad\qquad\rho_{(a=1)}:=\frac{1}{2}(\rho_{01}^{c}+\rho_{11}^{c})$
(7.32)

Dealing with these two states is sufficient since it can be shown that
discriminating between these two density matrices, is equivalent to
discriminating between the entire set of $4$ states in Eq. (7.5).

Again, we use the discrimination probability from the Holevo-Helstrom bound:

$P^{\mathrm{opt},\mathrm{II}}_{\mathrm{disc},\mathcal{P}_{2}}:=P^{\mathrm{opt}}_{\mathrm{disc}}(\rho_{(a=0)},\rho_{(a=1)}):=\frac{1}{2}+\frac{1}{2}d_{\text{Tr}}(\rho_{(a=0)},\rho_{(a=1)})$
(7.33)

Now, we have:

$\begin{split}d_{\text{Tr}}(\rho_{(a=0)},\rho_{(a=1)})&=\frac{1}{2}\left|\left|\rho_{(a=0)}-\rho_{(a=1)}\right|\right|_{\mathsf{Tr}}\\\
&=\frac{1}{2}\left|\left|\frac{1}{2}(\rho_{00}^{c}-\rho_{11}^{c})+\frac{1}{2}(\rho_{10}^{c}-\rho_{01}^{c})\right|\right|_{\mathsf{Tr}}\\\
&\leqslant\frac{1}{4}\left|\left|(\rho_{00}^{c}-\rho_{11}^{c})\right|\right|_{\mathsf{Tr}}+\left|\left|(\rho_{10}^{c}-\rho_{01}^{c})\right|\right|_{\mathsf{Tr}}\\\
&\leqslant\frac{1}{2}\left[d_{\text{Tr}}(\rho_{00}^{c},\rho_{11}^{c})+d_{\text{Tr}}(\rho_{01}^{c},\rho_{10}^{c})\right]\\\
\\\ \implies
P^{\mathrm{opt}}_{\mathrm{disc}}(\rho_{(a=0)},\rho_{(a=1)})&\leqslant\frac{1}{2}(P^{\mathrm{opt}}_{\mathrm{disc}}(\rho_{00}^{c},\rho_{11}^{c})+P^{\mathrm{opt}}_{\mathrm{disc}}(\rho_{01}^{c},\rho_{10}^{c}))\\\
&=P^{\mathrm{opt}}_{\mathrm{disc}}(\rho_{00}^{c},\rho_{11}^{c})\end{split}$
(7.34)

The last equality follows since for both ensembles,
$\\{\ket{\phi_{0,0}},\ket{\phi_{1,1}}\\}$ and
$\\{\ket{\phi_{0,1}},\ket{\phi_{1,0}}\\}$, we have that their output clones
having equal discrimination probability:

$P^{\mathrm{opt}}_{\mathrm{disc}}(\rho_{00}^{c},\rho_{11}^{c})=P^{\mathrm{opt}}_{\mathrm{disc}}(\rho_{01}^{c},\rho_{10}^{c})$
(7.35)

This is because the QCM is symmetric, and depends only on the overlap of the
states (we have in both cases
$\bra{\phi_{00}}\phi_{11}\rangle=\bra{\phi_{01}}\phi_{10}\rangle=\sin(2\phi)$).

Furthermore, since the cloning machine can only lower the discrimination
probability between two states, we have:

$P^{\mathrm{opt}}_{\mathrm{disc}}(\rho_{00}^{c},\rho_{11}^{c})\leqslant
P^{\mathrm{opt}}_{\mathrm{disc}}(\rho_{00}^{c},\ket{\phi_{1,1}}\bra{\phi_{1,1}})=:\overline{P^{\mathrm{opt}}_{\mathrm{disc}}}$
(7.36)

Now, using the relationship between fidelity and the trace distance (Eq.
(LABEL:)), we have the following bounds:

$\frac{1}{2}+\frac{1}{2}\left(1-\sqrt{\bra{\phi_{1,1}}\rho^{c}_{00}\ket{\phi_{1,1}}}\right)\leq\overline{P^{\mathrm{opt}}_{\mathrm{disc}}}\leq\frac{1}{2}+\frac{1}{2}\sqrt{1-\bra{\phi_{1,1}}\rho^{c}_{00}\ket{\phi_{1,1}}}$
(7.37)

By plugging this inequality in the observed density matrix for the output
clone, we can find this discrimination probability.

As in the previous section, the output density matrix from the QCM for an
output clone can be written as Eq. (7.14):

$\rho^{c}_{00}=\alpha\ket{\phi_{0,0}}\bra{\phi_{0,0}}+\beta\ket{\phi_{1,1}}\bra{\phi_{1,1}}+\gamma(\ket{\phi_{0,0}}\bra{\phi_{1,1}}+\ket{\phi_{1,1}}\bra{\phi_{0,0}})$
(7.38)

Hence the output state has a local fidelity,
$F_{\operatorname{\textsf{L}}}=\bra{\phi_{0,0}}\rho^{c}_{00}\ket{\phi_{0,0}}=\alpha+s^{2}\beta+s\gamma$.
On the other hand, we have
$F(\rho^{c}_{00},\ket{\phi_{1,1}}\bra{\phi_{1,1}})=\bra{\phi_{1,1}}\rho^{c}_{00}\ket{\phi_{1,1}}=s^{2}\alpha+\beta+s\gamma$.
Combining these two, we then have:

$F(\rho^{c}_{00},\ket{\phi_{1,1}}\bra{\phi_{1,1}})=F_{\operatorname{\textsf{L}}}+(s^{2}-1)(\alpha-\beta)$
(7.39)

Plugging in $F_{\operatorname{\textsf{L}}}$ from Eq. (2.79), and
$\alpha-\beta=\sqrt{\frac{1-s^{2}}{1-s^{4}}}$ (for an optimal state-dependent
cloner), we get:

$\frac{1}{2}+\frac{1}{2}\left[1-\sqrt{F_{\operatorname{\textsf{L}}}+(s^{2}-1)\sqrt{\frac{1-s^{2}}{1-s^{4}}}}\right]\leqslant
P^{\mathrm{opt},\textrm{II}}_{\mathrm{disc},\mathcal{P}_{2}}\leqslant\frac{1}{2}+\frac{1}{2}\sqrt{1-F_{\operatorname{\textsf{L}}}-(s^{2}-1)\sqrt{\frac{1-s^{2}}{1-s^{4}}}}$
(7.40)

To complete the proof, we use $F_{\operatorname{\textsf{L}}}\approx 0.989$ and
$s=1/\sqrt{2}$ which gives the numerical discrimination probabilities above. ∎

###  7.3 Variational Quantum Cloner: specifications of the algorithm

Now we introduce our machine learning algorithm _Variational Quantum Cloner_
or $\operatorname{\textsf{VarQlone}}$ that given a specific family of states,
learns the circuit that optimally clones that family. We recall that our
motivation is to find short-depth circuits to clone a given family of states,
and also use this toolkit to investigate the family of states where the
optimal figure of merit is unknown.

$\operatorname{\textsf{VarQlone}}$ is a variational quantum algorithm with
similar core parts to other VQAs. We have given an overview of such techniques
in the preliminaries (Section 2.6.4). In particular, this variational method
uses a parameterised state, denoted by $\rho_{\boldsymbol{\theta}}$, typically
prepared by some short-depth parameterised unitary on some initial state
$\rho_{\boldsymbol{\theta}}:=U(\boldsymbol{\theta})\ket{0}\bra{0}U^{\dagger}(\boldsymbol{\theta})$.