A Quantum Cloning Game with Applications to Quantum Position Verification

Colisson Palais, Léo; Escolà-Farràs, Llorenç; Speelman, Florian

doi:10.4230/LIPIcs.TQC.2025.2

A Quantum Cloning Game with Applications to Quantum Position Verification

Léo Colisson Palais

Laboratoire Jean Kuntzmann, Université Grenoble Alpes, France Llorenç Escolà-Farràs

TU Eindhoven, The Netherlands Florian Speelman

QuSoft & Informatics Institute, University of Amsterdam, The Netherlands

Abstract

We introduce a quantum cloning game in which $k$ separate collaborative parties receive a classical input, determining which of them has to share a maximally entangled state with an additional party (referee). We provide the optimal winning probability of such a game for every number of parties $k$ , and show that it decays exponentially when the game is played $n$ times in parallel. These results have applications to quantum cryptography, in particular in the topic of quantum position verification, where we show security of the routing protocol (played in parallel), and a variant of it, in the random oracle model.

Keywords and phrases:

Quantum position verification, cloning game, random oracle, parallel repetition

Funding:

Léo Colisson Palais: European Union (ERC, ASC-Q, 101040624) and the Dutch Ministry of Economic Affairs and Climate Policy (EZK), as part of the Quantum Delta NL programme.

Llorenç Escolà-Farràs: Dutch Ministry of Economic Affairs and Climate Policy (EZK), as part of the Quantum Delta NL programme.

Florian Speelman: Dutch Ministry of Economic Affairs and Climate Policy (EZK), as part of the Quantum Delta NL programme.

Copyright and License:

2012 ACM Subject Classification:

Security and privacy

\rightarrow

Cryptography

Editor:

Bill Fefferman

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Non-local correlations have extensively been studied in the field of quantum information theory, see e.g. [12]. Bell [9] originally showed that distant parties sharing quantum resources can reproduce correlations that could never be attained by any classical theory. Often, non-local correlations are studied as non-local games, which provide an operational framework for understanding them. These games are interesting per se from a fundamental point of view, since they give rise to understanding the underlying essence of nature, but they additionally lead to applications such as secure key distribution [1], certified randomness [33], reduced communication complexity [14], self-testing [32, 37], and computation [5].

A vast literature in non-local games covers the scenario where a classical referee sends questions to non-communicating collaborative parties, and their task is to produce answers according to a certain publicly-known predicate, where the questions and answers are all classical. The best-known non-local game is the CHSH game [18]. Non-locality has also been investigated in terms of supersets of non-local games, called monogamy-of-entanglement (MoE) games [38], where a quantum referee sends the same classical question to the players and the parties have to guess the (classical) outcome of a referee’s quantum measurement (depending on the question). MoE games have been used to provide security proofs for the quantum cryptographic primitives device-independent quantum key distribution [10] and quantum position verification [28]. Such games were later generalized under the name of extended non-local games [27].

Here, we introduce the concept of the quantum cloning game, played by $k$ distant parties and a quantum referee. The referee publically announces a party, i.e., sends the same classical question to all the players, and the chosen party has to end up with the maximally entangled (EPR) state with the referee. At the beginning of the game, the players are allowed to share any quantum state with the referee. In this work, we show that the optimal winning probability for players using any quantum resources is given by $\frac{1}{2}+\frac{1}{2k}$ , converging to $\frac{1}{2}$ for a large number of players. We analyze the game when it is played $n$ times in parallel, showing an exponential decay in $n$ of the optimal winning probability. Additionally, the quantum cloning game can be generalized to any arbitrary quantum state instead of an EPR state, and we provide its optimal winning probability.

We show that these results have applications in quantum position verification (QPV), which is a cryptographic primitive consisting of verifying the location of an untrusted party. Securely implementing this primitive is unachievable using only classical information, because a general attack exists even when using computational assumptions [17]. Due to the no-cloning theorem [41] the general classical attack does not apply if quantum information is used instead [28, 31], however, a general quantum attack exists which requires exponential entanglement [13, 8]. This means that hope for protocols secure against reasonable amounts of entanglement is alive, and indeed there has been much analysis on attacks on specific protocols [2, 28, 29, 34, 16, 36, 21, 22, 25, 20], and security analysis under extra assumptions [30, 24], such as the random oracle model [39]. A generic 1-dimensional (the main ideas generalize to higher dimensions) QPV protocol is described in the following way: two verifiers V₀ and V₁, placed on the left and right of an untrusted prover P, supposedly at the position $p o s$ , send quantum and classical messages to P at the speed of light, and he has to pass a challenge and reply correctly to them at the speed of light as well, if so, the verifiers accept, and if any of them receives a wrong answer or the timing does not correspond with the time it would have taken for light to travel back from the honest prover, the verifiers reject. The time consumed by the prover to perform the challenge is assumed to be negligible, and the verifiers are assumed to have perfectly-synchronized clocks.

In this work, we consider the routing QPV protocol [28], which has an appealing simple form: the prover has to return a received qubit to one of the verifiers, where the choice of verifier is a function of the classical information sent by the verifiers [28]. Besides the theoretical interest of this protocol, it is also an appealing candidate for free-space quantum position verification, when the quantum messages can travel with the vacuum speed of light, since the hardware of the prover could hypothetically be as simple as a mirror or an optical switch. Despite theoretical work on this protocol [15, 20, 11, 3, 6], there were gaps left in our understanding relative to measurement-based QPV protocol variants: namely the security of parallel repetition of this protocol against unentangled attackers and attackers who pre-share a linear (in the security parameter) amount of entangled qubits, and its security in the random-oracle model against arbitrary adversaries. As an application of the quantum cloning game, we show the security of the routing protocol in these scenarios.

2 Preliminaries

For $k\in\mathbb{N}$ , we will denote $[k]:=\{0,\ldots,k-1\}$ . Let $\mathcal{H}$ , $\mathcal{H^{\prime}}$ be finite-dimensional Hilbert spaces, we denote by $\mathcal{B}(\mathcal{H},\mathcal{H^{\prime}})$ the set of bounded operators from $\mathcal{H}$ to $\mathcal{H^{\prime}}$ and $\mathcal{B}(\mathcal{H})=\mathcal{B}(\mathcal{H},\mathcal{H})$ . Denote by $\mathcal{S}(\mathcal{H})$ the set of quantum states on $\mathcal{H}$ , i.e. ${\mathcal{S}(\mathcal{H})=\{\rho\in\mathcal{B}(\mathcal{H})\mid\rho\geq 0,% \mathrm{Tr}\left[\rho\right]=1)\}}$ . A pure state will be denoted by a ket $|\psi\rangle\in\mathcal{H}$ . The maximally entangled state or EPR pair is ${|\Phi^{+}\rangle=\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)}$ . We denote the identity matrix by $\mathbb{I}$ . For $M\in\mathcal{B}(\mathcal{H})$ , we denote its Schatten $\infty$ -norm by $\|M\|$ . We will use the notation $1,\ldots,\not{i},\ldots,k-1$ to denote $1,\ldots,i-1,i+1,\ldots,k-1$ .

Definition 1.

Let $N\in\mathbb{N}$ . Two permutations $\pi,\pi^{\prime}:[N]\rightarrow[N]$ are said to be orthogonal if $\pi(i)\neq\pi^{\prime}(i)$ for all $i\in[N]$ .

Lemma 2 (Lemma 2 in [38]).

Let $\Pi^{1},\ldots,\Pi^{N}$ be projectors acting on a Hilbert space $\mathcal{H}$ . Let $\{\pi_{k}\}_{k\in[n]}$ be a set of mutually orthogonal permutations. Then,

\bigg\|\sum_{i\in[N]}\Pi^{i}\bigg\|\leq\sum_{k\in[N]}\max_{i\in[N]}\big\|\Pi^{% i}\Pi^{\pi_{k}(i)}\big\|.

(1)

$\blacktriangleright$ Remark 3.

There always exist a set of $N$ permutations of $[N]$ that are mutually orthogonal, an example is the $N$ cyclic shifts.

Lemma 4 (Lemma 1 in [38]).

Let $A,B,L\in\mathcal{B}(\mathcal{H})$ such that $AA^{\dagger}\succeq B^{\dagger}B$ . Then it holds that $\|AL\|\geq\|BL\|$ .

3 $𝒌$ -party quantum cloning game

In the following definition, we introduce the quantum cloning game.

Definition 5.

The $k$ -party quantum cloning game, shortly denoted by QCG_k, consists of a referee $R$ with associated Hilbert space $\mathcal{H}_{R}=\mathbb{C}^{2}$ and $k$ collaborative distant parties (players) $P_{0},\ldots,P_{k-1}$ . Before the game starts, the parties prepare a joint quantum state of arbitrary dimension between themselves and the referee. During the game, the referee sends $x\in[k]$ , drawn uniformly at random, to all the collaborative parties. The players win the game if and only if the party $P_{x}$ (holding a qubit register $P_{x}$ ) ends up sharing the maximally entangled state with the referee, i.e. if a projection onto $|\Phi^{+}\rangle_{RP_{x}}$ yields the correct outcome.

See Figure 1 for a schematic representation of the ${\text{QCG}_{k}}$ . Intuitively, in such a game, the referee publically announces which party has to create an entangled state with herself.

Figure 1: Schematic representation of the

k

-party quantum cloning game, where

|\Psi\rangle_{RP_{x}}=|\Phi^{+}\rangle_{RP_{x}}

, where the gray-shaded region represents the shared state

\rho

. If

|\Psi\rangle_{RP_{x}}

is arbitrary, this represents a

\Psi

-QCG_k.

A strategy ${S}$ for the QCG_k is described by a quantum state $\rho\in\mathcal{S}(\mathcal{H}_{R}\otimes\mathcal{H}_{P_{0}E_{0}}\otimes\cdots% \otimes\mathcal{H}_{P_{k-1}E_{k-1}})$ , where, for $i\in[k]$ , registers $P_{i}$ are of the same dimension as $\mathcal{H}_{R}$ and $E_{i}$ are auxiliary systems of arbitrary dimension that each party possess, and completely positive trace-preserving (CPTP) maps $\{\mathcal{E}^{x}_{P_{i}E_{i}\rightarrow P_{i}}\}_{x}$ , where the subscript $P_{i}E_{i}\rightarrow P_{i}$ indicates that the map has input and output registers $P_{i}E_{i}$ and $P_{i}$ , respectively, i.e. $\mathcal{E}^{x}_{P_{i}E_{i}\rightarrow P_{i}}:\mathcal{B}(\mathcal{H}_{P_{i}E_% {i}})\rightarrow\mathcal{B}(\mathcal{H}_{P_{i}})$ . The winning probability of such a game, given the strategy $S$ , is provided by

\begin{split}&\omega(\text{QCG}_{k},S)=\frac{1}{k}\sum_{x\in[k]}\text{Tr}\bigg% [|\Phi^{+}\rangle\langle\Phi^{+}|_{RP_{x}}\mathrm{Tr}_{P_{0}\ldots\not{P}_{x}% \ldots P_{k-1}}\left[\mathbb{I}_{R}\bigotimes_{i\in[k]}\mathcal{E}^{x}_{P_{i}E% _{i}\rightarrow P_{i}}(\rho)\right]\bigg].\end{split}

(2)

The optimal winning probability of such games is given by

\omega^{*}(\text{QCG}_{k})=\sup_{S}\omega(\text{QCG}_{k},S),

(3)

where the supremum is taken over all the possible strategies over all possible Hilbert spaces. The following theorem gives the optimal winning probability of this game for every number of parties $k$ .

Theorem 6.

For every $k\in\mathbb{N}$ , the optimal winning probability of the $\emph{\text{QCG}}_{k}$ is given by

\omega^{*}(\emph{\text{QCG}}_{k})=\frac{1}{2}+\frac{1}{2k}.

(4)

Intuitively, this game cannot be perfectly won since, otherwise, it would be possible to have maximal entanglement between the referee and each of the parties, and this is not possible since entanglement is monogamous [19]. In the proof, see below, the key part is to show that the optimal winning probability is attainable by the actions of the players being independent of $x$ , intuitively, each party acts as if they were chosen to reproduce the maximally entangled state with the referee. In addition, in the proof, we show that the optimal value can be attained by preparing an initial state $\rho$ where, locally, each of the parties holds a qubit and no further actions taken by the players, i.e. their local actions are described by the identity channel $(\mathbb{I}_{P_{i}})$ . We then specify a strategy by providing a quantum state, since any local actions are independent of $x$ , they can be absorbed in the quantum state. More precisely, the optimal winning probability for the $\text{QCG}_{k}$ can be attained by the strategy given by the (pure) quantum state

|\varphi\rangle=\sqrt{\frac{2}{k(k+1)}}\sum_{x\in[k]}|\Phi^{+}\rangle_{RP_{x}}% |0\rangle_{P_{0}\ldots\not{P}_{x}\ldots P_{k-1}}.

(5)

Note that other natural multi-party entangled states that have been widely studied in the literature, such as the GHZ state ([26]) $|GHZ\rangle=\frac{1}{\sqrt{2}}(|000\rangle+|111\rangle)$ and the W state ([23]) $|W\rangle=\frac{1}{\sqrt{3}}(|001\rangle+|010\rangle+|100\rangle)$ , and their respective generalizations to arbitrary dimensions, as well as the strategy of “guessing” which party has to reproduce the quantum state, e.g. guessing $x=0$ , given by preparing the state $|\Phi^{+}\rangle_{VP_{0}}|0\rangle_{P_{1}}\ldots|0\rangle_{k-1}$ , provide significantly suboptimal winning probabilities. For 2-players, $\omega^{*}(\text{QCG}_{2})=\frac{3}{4}$ , and

\omega^{*}(\text{QCG}_{k})\xrightarrow[]{k\rightarrow\infty}\frac{1}{2},

(6)

which converges to the value attained by the strategy given by preparing the state ${|0\rangle_{R}|0\rangle_{P_{0}}\ldots|0\rangle_{P_{k-1}}}$ , showing that when $k$ increases even unentangled states allow for a near-optimal winning probability.

Proof.

A strategy ${S}$ for the QCG_k is described by a quantum state $\rho\in\mathcal{S}(\mathcal{H}_{R}\otimes\mathcal{H}_{P_{0}E_{0}}\otimes\ldots% \otimes\mathcal{H}_{P_{k-1}E_{k-1}})$ , where, for $i\in[k]$ , registers $P_{i}$ are of the same dimension as $\mathcal{H}_{R}$ and $E_{i}$ are auxiliary systems of arbitrary dimension that each party possesses, and unitary transformations $U=\{U^{x}_{P_{i}E_{i}}\}_{x}$ , acting on the registers in the subscripts (due to the Stinespring dilation of the quantum channels, we restrict our attention to unitary transformations $U^{x}_{P_{i}E_{i}}$ instead of quantum channels $\mathcal{E}^{x}_{P_{i}E_{i}\rightarrow P_{i}}$ ). Let $d$ be the dimension of the above (total) Hilbert space, which we denote by $\mathcal{H}_{d}$ . Then, the winning probability of the QCG_k, given the strategy $S$ on a $d$ -dimensional Hilbert space, is provided by

\begin{split}&\omega(\text{QCG}_{k},S,d)\\ &=\frac{1}{k}\sum_{x\in[k]}\mathrm{Tr}\left[\bigg(|\Phi^{+}\rangle\langle\Phi^% {+}|_{RP_{x}}\otimes\mathbb{I}_{E_{x}}\bigotimes_{i\neq x\in[k]}\mathbb{I}_{P_% {i}E_{i}}\bigg)\Bigg(\bigg(\mathbb{I}_{R}\otimes U^{x}_{P_{i}E_{i}}\otimes% \ldots\otimes U^{x}_{P_{i}E_{i}}\bigg)\rho\left(\mathbb{I}_{R}\otimes U^{x}_{P% _{i}E_{i}}\otimes\ldots\otimes U^{x}_{P_{i}E_{i}}\right)^{\dagger}\Bigg)\right% ]\\ &=\frac{1}{k}\sum_{x\in[k]}\mathrm{Tr}\left[\bigg(\mathbb{I}_{R}\otimes U^{x% \dagger}_{P_{i}E_{i}}\otimes\ldots\otimes U^{x\dagger}_{P_{i}E_{i}}\big)\bigg(% |\Phi^{+}\rangle\langle\Phi^{+}|_{RP_{x}}\otimes\mathbb{I}_{E_{x}}\bigotimes_{% i\neq x\in[k]}\mathbb{I}_{P_{i}E_{i}}\bigg)\left(\mathbb{I}_{R}\otimes U^{x}_{% P_{i}E_{i}}\otimes\ldots\otimes U^{x}_{P_{i}E_{i}}\right)\rho\right],\end{split}

where in the last equation we used cyclicity of the trace. For a specific choice of unitary transformations ${U=\{U^{x}_{P_{i}E_{i}}\}_{x}}$ , the optimal winning probability is given by

\begin{split}&\omega^{*}(\text{QCG}_{k},U,d)\\ &=\sup_{\rho\in\mathcal{S}(\mathcal{H}_{d})}\frac{1}{k}\sum_{x\in[k]}\mathrm{% Tr}\left[\big(\mathbb{I}_{R}\otimes U^{x\dagger}_{P_{i}E_{i}}\otimes\ldots% \otimes U^{x\dagger}_{P_{i}E_{i}}\big)\bigg(|\Phi^{+}\rangle\langle\Phi^{+}|_{% RP_{x}}\otimes\mathbb{I}_{E_{x}}\bigotimes_{i\neq x\in[k]}\mathbb{I}_{P_{i}E_{% i}}\bigg)\left(\mathbb{I}_{R}\otimes U^{x}_{P_{i}E_{i}}\otimes\ldots\otimes U^% {x}_{P_{i}E_{i}}\right)\rho\right]\\ &=\frac{1}{k}\|\sum_{x\in[k]}\left(\mathbb{I}_{R}\otimes U^{x\dagger}_{P_{i}E_% {i}}\otimes\ldots\otimes U^{x\dagger}_{P_{i}E_{i}}\right)\left(|\Phi^{+}% \rangle\langle\Phi^{+}|_{RP_{x}}\otimes\mathbb{I}_{E_{x}}\bigotimes_{i\neq x% \in[k]}\mathbb{I}_{P_{i}E_{i}}\right)\left(\mathbb{I}_{R}\otimes U^{x}_{P_{i}E% _{i}}\otimes\ldots\otimes U^{x}_{P_{i}E_{i}}\right)\|\\ &=\frac{1}{k}\|\sum_{x\in[k]}\bigg(\left(\mathbb{I}_{R}\otimes U^{x\dagger}_{P% _{x}E_{x}}\right)\left(|\Phi^{+}\rangle\langle\Phi^{+}|_{RP_{x}}\otimes\mathbb% {I}_{E_{x}}\right)\left(\mathbb{I}_{R}\otimes U^{x}_{P_{x}E_{x}}\right)\bigg)% \bigotimes_{i\neq x\in[k]}U^{x\dagger}_{P_{i}E_{i}}\bigotimes_{i\neq x\in[k]}% \mathbb{I}_{P_{i}E_{i}}\bigotimes_{i\neq x\in[k]}U^{x}_{P_{i}E_{i}}\|\\ &=\frac{1}{k}\|\sum_{x\in[k]}\bigg(\left(\mathbb{I}_{R}\otimes U^{x\dagger}_{P% _{x}E_{x}}\right)\left(|\Phi^{+}\rangle\langle\Phi^{+}|_{RP_{x}}\otimes\mathbb% {I}_{E_{x}}\right)\left(\mathbb{I}_{R}\otimes U^{x}_{P_{x}E_{x}}\right)\bigg)% \bigotimes_{i\neq x\in[k]}U^{x\dagger}_{P_{i}E_{i}}U^{x}_{P_{i}E_{i}}\|,\end{split}

Notice that, since $\{U^{x}_{P_{i}E_{i}}\}_{x}$ are unitary matrices, $U^{x\dagger}_{P_{i}E_{i}}U^{x}_{P_{i}E_{i}}=\mathbb{I}_{P_{i}E_{i}}$ , moreover,
$\mathbb{I}_{P_{i}E_{i}}=U^{i\dagger}_{P_{i}E_{i}}U^{i}_{P_{i}E_{i}}$ , then we can use $U^{x\dagger}_{P_{i}E_{i}}U^{x}_{P_{i}E_{i}}=U^{i\dagger}_{P_{i}E_{i}}U^{i}_{P_% {i}E_{i}}$ , and therefore

\begin{split}\omega^{*}&(\text{QCG}_{k},U,d)\\ &=\frac{1}{k}\|\sum_{x\in[k]}\bigg(\left(\mathbb{I}_{R}\otimes U^{x\dagger}_{P% _{x}E_{x}}\right)\left(|\Phi^{+}\rangle\langle\Phi^{+}|_{RP_{x}}\otimes\mathbb% {I}_{E_{x}}\right)\left(\mathbb{I}_{R}\otimes U^{x\dagger}_{P_{x}E_{x}}\right)% \bigg)\bigotimes_{i\neq x\in[k]}U^{i\dagger}_{P_{i}E_{i}}U^{i}_{P_{i}E_{i}}\|% \\ &=\frac{1}{k}\|\sum_{x\in[k]}\left(\mathbb{I}_{R}\bigotimes_{i\neq\in[k]}U^{i% \dagger}_{P_{i}E_{i}}\right)\left(|\Phi^{+}\rangle\langle\Phi^{+}|_{RP_{x}}% \otimes\mathbb{I}_{E_{x}}\bigotimes_{i\neq x\in[k]}\mathbb{I}_{P_{i}E_{i}}% \right)\left(\mathbb{I}_{R}\bigotimes_{i\in[k]}U^{i}_{P_{i}E_{i}}\right)\|\\ &=\frac{1}{k}\|\left(\mathbb{I}_{R}\bigotimes_{i\neq\in[k]}U^{i\dagger}_{P_{i}% E_{i}}\right)\left(\sum_{x\in[k]}|\Phi^{+}\rangle\langle\Phi^{+}|_{RP_{x}}% \otimes\mathbb{I}_{E_{x}}\bigotimes_{i\neq x\in[k]}\mathbb{I}_{P_{i}E_{i}}% \right)\left(\mathbb{I}_{R}\bigotimes_{i\in[k]}U^{i}_{P_{i}E_{i}}\right)\|\\ &=\frac{1}{k}\|\sum_{x\in[k]}|\Phi^{+}\rangle\langle\Phi^{+}|_{RP_{x}}\otimes% \mathbb{I}_{E_{x}}\bigotimes_{i\neq x\in[k]}\mathbb{I}_{P_{i}E_{i}}\|\\ &=\sup_{\rho\in\mathcal{S}(\mathcal{H}_{d})}\frac{1}{k}\sum_{x\in[k]}\mathrm{% Tr}\left[\left(|\Phi^{+}\rangle\langle\Phi^{+}|_{RP_{x}}\otimes\mathbb{I}_{E_{% x}}\bigotimes_{i\neq x\in[k]}\mathbb{I}_{P_{i}E_{i}}\right)\rho\right]=\omega^% {*}(\text{QCG}_{k},d)\end{split}

(7)

where in the fourth equality we used that the Schatten $\infty$ -norm is unitarily invariant, i.e. $\|V*W\|=\|*\|$ for unitary matrices $V$ and $W$ , and $\omega^{*}(\text{QCG}_{k},d)$ denotes the optimal winning probability if the dimension of the total initial Hilbert space is $d$ . Equation (7) shows that, given a Hilbert space $\mathcal{H}_{R}\otimes\mathcal{H}_{P_{0}E_{0}}\otimes\ldots\otimes\mathcal{H}_% {P_{k-1}E_{k-1}}$ , the optimal winning probability can be attained by an optimal quantum state independently of the actions of the players after knowing $x$ , i.e. the optimal winning probability is independent of $\{U^{x}_{P_{i}E_{i}}\}_{x}$ and they can apply $\{\mathbb{I}^{x}_{P_{i}E_{i}}\}_{x}$ . We are going to see that, actually, the optimal winning probability can be attained by each of the parties possessing a qubit (2-dimensional Hilbert space), i.e. by the total Hilbert space being $\mathcal{H}_{2^{k}}=\bigotimes_{i\in[k]}\mathbb{C}^{2}$ . From (7),

\begin{split}\omega^{*}(\text{QCG}_{k})&=\sup_{d\in\mathbb{N}}\omega^{*}(\text% {QCG}_{k},d)=\sup_{d\in\mathbb{N}}\frac{1}{k}\|\left(\sum_{x\in[k]}|\Phi^{+}% \rangle\langle\Phi^{+}|_{RP_{x}}\otimes\mathbb{I}_{P_{0}\ldots\not{P}_{x}% \ldots P_{k-1}}\right)\bigotimes_{i\in[k]}\mathbb{I}_{E_{i}}\|\\ &=\sup_{d\in\mathbb{N}}\frac{1}{k}\|\sum_{x\in[k]}|\Phi^{+}\rangle\langle\Phi^% {+}|_{RP_{x}}\otimes\mathbb{I}_{P_{0}\ldots\not{P}_{x}\ldots P_{k-1}}\|\|% \bigotimes_{i\in[k]}\mathbb{I}_{E_{i}}\|\\ &=\sup_{d\in\mathbb{N}}\frac{1}{k}\|\sum_{x\in[k]}|\Phi^{+}\rangle\langle\Phi^% {+}|_{RP_{x}}\otimes\mathbb{I}_{P_{0}\ldots\not{P}_{x}\ldots P_{k-1}}\|\\ &=\sup_{\rho\in\mathcal{S}\left(\mathcal{H}_{2^{k}}\right)}\frac{1}{k}\sum_{x% \in[k]}\mathrm{Tr}\left[\left(|\Phi^{+}\rangle\langle\Phi^{+}|_{RP_{x}}\otimes% \mathbb{I}_{P_{0}\ldots\not{P}_{x}\ldots P_{k-1}}\right)\rho\right],\end{split}

(8)

where, in the arguments of the supremums, the dependence on $d$ is implicit in the auxiliary spaces, which, together with the registers $P_{i}$ and $V$ , fully describe the total Hilbert space, and thus its dimension.

In order to provide the explicit value for the optimal winning probability, we have that, from (8),

\omega^{*}(\text{QCG}_{k})=\frac{1}{k}\|\sum_{x\in[k]}|\Phi^{+}\rangle\langle% \Phi^{+}|_{RP_{x}}\otimes\mathbb{I}_{P_{0}\ldots\not{P}_{x}\ldots P_{k-1}}\|=% \frac{1}{2}+\frac{1}{2k},

(9)

where the last equation is obtained by direct computation. $\hfill\blacktriangleleft$

3.1 Quantum cloning game with any target state

The concept of QCG_k can be generalized to the case where, instead of the parties having to reproduce EPR pairs with the referee, the state that has to be reproduced is an arbitrary-fixed state, i.e. the referee’s Hilbert space $\mathcal{H}_{R}$ is now of arbitrary dimension, and on input $x$ the party $P_{x}$ has to generate a given state $|\Psi\rangle_{RP_{x}}$ . Here, the dimension of the registers $P_{i}$ is the same for all $i\in[k]$ . We will refer to such a game as a $k$ -party quantum cloning game with target state $|\Psi\rangle$ , in short denoted by $\Psi$ -QCG_k, see Figure 1. Notice that this game becomes trivial if the target state $|\Psi\rangle_{RP}$ is a tensor product state. In the following theorem, we provide the optimal winning probability for any $\Psi$ -QCG_k for every number of parties $k$ and for any target state $|\Psi\rangle$ .

Theorem 7.

The optimal winning probability for every $\Psi$ -QCG_k is given by

\omega^{*}(\Psi\text{{-QCG}}_{k})=\frac{1}{k}\|\sum_{x\in[k]}|\Psi\rangle% \langle\Psi|_{RP_{x}}\otimes\mathbb{I}_{P_{0}\ldots\not{P}_{x}\ldots P_{k-1}}\|.

(10)

Along the lines of the proof of Theorem 6, the key idea relies on showing that the optimal winning probability can be attained by the actions of the players being independent on $x$ .

Proof.

The result follows from the proof of Theorem 6 by repeating the same steps, replacing $|\Phi^{+}\rangle_{VP_{x}}$ by $|\Psi\rangle_{VP_{x}}$ , and from (8), we obtain (10). $\hfill\blacktriangleleft$

4 Parallel repetition of QCG_k

A case of particular interest is given when $\text{QCG}_{k}$ is played $n$ times in parallel, denoted by $\text{QCG}_{k}^{\times n}$ . Specifically, we will analyze $\text{QCG}_{2}$ where now the two collaborative parties, who we rename as Alice and Bob, will receive $x=x_{0}\ldots x_{n-1}\in\{0,1\}^{n}$ . We denote by $R_{0}\ldots R_{n-1}$ , $A_{0}\ldots A_{n-1}$ and $B_{0}\ldots B_{n-1}$ the final (qubit) registers of the referee, Alice and Bob, respectively. The players win if at the end of the game Alice is able to create the maximally entangled state with the referee in all her registers such that $x_{i}=0$ , and analogously for Bob in all his registers such that $x_{i}=1$ . See Figure 2 for a schematic representation.

Figure 2: Schematic representation of the

n

-fold parallel repetition of the

2

-party quantum cloning game. The gray-shaded region represents the tripartie state

\rho

that Alice and Bob prepare.

Similarly as before, at the beginning of the game the three parties are allowed to share any arbitrary quantum state and, upon receiving the classical information, Alice and Bob can apply CPTP maps $\{\mathcal{E}^{x}_{A_{0}\ldots A_{n-1}E_{A}\rightarrow A_{0}\ldots A_{n-1}}\}_% {x}$ and $\{\mathcal{E}^{x}_{B_{0}\ldots B_{n-1}E_{B}\rightarrow B_{0}\ldots B_{n-1}}\}_% {x}$ , where $E_{A}$ and $E_{B}$ are arbitrary auxiliary systems that Alice and Bob possess, respectively.

In the following theorem, we state that the optimal winning probability decays exponentially with the number of parallel repetitions $n$ .

Theorem 8.

The optimal winning probability for $n$ parallel repetitions of the ${QCG}_{2}$ is such that

\left(\frac{3}{4}\right)^{n}\leq\omega^{*}(\emph{\text{QCG}}_{2}^{\times n})% \leq\left(\frac{1}{2}+\frac{1}{2\sqrt{2}}\right)^{n}.

(11)

The key idea of the proof relies on combining ideas used in the proof of Theorem 7 together with Proposition 4.3 in [35], which was also used in [38] to prove parallel repetition for monogamy-of-entanglement games.

Proof.

A strategy ${S}_{n}$ for the $n$ -parallel repetition of QCG₂ is described by a quantum state $\rho\in\mathcal{S}(\mathcal{H}_{R}\otimes\mathcal{H}_{A_{0}\ldots A_{n-1}E_{A}% }\otimes\mathcal{H}_{B_{0}\ldots B_{n-1}E_{B}})$ , where, for $i\in[n]$ , registers $A_{i}$ and $B_{i}$ are of the same dimension as $\mathcal{H}_{R}$ and $E_{A}$ and $E_{B}$ are auxiliary systems of arbitrary dimension that each party possess, and unitary transformations $\{U^{x}_{A_{0}\ldots A_{n-1}E_{A}}\}_{x}$ and $\{V^{x}_{B_{0}\ldots B_{n-1}E_{B}}\}_{x}$ , acting on the registers in the subscripts (due to the Stinespring dilation of the quantum channels, we restrict our attention to unitary transformations). For $x=x_{0}\ldots x_{n-1}\in\{0,1\}^{n}$ , let $Q_{x_{i}}=A_{i}$ if $x_{i}=0$ and $Q_{x_{i}}=B_{i}$ if $x_{i}=1$ , and we use the shorthand notation $R=R_{0}\ldots R_{n-1}$ , $A=A_{0}\ldots A_{n-1}$ and $B=B_{0}\ldots B_{n-1}$ . Then, the winning probability of this game, given the strategy $S_{n}$ , is provided by

\begin{split}&\omega({\text{QCG}}_{2}^{\times n},S_{n})\\ &=\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}\mathrm{Tr}\left[\bigg(\bigg(\bigotimes% _{i\in[n]}|\Phi^{+}\rangle\langle\Phi^{+}|_{R_{i}Q_{x_{i}}}\otimes\mathbb{I}_{% Q_{1-x_{i}}}\bigg)\otimes\mathbb{I}_{E_{A}E_{B}}\bigg)(\mathbb{I}_{R}\otimes U% ^{x}_{AE_{A}}\otimes V^{x}_{BE_{B}})\rho(\mathbb{I}_{R}\otimes U^{x}_{AE_{A}}% \otimes V^{x}_{BE_{B}})^{\dagger}\right]\\ &=\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}\mathrm{Tr}\left[(\mathbb{I}_{R}\otimes U% ^{x\dagger}_{AE_{A}}\otimes V^{x\dagger}_{BE_{B}})\bigg(\bigg(\bigotimes_{i\in% [n]}|\Phi^{+}\rangle\langle\Phi^{+}|_{R_{i}Q_{x_{i}}}\otimes\mathbb{I}_{Q_{1-x% _{i}}}\bigg)\otimes\mathbb{I}_{E_{A}E_{B}}\bigg)(\mathbb{I}_{R}\otimes U^{x}_{% AE_{A}}\otimes V^{x}_{BE_{B}})\rho\right]\\ &\leq\frac{1}{2^{n}}\|\sum_{x\in\{0,1\}^{n}}(\mathbb{I}_{R}\otimes U^{x\dagger% }_{AE_{A}}\otimes V^{x\dagger}_{BE_{B}})\left(\bigg(\bigotimes_{i\in[n]}|\Phi^% {+}\rangle\langle\Phi^{+}|_{R_{i}Q_{x_{i}}}\otimes\mathbb{I}_{Q_{1-x_{i}}}% \bigg)\otimes\mathbb{I}_{E_{A}E_{B}}\right)(\mathbb{I}_{R}\otimes U^{x}_{AE_{A% }}\otimes V^{x}_{BE_{B}})\|.\end{split}

Denote

M^{x}:=(\mathbb{I}_{R}\otimes U^{x\dagger}_{AE_{A}}\otimes V^{x\dagger}_{BE_{B% }})\left(\bigg(\bigotimes_{i\in[n]}|\Phi^{+}\rangle\langle\Phi^{+}|_{R_{i}Q_{x% _{i}}}\otimes\mathbb{I}_{Q_{1-x_{i}}}\bigg)\otimes\mathbb{I}_{E_{A}E_{B}}% \right)(\mathbb{I}_{R}\otimes U^{x}_{AE_{A}}\otimes V^{x}_{BE_{B}}),

(12)

then,

\omega({\text{QCG}}_{2}^{\times n},S_{n})\leq\frac{1}{2^{n}}\|\sum_{x\in\{0,1% \}^{n}}M^{x}\|\leq\frac{1}{2^{n}}\sum_{k\in[2^{n}]}\max_{x,x^{\prime}}\|M^{x}M% ^{x^{\prime}}\|,

(13)

where we used Lemma 2, and $x^{\prime}=\pi_{k}(x)$ , for $\{\pi_{k}\}_{k}$ being a set of mutually orthogonal permutations. Fix $x$ and $x^{\prime}$ , and let $\mathcal{T}$ be the set of indices where $x$ and $x^{\prime}$ differ, i.e. ${\mathcal{T}=\{i\mid x_{i}\neq x^{\prime}_{i}\}}$ , and let $t=\lvert\mathcal{T}\rvert$ . Let $\mathcal{T}_{A}=\{i\in\mathcal{T}\mid x_{i}=0\}$ , and $t_{A}:=\lvert\mathcal{T}_{A}\rvert$ , then we have that

\begin{split}&M^{x}\preceq M^{x}_{A}\\ &:=(\mathbb{I}_{R}\otimes U^{x\dagger}_{AE_{A}}\otimes V^{x\dagger}_{BE_{B}})% \\ &\qquad\bigg(\bigg(\bigotimes_{i\in\mathcal{T}_{A}}|\Phi^{+}\rangle\langle\Phi% ^{+}|_{R_{i}Q_{x_{i}}}\otimes\mathbb{I}_{Q_{1-x_{i}}}\bigg)\otimes\bigg(% \bigotimes_{i\in[n]\setminus\mathcal{T}_{A}}\mathbb{I}_{R_{i}Q_{x_{i}}Q_{1-x_{% i}}}\bigg)\otimes\mathbb{I}_{E_{A}E_{B}}\bigg)(\mathbb{I}_{R}\otimes U^{x}_{AE% _{A}}\otimes V^{x}_{BE_{B}})\\ &=(\mathbb{I}_{R}\otimes U^{x\dagger}_{AE_{A}}\otimes V^{x\dagger}_{BE_{B}})% \left(\bigg(\bigotimes_{i\in\mathcal{T}_{A}}|\Phi^{+}\rangle\langle\Phi^{+}|_{% R_{i}A_{i}}\bigotimes_{i\in[n]\setminus\mathcal{T}_{A}}\mathbb{I}_{R_{i}A_{i}E% _{A}}\right)\otimes\mathbb{I}_{BE_{B}}\bigg)(\mathbb{I}_{R}\otimes U^{x}_{AE_{% A}}\otimes V^{x}_{BE_{B}})\\ &=(\mathbb{I}_{R}\otimes U^{x\dagger}_{AE_{A}}\otimes V^{x^{\prime}\dagger}_{% BE_{B}})\left(\bigg(\bigotimes_{i\in\mathcal{T}_{A}}|\Phi^{+}\rangle\langle% \Phi^{+}|_{R_{i}A_{i}}\bigotimes_{i\in[n]\setminus\mathcal{T}_{A}}\mathbb{I}_{% R_{i}A_{i}E_{A}}\right)\otimes\mathbb{I}_{BE_{B}}\bigg)(\mathbb{I}_{R}\otimes U% ^{x}_{AE_{A}}\otimes V^{x^{\prime}}_{BE_{B}}),\end{split}

where in the last equality we used that $V^{x\dagger}_{BE_{B}}V^{x\dagger}_{BE_{B}}=\mathbb{I}_{BE_{B}}=V^{x^{\prime}% \dagger}_{BE_{B}}V^{x^{\prime}}_{BE_{B}}$ . Similarly,

\begin{split}&M^{x^{\prime}}\preceq M^{x^{\prime}}_{B}\\ &:=(\mathbb{I}_{R}\otimes U^{x^{\prime}\dagger}_{AE_{A}}\otimes V^{x^{\prime}% \dagger}_{BE_{B}})\\ &\qquad\bigg(\bigg(\bigotimes_{i\in\mathcal{T}_{A}}|\Phi^{+}\rangle\langle\Phi% ^{+}|_{R_{i}Q_{x^{\prime}_{i}}}\otimes\mathbb{I}_{Q_{1-x^{\prime}_{i}}}\bigg)% \otimes\bigg(\bigotimes_{i\in[n]\setminus\mathcal{T}_{A}}\mathbb{I}_{R_{i}Q_{x% ^{\prime}_{i}}Q_{1-x^{\prime}_{i}}}\bigg)\otimes\mathbb{I}_{E_{A}E_{B}}\bigg)(% \mathbb{I}_{R}\otimes U^{x^{\prime}}_{AE_{A}}\otimes V^{x^{\prime}}_{BE_{B}})% \\ &=(\mathbb{I}_{R}\otimes U^{x\dagger}_{AE_{A}}\otimes V^{x^{\prime}\dagger}_{% BE_{B}})\left(\bigg(\bigotimes_{i\in\mathcal{T}_{A}}|\Phi^{+}\rangle\langle% \Phi^{+}|_{R_{i}B_{i}}\bigotimes_{i\in[n]\setminus\mathcal{T}_{A}}\mathbb{I}_{% R_{i}B_{i}E_{B}}\right)\otimes\mathbb{I}_{AE_{A}}\bigg)(\mathbb{I}_{R}\otimes U% ^{x}_{AE_{A}}\otimes V^{x^{\prime}}_{BE_{B}}),\end{split}

(14)

By Lemma 4,

\|M^{x}M^{x^{\prime}}\|\leq\|M^{x}_{A}M^{x^{\prime}}_{B}\|,

(15)

then

\begin{split}&M^{x}_{A}M^{x^{\prime}}_{B}\\ &=(\mathbb{I}_{R}\otimes U^{x\dagger}_{AE_{A}}\otimes V^{x^{\prime}\dagger}_{% BE_{B}})\left(\bigg(\bigotimes_{i\in\mathcal{T}_{A}}|\Phi^{+}\rangle\langle% \Phi^{+}|_{R_{i}A_{i}}\bigotimes_{i\in[n]\setminus\mathcal{T}_{A}}\mathbb{I}_{% R_{i}A_{i}E_{A}}\right)\otimes\mathbb{I}_{BE_{B}}\bigg)(\mathbb{I}_{R}\otimes U% ^{x}_{AE_{A}}\otimes V^{x^{\prime}}_{BE_{B}})\\ &\cdot(\mathbb{I}_{R}\otimes U^{x\dagger}_{AE_{A}}\otimes V^{x^{\prime}\dagger% }_{BE_{B}})\left(\bigg(\bigotimes_{i\in\mathcal{T}_{A}}|\Phi^{+}\rangle\langle% \Phi^{+}|_{R_{i}B_{i}}\bigotimes_{i\in[n]\setminus\mathcal{T}_{A}}\mathbb{I}_{% R_{i}B_{i}E_{B}}\right)\otimes\mathbb{I}_{AE_{A}}\bigg)(\mathbb{I}_{R}\otimes U% ^{x}_{AE_{A}}\otimes V^{x^{\prime}}_{BE_{B}}).\end{split}

We have that $(\mathbb{I}_{R}\otimes U^{x}_{AE_{A}}\otimes V^{x^{\prime}}_{BE_{B}})(\mathbb{% I}_{R}\otimes U^{x\dagger}_{AE_{A}}\otimes V^{x^{\prime}\dagger}_{BE_{B}})=% \mathbb{I}_{RAEABE_{B}}$ , and, since the Schatten $\infty$ -norm is unitarily invariant,

\begin{split}&\|M^{x}_{A}M^{x^{\prime}}_{B}\|\\ &=\|\left(\bigotimes_{i\in\mathcal{T}_{A}}|\Phi^{+}\rangle\langle\Phi^{+}|_{R_% {i}A_{i}}\bigotimes_{i\in[n]\setminus\mathcal{T}_{A}}\mathbb{I}_{R_{i}A_{i}E_{% A}}\otimes\mathbb{I}_{BE_{B}}\right)\left(\bigotimes_{i\in\mathcal{T}_{A}}|% \Phi^{+}\rangle\langle\Phi^{+}|_{R_{i}B_{i}}\bigotimes_{i\in[n]\setminus% \mathcal{T}_{A}}\mathbb{I}_{R_{i}B_{i}E_{B}}\otimes\mathbb{I}_{AE_{A}}\right)% \|\\ &=\|\left(\bigotimes_{i\in\mathcal{T}_{A}}\big(|\Phi^{+}\rangle\langle\Phi^{+}% |_{R_{i}A_{i}}\otimes\mathbb{I}_{B_{i}}\big)\big(|\Phi^{+}\rangle\langle\Phi^{% +}|_{R_{i}B_{i}}\otimes\mathbb{I}_{A_{i}}\big)\right)\bigotimes_{i\in[n]% \setminus\mathcal{T}_{A}}\mathbb{I}_{R_{i}A_{i}B_{i}}\otimes\mathbb{I}_{E_{A}E% _{B}}\|\\ &=\|\bigotimes_{i\in\mathcal{T}_{A}}\big(|\Phi^{+}\rangle\langle\Phi^{+}|_{R_{% i}A_{i}}\otimes\mathbb{I}_{B_{i}}\big)\big(|\Phi^{+}\rangle\langle\Phi^{+}|_{R% _{i}B_{i}}\otimes\mathbb{I}_{A_{i}}\big)\|\|\bigotimes_{i\in[n]\setminus% \mathcal{T}_{A}}\mathbb{I}_{R_{i}A_{i}B_{i}}\otimes\mathbb{I}_{E_{A}E_{B}}\|\\ &=\prod_{i\in\mathcal{T}_{A}}\|\big(|\Phi^{+}\rangle\langle\Phi^{+}|_{R_{i}A_{% i}}\otimes\mathbb{I}_{B_{i}}\big)\big(|\Phi^{+}\rangle\langle\Phi^{+}|_{R_{i}B% _{i}}\otimes\mathbb{I}_{A_{i}}\big)\|\\ &=2^{-t_{A}},\end{split}

(16)

where we used that, for every $i$ ,

\|\big(|\Phi^{+}\rangle\langle\Phi^{+}|_{R_{i}A_{i}}\otimes\mathbb{I}_{B_{i}}% \big)\big(|\Phi^{+}\rangle\langle\Phi^{+}|_{R_{i}B_{i}}\otimes\mathbb{I}_{A_{i% }}\big)\|=2^{-1}.

(17)

Without loss of generality, assume $t_{A}\geq t/2$ , then, combining (15) and (16), we have that

\|M^{x}M^{x^{\prime}}\|\leq\|M^{x}_{A}M^{x^{\prime}}_{B}\|\leq 2^{-\frac{t}{2}}.

(18)

In order to apply the bound in Lemma 4, consider the set of permutations given by $\pi_{k}(x)=x\oplus k$ , where $x,k\in\{0,1\}^{n}$ (they are such that they have the same Hamming distance). There are $\binom{n}{i}$ permutations with Hamming distance $i$ . Then, we have

\omega({\text{QCG}}_{2}^{\times n},S_{n})\leq\frac{1}{2^{n}}\sum_{k\in[2^{n}]}% \max_{x,x^{\prime}}\|M^{x}M^{x^{\prime}}\|\leq\frac{1}{2^{n}}\sum_{t=0}^{n}% \binom{n}{t}2^{-\frac{t}{2}}=\left(\frac{1}{2}+\frac{1}{2\sqrt{2}}\right)^{n}.

(19)

$\hfill\blacktriangleleft$

5 Application to QPV in the No-PE and BE(m) models

In this section, we analyze the security of the routing QPV protocol, originally introduced in [28]. A round of this protocol, see Figure 3 for a schematic representation, is described as follows:

1.

The verifier V₀ selects a qubit ${|\phi\rangle\in\{|0\rangle,|1\rangle,|+\rangle,|-\rangle\}}$ , and the verifier V₁ selects $x\in\{0,1\}$ , both picked uniformly at random. They send $|\phi\rangle$ and $x$ (at time $t=0$ ) so that they arrive at the same time ( $t=1$ ) at $p o s$ .
2.

Upon receiving the information sent by V₀ and V₁, the prover sends the qubit $|\phi\rangle$ to the verifier V_x.
3.

If $|\phi\rangle$ arrives at the time consistent with $p o s$ ( $t=2)$ , and a projective measurement performed by V_x on the state sent by V₀ leads to the correct outcome, the verifiers accept. Otherwise, they reject.

Figure 3: Schematic representation of the

(H,n)

-routing QPV protocol. If

r_{0}

is an empty bit string, and

x=r_{1}

, this figure represents the

n

-parallel repetition of the routing QPV protocol. The time arrow is represented by

t

.

The most general attack to the routing protocol, pictured in Figure 4, consists of having two attackers Alice ( $\mathsf{A}$ ) and Bob ( $\mathsf{B}$ ), located between $\mathsf{V}_{0}$ and $P$ , and between $P$ and $\mathsf{V}_{0}$ , respectively. Before $t=0$ , the attackers agree on a strategy and might prepare an entangled state. After $t=0$ , Alice ( $\mathsf{A}_{0}$ ) and Bob ( $\mathsf{B}_{0}$ ) intercept the information sent from their closest verifier, respectively. Due to timing constraints, they are allowed to perform one round of simultaneous communication. After communicating (after $t=1$ ), Alice ( $\mathsf{A}_{1}$ ) and Bob ( $\mathsf{B}_{1}$ ) answer to their closest verifier, respectively.

Here, we analyze security within three attack models: (i) the No Pre-shared Entanglement (No-PE) model [13], where adversaries do not (pre-)share any entanglement before the protocol’s execution; (ii) the Bounded-Entanglement BE $(m)$ model, where adversaries pre-share at most $m$ entangled qubits; and (iii) the Random Oracle Model (ROM), where attackers (pre-)share any amount of entanglement before the protocol’s execution. We formalize the concept of security, given an attack model $\mathcal{M}$ , as follows:

Definition 9.

The routing protocol is said to be $\alpha$ -sound in the $\mathcal{M}$ model if, for any attackers acting according to such an attack model, the verifiers accept with probability at most $\alpha$ .

Figure 4: Schematic representation of a generic attack to the

(H,n)

-routing protocol (and in particular, to the routing protocol).

The security of a variation of this protocol, the $f$ -routing QPV protocol, where the classical information $x$ is split into two bit strings, each sent from each verifier, and the qubit has to be routed according to the outcome of a boolean function $f$ on those bit strings has been studied in the BE $(m)$ model [11, 6, 7]. The authors of these works showed that the $f$ -routing QPV protocol remains secure as long as $m$ is at most linear in the size of the bit strings. However, unlike other protocols [13, 38, 4] the security of the routing QPV protocol in the No-PE model was never analyzed. The No-PE assumption is necessary to obtain non-trivial bounds, since there is a perfect attack if the attackers pre-share entanglement [28]. We show security in the No-PE model, providing the tight result, summarized in the following proposition:

Proposition 10.

In the No-PE model, the routing QPV protocol is $\frac{3}{4}$ -sound. Moreover, this is optimal.

The intuition behind Proposition 10 relies on the fact that the most general attack can be reduced to a QCG₂. Consider the purified version of the routing protocol, which is equivalent to the original version, and where the only difference relies on V₀, instead of sending the qubit $|\phi\rangle$ , prepares the state $|\Phi^{+}\rangle$ and keeps a register for herself and sends the other register to the prover. Then, as seen in Figure 4, the most general attack to the routing QPV protocol is to place an adversary between V₀ and the prover, Alice, and another adversary between the prover and V₁, Bob. In the No-PE model, we can simplify it further, as Alice intercepts the qubit sent by V₀, applies an arbitrary quantum operation to it, and possibly some ancillary systems she possesses. She keeps a part of it and sends the other to Bob. On the other side, Bob intercepts $x$ , copies it and sends the copy to Alice. Since they share no entanglement, any quantum operation that Bob could perform as a function of $x$ can be included in Alice’s operation. After one-round of simultaneous communication, Alice and Bob share a tripartite state with V₀, and their task is that the party designated by $x$ has to end up with a maximally entangled state with the V₀. By Theorem 7, even if Alice and Bob can share any state with the referee (in this case V₀), they can succeed with at most probability $\frac{3}{4}$ .

On the other hand, to show optimality, consider the attack where (i) at the beginning of the protocol Alice prepares the 3-qubit state ${\frac{1}{\sqrt{3}}(|\Phi^{+}\rangle_{A_{0}A}|0\rangle_{B}+|\Phi^{+}\rangle_{A% _{0}B}|0\rangle_{A})}$ , (ii) intercepts $|\phi\rangle$ and performs a Bell measurement on the intercepted state and her register $A_{0}$ , immediately she applies the teleportation corrections to both of her registers $A$ and $B$ , (iii) she keeps register $A$ and sends register $B$ to Bob, (iv) in the meantime, Bob intercepts and broadcasts $x$ , after receiving the information from their fellow attacker, if $x=0$ , Alice sends her register ( $A$ ) to V₀, whereas if $x=1$ , Bob sends his register ( $B$ ) to V₁. This attack has a winning probability of $\frac{3}{4}$ .

An analogous reduction applies when the routing QPV protocol is executed $n$ times in parallel, and therefore, its security can be reduced to the $n$ -parallel repetition of QCG₂:

Proposition 11.

In the No-PE model, the routing QPV protocol executed $n$ times in parallel is ${(\frac{1}{2}+\frac{1}{2\sqrt{2}})^{n}}$ -sound.

A direct consequence of Lemma 5.3 in [8] implies, similarly as in [38], security for the routing protocol executed in parallel for attackers who pre-share a linear amount of qubits:

Corollary 12.

In the $BE(m)$ model, the routing QPV protocol executed $n$ times in parallel is $\left(2^{m}(\frac{1}{2}+\frac{1}{2\sqrt{2}})^{n}\right)$ -sound.

In particular, the above soundness is exponentially small in $n$ if $m<n\log\left((\frac{1}{2}+\frac{1}{2\sqrt{2}})^{-1}\right)\simeq 0.228n$ .

6 Application to QPV in the random oracle model

Consider the $n$ -parallel repetition of the routing QPV protocol but instead of V₁ sending $x\in\{0,1\}^{n}$ , V₀ and V₁ send $r_{0},r_{1}\in\{0,1\}^{\ell}$ , for $\ell\in\mathbb{N}$ , to the prover, respectively. Then, the $x$ used in the rest of the protocol is computed via $x=H(r_{0}\oplus r_{1})$ , for a given hash function $H:\{0,1\}^{\ell}\rightarrow\{0,1\}^{n}$ . We will denote this variation as $(H,n)$ -routing QPV protocol, see Figure 3 for a schematic representation.

To provide security in the quantum random oracle model against adversaries sharing an arbitrary amount of entanglement, we use some techniques introduced in [40]. A quantum random oracle is defined as a fixed function $H\colon\{0,1\}^{\ell}\to\{0,1\}^{n}$ that is sampled uniformly at random from the set of functions from $\ell$ bits to $n$ bits¹¹1This can be done by simply sampling a large table $T$ of size $2^{\ell}$ , and outputting $T[r]$ when queried on input $r$ . Note that this sampling procedure is not efficient: while having an efficient oracle [42] is sometimes required, for instance when working with composable security and computationally bounded distinguishers, or when reducing to problems that are hard only for bounded adversaries, in our case we do not need this additional property since we do a reduction to a problem that is hard even for unbounded adversaries.. The parties are not given the full description of $H$ directly, but they are given oracle access to $H$ , in the sense that they have access to a special gate implementing the unitary $U_{H}\colon|r\rangle|b\rangle\to|r\rangle|b\oplus H(r)\rangle$ . We denote the number of queries made by the adversary by $q$ . As a proof technique, an oracle can also be reprogrammed, where security of the protocol is shown by first studying a variant where the gate applied by the oracle may change over time. A typical setting is where we change a single entry of the oracle: we denote by $H[r\mapsto x]$ the new oracle that behaves like $H$ except that $H(r)=x$ . The chances of distinguishing whether $H$ has been reprogrammed or not can be bounded using [40], which informally states that if we can distinguish whether the oracle has been reprogrammed or no, then we have queried it on $r$ before it has been reprogrammed (for completeness, see Lemma 14). In the following theorem, we show security of the $(H,n)$ -routing protocol in the ROM.

Theorem 13.

If the (possibly entangled) attackers Alice and Bob perform at most $q$ queries to the (quantum) random oracle $H$ , the $(H,n)$ -routing QPV protocol is $\epsilon$ -sound, with

\epsilon=2q2^{-\frac{\ell}{2}}+\left(\frac{1}{2}+\frac{1}{2\sqrt{2}}\right)^{n}.

(20)

In particular, $\epsilon$ is negligible if $q$ and $\ell$ scale polynomially with $n$ .

The starting idea of the proof follows [40], where we send Bell pairs instead of single qubits in order to make the input state independent of $x$ , the output of the oracle. Then we reprogram this oracle after adversaries share their state to ensure $x$ is truly random and independent of the state shared by malicious parties at time $t=1$ . Finally, we realize that we can rewrite this into an instance of Theorem 8. In the proof of Theorem 13, we will rely on this lemma by Unruh:

Lemma 14 ([40, Lemma 3]).

Let $(\mathcal{A}_{1},\mathcal{A}_{2})$ be oracle algorithms sharing state between invocations that perform at most $q$ queries to $H$ . Let $C$ be an oracle algorithm that on input $(j,r)$ does the following: Run $\mathcal{A}_{1}^{H}(r)$ until the $j$ -th query to $H$ , then measure the argument of that query in the computational basis, and output the measurement outcome (or $\bot$ if no $j$ -th query occurs). Let:

$\displaystyle P_{\mathcal{A}}^{1}$	$\displaystyle\coloneqq\Pr_{\begin{subarray}{c}H\mathrel{\mathchoice{\ooalign{% \hskip 0.0pt\raisebox{0.7pt}{$\scriptstyle\mathdollar$}\hskip 0.0pt\cr$% \displaystyle\leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$% \scriptstyle\mathdollar$}\hskip 0.0pt\cr$\textstyle\leftarrow$\cr}}{\ooalign{% \hskip 0.0pt\raisebox{0.7pt}{$\scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$% \scriptstyle\leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$% \scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$\scriptscriptstyle\leftarrow$% \cr}}}(\{0,1\}^{\ell}\to\{0,1\}^{n})\\ r\mathrel{\mathchoice{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$\scriptstyle% \mathdollar$}\hskip 0.0pt\cr$\displaystyle\leftarrow$\cr}}{\ooalign{\hskip 0.0% pt\raisebox{0.7pt}{$\scriptstyle\mathdollar$}\hskip 0.0pt\cr$\textstyle% \leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$\scriptscriptstyle% \mathdollar$}\hskip 0.0pt\cr$\scriptstyle\leftarrow$\cr}}{\ooalign{\hskip 0.0% pt\raisebox{0.7pt}{$\scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$% \scriptscriptstyle\leftarrow$\cr}}}\{0,1\}^{l},\mathcal{A}_{1}^{H}(r)\\ b^{\prime}\rightarrow\mathcal{A}_{2}^{H}(r,H(r))\end{subarray}}\left[\,b^{% \prime}=\mathsf{Accept}\,\right],$	(21)
$\displaystyle P_{\mathcal{A}}^{2}$	$\displaystyle\coloneqq\Pr_{\begin{subarray}{c}H\mathrel{\mathchoice{\ooalign{% \hskip 0.0pt\raisebox{0.7pt}{$\scriptstyle\mathdollar$}\hskip 0.0pt\cr$% \displaystyle\leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$% \scriptstyle\mathdollar$}\hskip 0.0pt\cr$\textstyle\leftarrow$\cr}}{\ooalign{% \hskip 0.0pt\raisebox{0.7pt}{$\scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$% \scriptstyle\leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$% \scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$\scriptscriptstyle\leftarrow$% \cr}}}(\{0,1\}^{\ell}\to\{0,1\}^{n})\\ r\mathrel{\mathchoice{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$\scriptstyle% \mathdollar$}\hskip 0.0pt\cr$\displaystyle\leftarrow$\cr}}{\ooalign{\hskip 0.0% pt\raisebox{0.7pt}{$\scriptstyle\mathdollar$}\hskip 0.0pt\cr$\textstyle% \leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$\scriptscriptstyle% \mathdollar$}\hskip 0.0pt\cr$\scriptstyle\leftarrow$\cr}}{\ooalign{\hskip 0.0% pt\raisebox{0.7pt}{$\scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$% \scriptscriptstyle\leftarrow$\cr}}}\{0,1\}^{l},x\mathrel{\mathchoice{\ooalign{% \hskip 0.0pt\raisebox{0.7pt}{$\scriptstyle\mathdollar$}\hskip 0.0pt\cr$% \displaystyle\leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$% \scriptstyle\mathdollar$}\hskip 0.0pt\cr$\textstyle\leftarrow$\cr}}{\ooalign{% \hskip 0.0pt\raisebox{0.7pt}{$\scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$% \scriptstyle\leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$% \scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$\scriptscriptstyle\leftarrow$% \cr}}}\{0,1\}^{n}\\ H^{\prime}\coloneqq H[r\mapsto x],\mathcal{A}_{1}^{H}(r)\\ b^{\prime}\rightarrow\mathcal{A}_{2}^{H^{\prime}}(r,x)\end{subarray}}\left[\,b% ^{\prime}=\mathsf{Accept}\,\right],$	(22)
$\displaystyle P_{C}$	$\displaystyle\coloneqq\Pr_{\begin{subarray}{c}H\mathrel{\mathchoice{\ooalign{% \hskip 0.0pt\raisebox{0.7pt}{$\scriptstyle\mathdollar$}\hskip 0.0pt\cr$% \displaystyle\leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$% \scriptstyle\mathdollar$}\hskip 0.0pt\cr$\textstyle\leftarrow$\cr}}{\ooalign{% \hskip 0.0pt\raisebox{0.7pt}{$\scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$% \scriptstyle\leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$% \scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$\scriptscriptstyle\leftarrow$% \cr}}}(\{0,1\}^{\ell}\to\{0,1\}^{n})\\ r\mathrel{\mathchoice{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$\scriptstyle% \mathdollar$}\hskip 0.0pt\cr$\displaystyle\leftarrow$\cr}}{\ooalign{\hskip 0.0% pt\raisebox{0.7pt}{$\scriptstyle\mathdollar$}\hskip 0.0pt\cr$\textstyle% \leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$\scriptscriptstyle% \mathdollar$}\hskip 0.0pt\cr$\scriptstyle\leftarrow$\cr}}{\ooalign{\hskip 0.0% pt\raisebox{0.7pt}{$\scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$% \scriptscriptstyle\leftarrow$\cr}}}\{0,1\}^{l},j\mathrel{\mathchoice{\ooalign{% \hskip 0.0pt\raisebox{0.7pt}{$\scriptstyle\mathdollar$}\hskip 0.0pt\cr$% \displaystyle\leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$% \scriptstyle\mathdollar$}\hskip 0.0pt\cr$\textstyle\leftarrow$\cr}}{\ooalign{% \hskip 0.0pt\raisebox{0.7pt}{$\scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$% \scriptstyle\leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$% \scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$\scriptscriptstyle\leftarrow$% \cr}}}\{1,\dots,q\}\\ x^{\prime}\rightarrow C^{H}(j,x)\end{subarray}}\left[\,x=x^{\prime}\,\right].$	(23)

Then, $|P_{\mathcal{A}}^{1}-P_{\mathcal{A}}^{2}|\leq 2q\sqrt{P_{C}}$ .

Proof (of Theorem 13).

To prove this theorem, we must show that the probability that the verifiers accept in a malicious run of the protocol is lower bounded by $\epsilon$ , i.e., if we denote by $\mathsf{V}_{0}\kern-2.0pt\leftrightsquigarrow\kern-2.0pt\mathsf{A}\kern-2.0pt% \leftrightsquigarrow\kern-2.0pt\mathsf{B}\kern-2.0pt\leftrightsquigarrow\kern-% 2.0pt\mathsf{V}_{1}$ the output of the verifiers ( $\mathsf{Accept}$ or $\mathsf{Reject}$ ) at the end of a protocol involving a malicious Alice $\mathsf{A}$ and a malicious Bob $\mathsf{B}$ , we want to show that

\displaystyle\Pr\left[\,\mathsf{V}_{0}\kern-2.0pt\leftrightsquigarrow\kern-2.0% pt\mathsf{A}\kern-2.0pt\leftrightsquigarrow\kern-2.0pt\mathsf{B}\kern-2.0pt% \leftrightsquigarrow\kern-2.0pt\mathsf{V}_{1}=\mathsf{Accept}\,\right]\leq\epsilon.

(24)

We prove this by defining a series of games, where the probability of accepting each game is close to the probability of accepting the next game. By ensuring that the first game corresponds to the real protocol, and that the probability of the last game can easily be computed, we can bound $\epsilon$ by transitivity.

Game₁.

This game is defined as the real protocol, i.e. $\mathsf{Game}_{1}\coloneqq\mathsf{V}_{0}\kern-2.0pt\leftrightsquigarrow\kern-2% .0pt\mathsf{A}\kern-2.0pt\leftrightsquigarrow\kern-2.0pt\mathsf{B}\kern-2.0pt% \leftrightsquigarrow\kern-2.0pt\mathsf{V}_{1}$ . Therefore, we trivially have:

\displaystyle\Pr\left[\,\mathsf{V}_{0}\kern-2.0pt\leftrightsquigarrow\kern-2.0% pt\mathsf{A}\kern-2.0pt\leftrightsquigarrow\kern-2.0pt\mathsf{B}\kern-2.0pt% \leftrightsquigarrow\kern-2.0pt\mathsf{V}_{1}=\mathsf{Accept}\,\right]=\Pr% \left[\,\mathsf{Game}_{1}=\mathsf{Accept}\,\right].

(25)

Game₂.

Is like $\mathsf{Game}_{1}$ , except that each $|\phi_{i}\rangle$ is replaced with one half of a Bell pair. Similarly, instead of projecting on $|\phi_{i}\rangle$ , the verifier will do a Bell measurement between the state sent by the prover and its corresponding half of Bell pair, accepting only if the outcome is $(0,0)$ . This trick is often used in literature, hence we skip the computations. Hence

\displaystyle\Pr\left[\,\mathsf{Game}_{1}=\mathsf{Accept}\,\right]=\Pr\left[\,% \mathsf{Game}_{2}=\mathsf{Accept}\,\right].

(26)

Game₃.

Is like $\mathsf{Game}_{2}$ , except that at time $t=1$ , one samples the random bit string $x\mathrel{\mathchoice{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$\scriptstyle% \mathdollar$}\hskip 0.0pt\cr$\displaystyle\leftarrow$\cr}}{\ooalign{\hskip 0.0% pt\raisebox{0.7pt}{$\scriptstyle\mathdollar$}\hskip 0.0pt\cr$\textstyle% \leftarrow$\cr}}{\ooalign{\hskip 0.0pt\raisebox{0.7pt}{$\scriptscriptstyle% \mathdollar$}\hskip 0.0pt\cr$\scriptstyle\leftarrow$\cr}}{\ooalign{\hskip 0.0% pt\raisebox{0.7pt}{$\scriptscriptstyle\mathdollar$}\hskip 0.0pt\cr$% \scriptscriptstyle\leftarrow$\cr}}}\{0,1\}^{n}$ , and reprogram the oracle to implement $H^{\prime}\coloneqq H[r_{0}\oplus r_{1}\mapsto x]$ (i.e., $A_{1}$ and $B_{1}$ will have oracle access to $H^{\prime}$ instead of $H$ ). Note that the simulators will use this value of $x=H^{\prime}(r_{0}\oplus r_{1})$ instead of $H(r_{0}\oplus r_{1})$ to perform the verification at the end. Intuitively, the only way to distinguish this game from the previous game is if the adversary managed to query $H(r_{0}\oplus r_{1})$ before $t=0$ and after, but this is highly unlikely since neither $A_{0}$ nor $B_{0}$ know both $r_{0}$ and $r_{1}$ (and remember that they cannot query the oracle more than $q$ times, so they cannot just evaluate the oracle on all inputs). This intuition is formalized thanks to Lemma 14: if we define $\mathcal{A}_{1}(r)$ as the execution of the protocol in $\mathsf{Game}_{2}$ until $t=1$ (which is the same as in $\mathsf{Game}_{3}$ ), except that $r_{2}$ is chosen as $r_{2}\coloneqq r_{1}\oplus r$ , and $\mathcal{A}_{2}(r,x)$ as the execution of the protocol after time $t=1$ , we can remark that (using notations from Lemma 14):

\displaystyle P_{\mathcal{A}}^{1}=\text{Pr}[\mathsf{Game}_{2}=\mathsf{Accept}].

(27)

since sampling $(r_{1},r_{2})$ uniformly at random is strictly equivalent to sampling $(r_{1},r)$ randomly and then defining $r_{2}\coloneqq r\oplus r_{1}$ . Similarly, we also have:

\displaystyle P_{\mathcal{A}}^{2}=\text{Pr}[\mathsf{Game}_{3}=\mathsf{Accept}].

(28)

The remaining part is to bound $P_{C}$ . To compute $P_{C}$ , we need to bound the probability of querying $H(r)$ during the first part of the protocol on $j$ -th query. But when $\mathsf{A}_{0}$ does this query, we know that it must be independent of $r$ since all inputs of $\mathsf{A}_{0}$ are independent of $r$ (if not, we could break non-signaling). Similarly, queries made by $\mathsf{B}_{0}$ are independent of $r$ : the exact same argument does not hold since $r_{2}=r_{1}\oplus r$ does depend on $r$ … but this is only a very superficial dependency, since we could have exactly the same probability distributions of $r_{1}$ and $r_{2}$ by sampling instead $r_{2}$ randomly and $r_{1}=r_{2}\oplus r$ , making $r_{2}$ independent of $r$ now. Hence, the $j$ -th query is independent of $r$ , so the best probability of it being equal to $r$ is lower bounded by $P_{C}\leq\frac{1}{2^{\ell}}$ . Hence, using Lemma 14, we have:

	$\displaystyle\|\Pr\left[\,\mathsf{Game}_{2}=\mathsf{Accept}\,\right]-\Pr\left[% \,\mathsf{Game}_{3}=\mathsf{Accept}\,\right]\|$		(29)
	$\displaystyle\mathrel{\stackrel{{\scriptstyle\begin{subarray}{c}(\ref{eq:% pcagame3})\end{subarray}}}{{=}}}\|P_{\mathcal{A}}^{1}-P_{\mathcal{A}}^{2}\|% \mathrel{\stackrel{{\scriptstyle\begin{subarray}{c}(\ref{unr14:reprogrammable}% )\end{subarray}}}{{\leq}}}2q\sqrt{P_{C}}\leq 2q2^{-\ell/2}.$		(30)

Game₄.

Now, we can realize that all operations in $\mathsf{Game}_{3}$ until $t=1$ is independent of $x$ . So let us call $|\psi\rangle_{RP_{A}P_{B}}$ the (purification) of the state owned by the verifier (consisting in a list of qubits part of a shared Bell pair), Alice and Bob (we also include in $P_{B}$ the message sent by $\mathsf{A}_{0}$ to $\mathsf{B}_{1}$ , and similarly in $P_{A}$ the message sent by $\mathsf{B}_{0}$ to $\mathsf{A}_{1}$ ). Additionally, we also include in $|\psi\rangle$ the (exponentially large) definition of $H$ , $r_{0}$ and $r_{1}$ in both registers $P_{A}$ and $P_{B}$ , one copy for each party. Then, we define the referee operation $R$ as the identity, $P_{A}$ as the map that runs $\mathsf{A}_{1}$ , simulating the query to $H^{\prime}$ using the table $H$ , $r_{0}$ and $r_{1}$ that are part of $|\psi\rangle$ , and $x$ that is given as an input to $P_{A}$ , and we define similarly $P_{B}$ simulating $\mathsf{B}_{1}$ . We define then $\mathsf{Game}_{4}$ as the game $\text{QCG}_{2}^{\times n}$ , i.e. the parallel repetition of the $2$ -party quantum cloning game (Definition 5), involving the shared state $|\psi\rangle$ , the referee $R$ , and the two parties $P_{A}$ and $P_{B}$ . This game is exactly like $\mathsf{Game}_{3}$ as we simulate exactly the same process, just grouping differently the various circuits involved. Hence, $\Pr\left[\,\mathsf{Game}_{4}=\mathsf{Accept}\,\right]=\Pr\left[\,\mathsf{Game}% _{3}=\mathsf{Accept}\,\right]$ . But using Theorem 8, we have:

\displaystyle\Pr\left[\,\mathsf{Game}_{4}\,\right]=\omega^{*}(\emph{{QCG}}_{2}% ^{\times n})\mathrel{\stackrel{{\scriptstyle\begin{subarray}{c}(\ref{thm:% optimal2QCGparallel})\end{subarray}}}{{\leq}}}\left(\frac{1}{2}+\frac{1}{2% \sqrt{2}}\right)^{n}.

(31)

Hence, we can combine all the above equations to obtain:

\displaystyle\Pr\left[\,\mathsf{V}_{0}\kern-2.0pt\leftrightsquigarrow\kern-2.0% pt\mathsf{A}\kern-2.0pt\leftrightsquigarrow\kern-2.0pt\mathsf{B}\kern-2.0pt% \leftrightsquigarrow\kern-2.0pt\mathsf{V}_{1}=\mathsf{Accept}\,\right]=\Pr% \left[\,\mathsf{Game}_{1}=\mathsf{Accept}\,\right]\leq\left(\frac{1}{2}+\frac{% 1}{2\sqrt{2}}\right)^{n}+2q2^{-\ell/2},

(32)

concluding the proof. $\hfill\blacktriangleleft$

7 Discussion

We have introduced the concept of the $k$ -party quantum cloning game and provided the optimal winning probability for any number of parties. The parallel repetition for the two-party version was studied, showing an exponential decay of the optimal winning probability. We applied the above results to show security of the routing QPV protocol in the No Pre-shared Entanglement and Bounded-Entanglement models, as well as in the Random Oracle Model. The tightness of Theorem 8 remains an open question, either by showing a strategy attaining the value (11), or if strong parallel repetition holds and actually the optimal value is $\left(\frac{3}{4}\right)^{n}$ (or neither of them). Closing this gap would imply knowing what is the optimal security for the routing protocol in the No-PE model, and would further tighten its security in the BE $(m)$ and random-oracle models.

References

[1] Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani. Device-Independent Security of Quantum Cryptography against Collective Attacks. Physical Review Letters, 98(23):230501, June 2007. doi:10.1103/PhysRevLett.98.230501.
[2] Tomothy Spiller Adrian Kent, William Munro and Raymond Beausoleil. Tagging systems. us patent nr 2006/0022832, 2006.
[3] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, and Philip Verduyn Lunel. Relating non-local quantum computation to information theoretic cryptography. Quantum, 8:1387, June 2024. doi:10.22331/q-2024-06-27-1387.
[4] Rene Allerstorfer, Harry Buhrman, Florian Speelman, and Philip Verduyn Lunel. On the role of quantum communication and loss in attacks on quantum position verification, 2022. arXiv:2208.04341.
[5] Janet Anders and Dan E. Browne. Computational Power of Correlations. Physical Review Letters, 102(5):050502, February 2009. doi:10.1103/PhysRevLett.102.050502.
[6] Vahid Asadi, Richard Cleve, Eric Culf, and Alex May. Linear gate bounds against natural functions for position-verification, 2024. doi:10.22331/q-2025-01-21-1604.
[7] Vahid Asadi, Eric Culf, and Alex May. Rank lower bounds on non-local quantum computation. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:18, 2025. doi:10.4230/LIPIcs.ITCS.2025.11.
[8] Salman Beigi and Robert König. Simplified instantaneous non-local quantum computation with applications to position-based cryptography. New Journal of Physics, 13(9):093036, September 2011. doi:10.1088/1367-2630/13/9/093036.
[9] J. S. Bell. On the einstein podolsky rosen paradox. Physics Physique Fizika, 1:195–200, November 1964. doi:10.1103/PhysicsPhysiqueFizika.1.195.
[10] Charles H. Bennett and Gilles Brassard. Quantum cryptography: public key distribution and coin tossing. Proc. IEEE Int. Conf. on Computers, Systems, and Signal Process (Bangalore) (Piscataway, NJ: IEEE), 1984.
[11] Andreas Bluhm, Matthias Christandl, and Florian Speelman. A single-qubit position verification protocol that is secure against multi-qubit attacks. Nature Physics, pages 1–4, 2022.
[12] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner. Bell nonlocality. Rev. Mod. Phys., 86:419–478, April 2014. doi:10.1103/RevModPhys.86.419.
[13] Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner. Position-based quantum cryptography: Impossibility and constructions. SIAM Journal on Computing, 43(1):150–178, January 2014. doi:10.1137/130913687.
[14] Harry Buhrman, Richard Cleve, Serge Massar, and Ronald de Wolf. Nonlocality and communication complexity. Reviews of Modern Physics, 82(1):665–698, March 2010. doi:10.1103/RevModPhys.82.665.
[15] Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman. The garden-hose model. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science - ITCS '13. ACM Press, 2013. doi:10.1145/2422436.2422455.
[16] Kaushik Chakraborty and Anthony Leverrier. Practical position-based quantum cryptography. Physical Review A, 92(5), November 2015. doi:10.1103/physreva.92.052304.
[17] Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky. Position based cryptography. In Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference, volume 5677 of Lecture Notes in Computer Science, pages 391–407. Springer, 2009. doi:10.1007/978-3-642-03356-8_23.
[18] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 1969.
[19] Valerie Coffman, Joydip Kundu, and William K. Wootters. Distributed entanglement. Physical Review A, 61(5), April 2000. doi:10.1103/physreva.61.052306.
[20] Sam Cree and Alex May. Code-routing: a new attack on position-verification. Quantum, 7, 1079, 2022. doi:10.22331/q-2023-08-09-1079.
[21] Kfir Dolev. Constraining the doability of relativistic quantum tasks. arXiv preprint, 2019. arXiv:1909.05403.
[22] Kfir Dolev and Sam Cree. Non-local computation of quantum circuits with small light cones. arXiv preprint, 2022. arXiv:2203.10106.
[23] W. Dür, G. Vidal, and J. I. Cirac. Three qubits can be entangled in two inequivalent ways. Phys. Rev. A, 62:062314, November 2000. doi:10.1103/PhysRevA.62.062314.
[24] Fei Gao, Bin Liu, and QiaoYan Wen. Quantum position verification in bounded-attack-frequency model. SCIENCE CHINA Physics, Mechanics & Astronomy, 59(11):1–11, 2016.
[25] Alvin Gonzales and Eric Chitambar. Bounds on instantaneous nonlocal quantum computation. IEEE Transactions on Information Theory, 66(5):2951–2963, 2019.
[26] Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. Going beyond bell’s theorem. In Menas Kafatos, editor, Bell’s Theorem, Quantum Theory and Conceptions of the Universe, pages 69–72. Springer Netherlands, Dordrecht, 1989. doi:10.1007/978-94-017-0849-4_10.
[27] Nathaniel Johnston, Rajat Mittal, Vincent Russo, and John Watrous. Extended non-local games and monogamy-of-entanglement games. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 472(2189):20160003, May 2016. doi:10.1098/rspa.2016.0003.
[28] Adrian Kent, William J. Munro, and Timothy P. Spiller. Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Physical Review A, 84(1), July 2011. doi:10.1103/physreva.84.012326.
[29] Hoi-Kwan Lau and Hoi-Kwong Lo. Insecurity of position-based quantum-cryptography protocols against entanglement attacks. Physical Review A, 83(1), January 2011. doi:10.1103/physreva.83.012322.
[30] Jiahui Liu, Qipeng Liu, and Luowen Qian. Beating Classical Impossibility of Position Verification. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 100:1–100:11, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2022.100.
[31] Robert A. Malaney. Location-dependent communications using quantum entanglement. Phys. Rev. A, 81:042319, April 2010. doi:10.1103/PhysRevA.81.042319.
[32] Dominic Mayers and Andrew Yao. Self Testing Quantum Apparatus. Quantum Info. Comput., 4(4):273–286, July 2004. URL: http://dl.acm.org/citation.cfm?id=2011827.2011830.
[33] S. Pironio, A. Acín, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe. Random numbers certified by Bell’s theorem. Nature, 464(7291):1021–1024, April 2010. doi:10.1038/nature09008.
[34] Jérémy Ribeiro and Frédéric Grosshans. A tight lower bound for the bb84-states quantum-position-verification protocol, 2015. doi:10.48550/arXiv.1504.07171.
[35] Christian Schaffner. Cryptography in the bounded-quantum-storage model, 2007. arXiv:0709.0289.
[36] Florian Speelman. Instantaneous non-local computation of low T-depth quantum circuits. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016.
[37] Ivan Šupić and Joseph Bowles. Self-testing of quantum systems: a review. arXiv:1904.10042 [quant-ph], April 2019. arXiv: 1904.10042. arXiv:1904.10042.
[38] Marco Tomamichel, Serge Fehr, Jedrzej Kaniewski, and Stephanie Wehner. A monogamy-of-entanglement game with applications to device-independent quantum cryptography. New Journal of Physics, 15(10):103002, October 2013. doi:10.1088/1367-2630/15/10/103002.
[39] Dominique Unruh. Quantum position verification in the random oracle model. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology – CRYPTO 2014, pages 1–18, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
[40] Dominique Unruh. Quantum Position Verification in the Random Oracle Model. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology – CRYPTO 2014, Lecture Notes in Computer Science, pages 1–18, Berlin, Heidelberg, 2014. Springer. doi:10.1007/978-3-662-44381-1_1.
[41] William K. Wootters and Wojciech Zurek. A single quantum cannot be cloned. Nature, 299:802–803, 1982.
[42] Mark Zhandry. How to Record Quantum Queries, and Applications to Quantum Indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, Lecture Notes in Computer Science, pages 239–268. Springer International Publishing, 2019. doi:10.1007/978-3-030-26951-7_9.

[bib.bib1] [1] Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani. Device-Independent Security of Quantum Cryptography against Collective Attacks. Physical Review Letters, 98(23):230501, June 2007. doi:10.1103/PhysRevLett.98.230501.

[bib.bib2] [2] Tomothy Spiller Adrian Kent, William Munro and Raymond Beausoleil. Tagging systems. us patent nr 2006/0022832, 2006.

[bib.bib3] [3] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, and Philip Verduyn Lunel. Relating non-local quantum computation to information theoretic cryptography. Quantum, 8:1387, June 2024. doi:10.22331/q-2024-06-27-1387.

[bib.bib4] [4] Rene Allerstorfer, Harry Buhrman, Florian Speelman, and Philip Verduyn Lunel. On the role of quantum communication and loss in attacks on quantum position verification, 2022. arXiv:2208.04341.

[bib.bib5] [5] Janet Anders and Dan E. Browne. Computational Power of Correlations. Physical Review Letters, 102(5):050502, February 2009. doi:10.1103/PhysRevLett.102.050502.

[bib.bib6] [6] Vahid Asadi, Richard Cleve, Eric Culf, and Alex May. Linear gate bounds against natural functions for position-verification, 2024. doi:10.22331/q-2025-01-21-1604.

[bib.bib7] [7] Vahid Asadi, Eric Culf, and Alex May. Rank lower bounds on non-local quantum computation. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:18, 2025. doi:10.4230/LIPIcs.ITCS.2025.11.

[bib.bib8] [8] Salman Beigi and Robert König. Simplified instantaneous non-local quantum computation with applications to position-based cryptography. New Journal of Physics, 13(9):093036, September 2011. doi:10.1088/1367-2630/13/9/093036.

[bib.bib9] [9] J. S. Bell. On the einstein podolsky rosen paradox. Physics Physique Fizika, 1:195–200, November 1964. doi:10.1103/PhysicsPhysiqueFizika.1.195.

[bib.bib10] [10] Charles H. Bennett and Gilles Brassard. Quantum cryptography: public key distribution and coin tossing. Proc. IEEE Int. Conf. on Computers, Systems, and Signal Process (Bangalore) (Piscataway, NJ: IEEE), 1984.

[bib.bib11] [11] Andreas Bluhm, Matthias Christandl, and Florian Speelman. A single-qubit position verification protocol that is secure against multi-qubit attacks. Nature Physics, pages 1–4, 2022.

[bib.bib12] [12] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner. Bell nonlocality. Rev. Mod. Phys., 86:419–478, April 2014. doi:10.1103/RevModPhys.86.419.

[bib.bib13] [13] Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner. Position-based quantum cryptography: Impossibility and constructions. SIAM Journal on Computing, 43(1):150–178, January 2014. doi:10.1137/130913687.

[bib.bib14] [14] Harry Buhrman, Richard Cleve, Serge Massar, and Ronald de Wolf. Nonlocality and communication complexity. Reviews of Modern Physics, 82(1):665–698, March 2010. doi:10.1103/RevModPhys.82.665.

[bib.bib15] [15] Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman. The garden-hose model. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science - ITCS '13. ACM Press, 2013. doi:10.1145/2422436.2422455.

[bib.bib16] [16] Kaushik Chakraborty and Anthony Leverrier. Practical position-based quantum cryptography. Physical Review A, 92(5), November 2015. doi:10.1103/physreva.92.052304.

[bib.bib17] [17] Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky. Position based cryptography. In Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference, volume 5677 of Lecture Notes in Computer Science, pages 391–407. Springer, 2009. doi:10.1007/978-3-642-03356-8_23.

[bib.bib18] [18] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 1969.

[bib.bib19] [19] Valerie Coffman, Joydip Kundu, and William K. Wootters. Distributed entanglement. Physical Review A, 61(5), April 2000. doi:10.1103/physreva.61.052306.

[bib.bib20] [20] Sam Cree and Alex May. Code-routing: a new attack on position-verification. Quantum, 7, 1079, 2022. doi:10.22331/q-2023-08-09-1079.

[bib.bib21] [21] Kfir Dolev. Constraining the doability of relativistic quantum tasks. arXiv preprint, 2019. arXiv:1909.05403.

[bib.bib22] [22] Kfir Dolev and Sam Cree. Non-local computation of quantum circuits with small light cones. arXiv preprint, 2022. arXiv:2203.10106.

[bib.bib23] [23] W. Dür, G. Vidal, and J. I. Cirac. Three qubits can be entangled in two inequivalent ways. Phys. Rev. A, 62:062314, November 2000. doi:10.1103/PhysRevA.62.062314.

[bib.bib24] [24] Fei Gao, Bin Liu, and QiaoYan Wen. Quantum position verification in bounded-attack-frequency model. SCIENCE CHINA Physics, Mechanics & Astronomy, 59(11):1–11, 2016.

[bib.bib25] [25] Alvin Gonzales and Eric Chitambar. Bounds on instantaneous nonlocal quantum computation. IEEE Transactions on Information Theory, 66(5):2951–2963, 2019.

[bib.bib26] [26] Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. Going beyond bell’s theorem. In Menas Kafatos, editor, Bell’s Theorem, Quantum Theory and Conceptions of the Universe, pages 69–72. Springer Netherlands, Dordrecht, 1989. doi:10.1007/978-94-017-0849-4_10.

[bib.bib27] [27] Nathaniel Johnston, Rajat Mittal, Vincent Russo, and John Watrous. Extended non-local games and monogamy-of-entanglement games. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 472(2189):20160003, May 2016. doi:10.1098/rspa.2016.0003.

[bib.bib28] [28] Adrian Kent, William J. Munro, and Timothy P. Spiller. Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Physical Review A, 84(1), July 2011. doi:10.1103/physreva.84.012326.

[bib.bib29] [29] Hoi-Kwan Lau and Hoi-Kwong Lo. Insecurity of position-based quantum-cryptography protocols against entanglement attacks. Physical Review A, 83(1), January 2011. doi:10.1103/physreva.83.012322.

[bib.bib30] [30] Jiahui Liu, Qipeng Liu, and Luowen Qian. Beating Classical Impossibility of Position Verification. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 100:1–100:11, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2022.100.

[bib.bib31] [31] Robert A. Malaney. Location-dependent communications using quantum entanglement. Phys. Rev. A, 81:042319, April 2010. doi:10.1103/PhysRevA.81.042319.

[bib.bib32] [32] Dominic Mayers and Andrew Yao. Self Testing Quantum Apparatus. Quantum Info. Comput., 4(4):273–286, July 2004. URL: http://dl.acm.org/citation.cfm?id=2011827.2011830.

[bib.bib33] [33] S. Pironio, A. Acín, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe. Random numbers certified by Bell’s theorem. Nature, 464(7291):1021–1024, April 2010. doi:10.1038/nature09008.

[bib.bib34] [34] Jérémy Ribeiro and Frédéric Grosshans. A tight lower bound for the bb84-states quantum-position-verification protocol, 2015. doi:10.48550/arXiv.1504.07171.

[bib.bib35] [35] Christian Schaffner. Cryptography in the bounded-quantum-storage model, 2007. arXiv:0709.0289.

[bib.bib36] [36] Florian Speelman. Instantaneous non-local computation of low T-depth quantum circuits. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016.

[bib.bib37] [37] Ivan Šupić and Joseph Bowles. Self-testing of quantum systems: a review. arXiv:1904.10042 [quant-ph], April 2019. arXiv: 1904.10042. arXiv:1904.10042.

[bib.bib38] [38] Marco Tomamichel, Serge Fehr, Jedrzej Kaniewski, and Stephanie Wehner. A monogamy-of-entanglement game with applications to device-independent quantum cryptography. New Journal of Physics, 15(10):103002, October 2013. doi:10.1088/1367-2630/15/10/103002.

[bib.bib39] [39] Dominique Unruh. Quantum position verification in the random oracle model. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology – CRYPTO 2014, pages 1–18, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.

[bib.bib40] [40] Dominique Unruh. Quantum Position Verification in the Random Oracle Model. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology – CRYPTO 2014, Lecture Notes in Computer Science, pages 1–18, Berlin, Heidelberg, 2014. Springer. doi:10.1007/978-3-662-44381-1_1.

[bib.bib41] [41] William K. Wootters and Wojciech Zurek. A single quantum cannot be cloned. Nature, 299:802–803, 1982.

[bib.bib42] [42] Mark Zhandry. How to Record Quantum Queries, and Applications to Quantum Indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, Lecture Notes in Computer Science, pages 239–268. Springer International Publishing, 2019. doi:10.1007/978-3-030-26951-7_9.

A Quantum Cloning Game with Applications to Quantum Position Verification

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

2 Preliminaries

Definition 1.

Lemma 2 (Lemma 2 in [38]).

▶ Remark 3.

Lemma 4 (Lemma 1 in [38]).

3 𝒌-party quantum cloning game

Definition 5.

Theorem 6.

Proof.

3.1 Quantum cloning game with any target state

Theorem 7.

Proof.

4 Parallel repetition of QCGk

Theorem 8.

Proof.

5 Application to QPV in the No-PE and BE(m) models

Definition 9.

Proposition 10.

Proposition 11.

Corollary 12.

6 Application to QPV in the random oracle model

Theorem 13.

Lemma 14 ([40, Lemma 3]).

Proof (of Theorem 13).

Game1.

Game2.

Game3.

Game4.

7 Discussion

References

$\blacktriangleright$ Remark 3.

3 $𝒌$ -party quantum cloning game

4 Parallel repetition of QCG_k

Game₁.

Game₂.

Game₃.

Game₄.