Paper The following article is Open access

A monogamy-of-entanglement game with applications to device-independent quantum cryptography

, , and

Published 2 October 2013 © IOP Publishing and Deutsche Physikalische Gesellschaft
, , Citation Marco Tomamichel et al 2013 New J. Phys. 15 103002 DOI 10.1088/1367-2630/15/10/103002

1367-2630/15/10/103002

Abstract

We consider a game in which two separate laboratories collaborate to prepare a quantum system and are then asked to guess the outcome of a measurement performed by a third party in a random basis on that system. Intuitively, by the uncertainty principle and the monogamy of entanglement, the probability that both players simultaneously succeed in guessing the outcome correctly is bounded. We are interested in the question of how the success probability scales when many such games are performed in parallel. We show that any strategy that maximizes the probability to win every game individually is also optimal for the parallel repetition of the game. Our result implies that the optimal guessing probability can be achieved without the use of entanglement. We explore several applications of this result. Firstly, we show that it implies security for standard BB84 quantum key distribution when the receiving party uses fully untrusted measurement devices, i.e. we show that BB84 is one-sided device independent. Secondly, we show how our result can be used to prove security of a one-round position-verification scheme. Finally, we generalize a well-known uncertainty relation for the guessing probability to quantum side information.

Export citation and abstract BibTeX RIS

Content from this work may be used under the terms of the Creative Commons Attribution 3.0 licence. Any further distribution of this work must maintain attribution to the author(s) and the title of the work, journal citation and DOI.

1. Introduction

Apart from their obvious entertainment value, games among multiple (competing) players often provide an intuitive way to understand complex problems. For example, we may understand Bell inequalities in physics [4], or interactive proofs in computer science [5], as a game played by a referee against multiple provers [16, 21]. Here we investigate a simple quantum multiplayer game whose analysis enables us to tackle several open questions in quantum cryptography.

1.1. Monogamy game

We consider a game played among three parties: Alice, Bob and Charlie (these players should be seen as operating in three different laboratories). In this game, Alice takes the role of a referee and is assumed to be honest whereas Bob and Charlie form a team determined to beat Alice. A monogamy-of-entanglement game G consists of a list of measurements, $\mathcal {M}^\theta = \{F_x^\theta \}_{x \in \cal X}$ , indexed by θ∈Θ, on a d-dimensional quantum system.

Preparation phase. Bob and Charlie agree on a strategy and prepare an arbitrary quantum state ρABC, where ρA has dimension d. They pass ρA to Alice and hold on to ρB and ρC, respectively. After this phase, Bob and Charlie are no longer allowed to communicate.

Question phase. Alice chooses θ∈Θ uniformly at random and measures ρA using $\mathcal {M}^\theta $ to obtain the measurement outcome, $x \in \cal X$ . She then announces θ to Bob and Charlie.

Answer phase. Bob and Charlie independently form a guess of x by performing a measurement (which may depend on θ) on their respective shares of the quantum state.

Winning condition. The game is won if both Bob and Charlie guess x correctly.

From the perspective of classical information processing, our game may appear somewhat trivial—after all, if Bob and Charlie were to provide some classical information k to Alice who would merely apply a random function fθ, they could predict the value of x = fθ(k) perfectly from k and θ. In quantum mechanics, however, the well-known uncertainty principle [25] places a limit on how well observers can predict the outcome x of incompatible measurements.

To exemplify this, we will in the following focus on the game GBB84 in which Alice measures a qubit in one of the two BB84 bases [7] to obtain a bit x∈{01} and use pwin(GBB84) to denote the probability that Bob and Charlie win, maximized over all strategies. (A strategy is comprised of a tripartite state ρABC, and, for each θ∈Θ, a measurement on B and a measurement on C.) Then, if Bob and Charlie are restricted to classical memory (i.e. they are not entangled with Alice), it is easy to see that they win the game with an (average) probability of at most $1/2 + 1/(2\sqrt {2}) \leqslant p_{\mathrm {win}}({\sf G}_{\mathrm {BB84}})$ .4

In a fully quantum world, however, uncertainty is not quite the end of the story as indeed Bob and Charlie are allowed to have a quantum memory. To illustrate the power of such a memory, consider the same game played just between Alice and Bob. As Einstein et al [19] famously observed. If ρAB is a maximally entangled state, then once Bob learns Alice's choice of measurement θ, he can perform an adequate measurement on his share of the state to obtain x himself. That is, there exists a strategy for Bob to guess x perfectly. Does this change when we add the extra player, Charlie? We can certainly be hopeful as it turns out that quantum entanglement is 'monogamous' [55] in the sense that the more entangled Bob is with Alice, the less entangled Charlie can be. In the extreme case where ρAB is maximally entangled, even if Bob can guess x perfectly every time, Charlie has to resort to making an uninformed random guess. As both of them have to be correct in order to win the game, this strategy turns out to be worse than optimal.

An analysis of this game thus requires a tightrope walk between uncertainty on the one hand, and the monogamy of entanglement on the other. The following result is a special case of our main result (which we explain further down); a slightly weaker bound had been derived in [14], and the exact value had first been proven by Christandl and Schuch [15]5.

  • Result (informal). We find $p_{\mathrm {win}}({\sf G}_{\mathrm { BB84}}) = 1/2 + 1/(2\sqrt {2}) \approx 0.85$ . Moreover, this value can be achieved when Bob and Charlie have a classical memory only.

Interestingly, we thus see that monogamy of entanglement wins out entirely, canceling the power of Bob and Charlie's quantum memory—the optimal winning probability can be achieved without any entanglement at all. In fact, this strategy results in a higher success probability than the one in which Bob is maximally entangled with Alice and Charlie is classical. In such a case the winning probability can be shown to be at most 1/2. In spirit, this result is similar to (but not implied by) recent results obtained in the study of non-local games where the addition of one or more extra parties cancels the advantage coming from the use of entanglement [29].

To employ the monogamy game for quantum cryptographic purposes, we need to understand what happens if we play the same game Gn times in parallel. The resulting game, G×n, requires both Bob and Charlie to guess the entire string x = x1...xn of measurement outcomes, where xj, j∈[n], is generated by measuring ρAj (ρAj is the quantum state provided by Bob and Charlie in the jth round of the game) in the basis $\mathcal {M}^{\theta _j}$ , and θj∈Θ is chosen uniformly at random. Strategies for Bob and Charlie are then determined by the state ρA1...AnBC (with each Aj being d-dimensional) as well as independent measurements on B and C that produce a guess of the string x, for each value of θ = θ1...θn∈Θn. In the following, we say that a game satisfies parallel repetition if pwin(G×n) drops exponentially in n. Moreover, we say that it satisfies strong parallel repetition if this exponential drop is maximally fast, i.e. if pwin(G×n) = pwin(G)n.

Returning to our example, Bob and Charlie could repeat the strategy that is optimal for a single round n times to achieve a winning probability of $p_{\mathrm {win}}({\sf G}_{\mathrm { BB84}})^n = (1/2 + 1/(2\sqrt {2})^n \leqslant p_{\mathrm {win}}({\sf G}_{\mathrm { BB84}}^{\times n})$ , but is this really the best they can do? Even classically, analyzing the n-fold parallel repetition of games or tasks is typically challenging. Examples include the parallel repetition of interactive proof systems (see e.g. [26, 48]) or the analysis of communication complexity tasks (see e.g. [33]). In a quantum world, such an analysis is often exacerbated further by the presence of entanglement and the fact that quantum information cannot generally be copied. Famous examples include the analysis of the 'parallel repetition' of channels in quantum information theory (where the problem is referred to as the additivity of capacities) (see e.g. [24, 54]), entangled non-local games [30], or the question whether an eavesdropper's optimal strategy in quantum key distribution (QKD) is to perform the optimal strategy for each round. Fortunately, it turns out that strong parallel repetition does hold for our monogamy game.

  • Main result (informal). We find $p_{\mathrm {win}}({\sf G}_{\mathrm { BB84}}^{\times n}) = (1/2 + 1/(2\sqrt {2}))^n$ . More generally, for all monogamy-of-entanglement games using incompatible measurements, we find that pwin(G×n) decreases exponentially in n. This also holds in the approximate case where Bob and Charlie are allowed to make a small fraction of errors.

Our proofs are appealing in their simplicity and use only tools from linear algebra, inspired by techniques proposed by Kittaneh [32]. Note that, in the more general case, we obtain parallel repetition, albeit not strong parallel repetition.

1.2. Applications

1.2.1. One-sided device independent quantum key distribution (QKD)

QKD makes use of quantum mechanical effects to allow two parties, Alice and Bob, to exchange a secret key while being eavesdropped by an attacker Eve [7, 20]. In principle, the security of QKD can be rigorously proven based solely on the laws of quantum mechanics [45, 50, 53]; in particular, the security does not rely on the assumed hardness of some computational problem. However, these security proofs typically make stringent assumptions about the devices used by Alice and Bob to prepare and measure the quantum states that are communicated. These assumptions are not necessarily satisfied by real-world devices, leaving the implementations of QKD schemes open to hacking attacks [40].

One way to counter this problem is by protecting the devices in an ad hoc manner against known attacks. This is somewhat unsatisfactory in that the implementation may still be vulnerable to unknown attacks, and the fact that the scheme is in principle provably secure loses a lot of its significance.

Another approach is to try to remove the assumptions on the devices necessary for the security proof; this leads to the notion of device-independent (DI) QKD. This line of research can be traced back to Mayers and Yao [46] (see also [1, 2]). After some limited results (see e.g. [23, 44]), the possibility of DI QKD has recently been shown in the most general case by Reichardt et al in [49] and by Vazirani and Vidick in [61]. In a typical DI QKD scheme, Alice and Bob check if the classical data obtained from the quantum communication violates a Bell inequality, which in turn ensures that there is some amount of fresh randomness in the data that cannot be known by Eve. This can then be transformed into a secret key using standard cryptographic techniques like information reconciliation and randomness extraction.

While this argument shows that DI QKD is theoretically possible, the disadvantage of such schemes is that they require a long-distance detection-loophole-free violation of a Bell inequality by Alice and Bob. This makes fully DI QKD schemes very hard to implement and very sensitive to any kind of noise and to inefficiencies of the physical devices: any deficiency will result in a lower observed (loophole free) Bell inequality violation, and currently conceivable experimental parameters are insufficient to provide provable security. Trying to find ways around this problem is an active line of research, see e.g. [10, 22, 37, 39, 47].

Here, we follow a somewhat different approach, not relying on Bell tests, but making use of the monogamy of entanglement. Informally, the latter states that if Alice's state is fully entangled with Bob's, then it cannot be entangled with Eve's, and vice versa. As a consequence, if Alice measures a quantum system by randomly choosing one of two incompatible measurements, it is impossible for Bob and Eve to both have low entropy about Alice's measurement outcome. Thus, if one can verify that Bob has low entropy about Alice's measurement during the run of the scheme, it is guaranteed that Eve's entropy is high, and thus that a secret key can be distilled.

Based on this idea, we show that the standard BB84 QKD scheme [7] is one-sided DI. This means that only Alice's quantum device has to be trusted, but no assumption about Bob's measurement device has to be made in order to prove security. Beyond that it does not communicate the measurement outcome to Eve, Bob's measurement device may be arbitrarily malicious.

  • Application to QKD (informal). We show that the BB84 QKD scheme is secure in the setting of fully one-sided device independence and provide a complete security analysis for finite key lengths.

One-sided DI security of BB84 was first claimed in [60]. However, a close inspection of their proof sketch, which is based on an entropic uncertainty relation with quantum side information, reveals that their arguments are insufficient to prove full one-sided DI security (as confirmed by the authors). It needs to be assumed that Bob's measurement device is memoryless. The same holds for the follow up work [9, 58] of [60].

Despite the practical motivation, our result is at this point of theoretical nature. This is because, as in all contemporary fully DI schemes, our analysis here (implicitly) assumes that every qubit sent by Alice is indeed received by Bob, or, more generally, whether it is received or not does not depend on the basis it is to be measured in; this is not necessarily satisfied in practical implementations—and some recent attacks on QKD take advantage of exactly this effect by blinding the detectors whenever a measurement in a basis not to Eve's liking is attempted [40]. We remark here that this unwanted assumption can be removed in principle by a refined analysis along the lines of Branciard et al [9].6 While this leads to a significantly lower key rate, the analysis in [9] suggests that the loss tolerance for one-sided DI QKD is higher than for fully DI QKD. More precisely, while DI QKD requires a detection-loophole-free violation of a Bell inequality, for one-sided DI QKD a loophole-free violation of a steering inequality is sufficient, and such a violation has recently been shown [63].

Our analysis of BB84 QKD with one-sided DI security admits a noise level of up to 1.5%. This is significantly lower than the 11% tolerable for standard (i.e. not DI) security. We believe that this is not inherent to the scheme but an artifact of our analysis. Improving this bound by means of a better analysis is an open problem (it can be slightly improved by using a better scheme, e.g. the six-state scheme [11]). Nonetheless, one-sided DI QKD appears to be an attractive alternative to DI QKD in an asymmetric setting, when we can expect from one party, say, a server, to invest in a very carefully designed, constructed and tested apparatus, but not the other party, the user, and/or in case of a star network with one designated link being connected with many other links.

A comparison to other recent results on DI QKD is given in table 1. The noise tolerance is determined using isotropic noise.

Table 1. Comparison of recent fully and partially DI security proofs for QKD.

  Reichardt et al [49] Vazirani/Vidick [61] This work Tomamichel et al [59]a
Protocol E91-based [20] E91-based BBM92 [6]/BB84 [7] Asymmetric BB84 [38]
Device assumptions None None Trusted Aliceb Trusted Aliceb,
        memoryless Bob
Noise tolerance 0% 1.2% 1.5% 11%
Key rate (zero noise) 0% 2.5% 22.8%/11.4%c 1
Finite key analysis No No Yes Yes

aFor comparison, this proof achieves maximum noise tolerance and key rate for BB84. See also [9]. bCombining our results with results on self-testing in [37, 57], one can reduce the assumption to memoryless for Alice. cThis loss of a factor $\frac {1}{2}$ is due to sifting when moving from BBM92 to BB84.

1.2.2. Position verification

Our second application is to the task of position verification. Here, we consider a one-dimensional setting where a prover wants to convince two verifiers that he controls a certain position, pos. The verifiers are located at known positions around pos, honest, and connected by secure communication channels. Moreover, all parties are assumed to have synchronized clocks, and the message delivery time between any two parties is assumed to be proportional to the distance between them. Finally, all local computations are assumed to be instantaneous.

Position verification and variants thereof (like distance bounding) is a rather well-studied problem in the field of wireless security (see e.g. [14]). It was shown in [14] that in the presence of colluding adversaries at different locations, position verification is impossible classically, even with computational hardness assumptions. That is, the prover can always trick the verifiers into believing that he controls a position. The fact that the classical attack requires the adversary to copy information, initially gave hope that we may circumvent the impossibility result using quantum communication [13, 31, 42, 43]. However, such schemes were subsequently broken [36] and indeed a general impossibility proof holds [12]: without any restriction on the adversaries, in particular on the amount of pre-shared entanglement they may hold, no quantum scheme for position verification can be secure. This impossibility proof was constructive but required the dishonest parties to share a number of Einstein–Podolsky–Rosen (EPR) pairs [19] that grows doubly exponentially in the number of qubits the honest parties exchange. Using port-based teleportation, as introduced by Ishizaka and Hiroshima [27, 28], this was reduced by Beigi and König [3] to a single exponential amount. On the other hand, there are schemes for position verification that are provably secure against adversaries that have no pre-shared entanglement, or only hold a couple of entangled qubits [3, 12, 13, 36].

However, all known schemes that are provably secure with a negligible soundness error (the maximal probability that a coalition of adversaries can pass the position verification test for position pos without actually controlling that specific position) against adversaries with no or with bounded pre-shared entanglement are either multi-round schemes, or require the honest participants to manipulate large quantum states.

  • Application to position verification (informal). We present the first provably secure one-round position verification scheme with negligible soundness error in which the honest parties are only required to perform single qubit operations. We prove its security against adversaries with an amount of pre-shared entanglement that is linear in the number of qubits transmitted by the honest parties.

1.2.3. Entropic uncertainty relation

The final application of our monogamy game is to entropic uncertainty relations with quantum side information [8]. Our result is in the spirit of [17, 60] which shows an uncertainty relation for a tripartite state ρABC for measurements on A, trading off the uncertainty between the two observers B and C as in our monogamy game.

  • Application to entropic uncertainty relations. For any two general (positive operator valued measure (POVM)) measurements, {N0x}x and {N1x}x, we find
    The entropies are evaluated for the post-measurement state ρXBCΘ, where X is the outcome of the measurement {Nθx}x, where Θ∈{0,1} is chosen uniformly at random.

1.3. Outline

The remainder of this paper is structured as follows. In section 2, we introduce the basic terminology and notation used throughout this work. In section 3, we discuss the monogamy game and prove a strong parallel repetition theorem. Here, we also generalize the game to include the case where Bob and Charlie are allowed to have some errors in their guess and show an upper bound on the winning probability for the generalized game. Sections 46 then apply these results to prove security for one-sided DI QKD, a one-round position verification scheme and an entropic uncertainty relation.

2. Technical preliminaries

2.1. Basic notation and terminology

Let ${\cal H}$ be an arbitrary, finite dimensional Hilbert space. $\mathcal {L}({\cal H})$ and $\mathcal {P}({\cal H})$ denote linear and positive semi-definite operators on ${\cal H}$ , respectively. Note that an operator $A \in \mathcal {P}({\cal H})$ is in particular Hermitian, meaning that A = A. The set of density operators on ${\cal H}$ , i.e. the set of operators in $\mathcal {P}({\cal H})$ with unit trace, is denoted by ${\cal S}({\cal H})$ . For $A,B \in \mathcal {L}({\cal H})$ , we write A ⩾ B to express that $A - B \in \mathcal {P}({\cal H})$ . When operators are compared with scalars, we implicitly assume that the scalars are multiplied by the identity operator, which we denote by  $1_{{\cal H}}$ , or 1 if ${\cal H}$ is clear from the context. A projector is an operator $P \in \mathcal {P}({\cal H})$ that satisfies P2 = P. A POVM (short for positive operator valued measure) is a set {Nx}x of operators $N_x \in \mathcal {P}({\cal H})$ such that $\sum _x N_x = 1$ , and a POVM is called projective if all its elements Nx are projectors. We use the trace distance

as a metric on density operators $\rho ,\sigma \in {\cal S}({\cal H})$ .

The most prominent example of a Hilbert space is the qubit, ${\cal H} \equiv \mathbb {C}^2$ . The vectors |0〉 and |1〉 form its rectilinear (or computational) basis, and the vectors $H| 0 \rangle = (| 0 \rangle +| 1 \rangle )/\sqrt {2}$ and $H| 1 \rangle = (| 0 \rangle -| 1 \rangle )/\sqrt {2}$ form its diagonal (or Hadamard) basis, where H denotes the Hadamard matrix. More generally, we often consider systems composed of n qubits, ${\cal H} \equiv \mathbb {C}^2 \otimes \cdots \otimes \mathbb {C}^2$ . For x,θ∈{0,1}n, we write |xθ〉 as a shorthand for the state vector $H^{\theta _1}| x_1 \rangle \otimes \cdots \otimes H^{\theta _n}| x_n \rangle \in {\cal H}$ .

2.2. The Schatten -norm

For $L \in \mathcal {L}({\cal H})$ , we use the Schatten -norm ∥L∥: = ∥L = s1(L), which evaluates the largest singular value of L. It is easy to verify that this norm satisfies ∥L2 = ∥LL∥ = ∥LL∥. Also, for $A, B \in \mathcal {P}({\cal H})$ , ∥A∥ coincides the largest eigenvalue of A, and A ⩽ B implies ∥A∥ ⩽ ∥B∥. Finally, for block-diagonal operators we have $\| A \oplus B \| = \max \{ \| A \|, \| B \| \}$ . We will also need the following norm inequality.

Lemma 1 Let $A, B, L \in \mathcal {L}({\cal H})$ such that AA ⩾ BB. Then, it holds that ∥AL∥ ⩾ ∥BL∥.

Proof. First, note that AA ⩾ BB implies that LAAL ⩾ LBBL holds for an arbitrary linear operator L. By taking the norm we arrive at ∥LAAL∥ ⩾ ∥LBBL∥, which is equivalent to ∥AL∥ ⩾ ∥BL∥.   □

In particular, if $A, A', B, B' \in \mathcal {P}({\cal H})$ satisfy A' ⩾ A and B' ⩾ B then applying the lemma twice (to the square roots of these operators) gives $\big \| \sqrt {A'} \sqrt {B'} \big \| \geqslant \big \| \sqrt {A'} \sqrt {B} \big \| \geqslant \big \| \sqrt {A} \sqrt {B} \big \|$ . For projectors the square roots can be omitted.

One of our main tools is the following lemma 2, which bounds the Schatten norm of the sum of n positive semi-definite operators by means of their pairwise products. We derive the bound using a construction due to Kittaneh [32], which was also used by Schaffner [52] to derive a similar, but less general, result.

We call two permutations π:[N] → [N] and π':[N] → [N] of the set [N]: = {1,...,N} orthogonal if π(i) ≠ π'(i) for all i∈[N]. There always exists a set of N permutations of [N] that are mutually orthogonal (for instance the N cyclic shifts).

Lemma 2 Let $A_1, A_2, \ldots , A_N \in \mathcal {P}({\cal H})$ , and let {πk}k∈[N] be a set of N mutually orthogonal permutations of [N]. Then

Equation (1)

Proof. We define X = [Xij] as the N × N block-matrix with blocks given by $X_{ij} = \delta _{j1} \sqrt {A_i}$ . Then, the matrices XX and XX are easy to evaluate, namely, $(X^{\dagger }X)_{ij} = \delta _{i1}\delta _{j1} \sum _i A_i$ , as well as XX and $(XX^{\dagger })_{ij} = \sqrt {A_i}\sqrt {A_j}$ . We have

Next, we decompose XX = D1 + D2 + ··· + DN, where the matrices Dk are defined by the permutations πk, respectively, as $(D_k)_{ij} = \delta _{j,\pi ^k(i)} \sqrt {A_i}\sqrt {A_j}$ . Note that the requirement that the permutations are mutually orthogonal ensures that $XX^{\dagger } = \sum _k D_k$ . Moreover, since the matrices Dk are constructed such that they contain exactly one non-zero block in each row and column, they can be transformed into a block-diagonal matrix

by a unitary rotation. Hence, using the triangle inequality and unitary invariance of the norm, we get $\big \| \sum _{k} A_{k} \big \| \leqslant \sum _k \big \| D_k \big \| = \sum _k \big \| D_k' \big \|$ , which implies (1) since $\big \| \bigoplus _i L_i \big \| = \max _i \big \{ \| L_i \| \big \}$ .   □

A special case of the lemma states that $\big \| A_1 + A_2 \big \| \leqslant \max \{ \| A_1 \|, \| A_2 \| \} + \big \| \sqrt {A_1}\sqrt {A_2} \big \|$ .

2.3. Classical-quantum states and min-entropy

A state $\rho _{XB} \in {\cal S}({\cal H}_X \otimes {\cal H}_B)$ is called a classical-quantum (CQ) state with classical X over $\cal X$ , if it is of the form

where $\{ | x \rangle \}_{x \in {\cal X}}$ is a fixed basis of ${\cal H}_X$ , $\{ p_x \}_{x \in {\cal X}}$ is a probability distribution, and $\rho _B^x \in {\cal S}({\cal H}_B)$ . For such a state, X can be understood as a random variable that is correlated with (potentially quantum) side information B.

If $\lambda : {\cal X} \to \{0,1\}$ is a predicate on $\cal X$ , then we denote by $\Pr _{\rho }[\lambda (X)]$ the probability of the event λ(X) under ρ; formally, $\Pr _{\rho }[\lambda (X)] = \sum _x p_x\, \lambda (x)$ . We also define the state ρXB|λ(X), which is the state of the X and B conditioned on the event λ(X). Formally,

For a CQ-state $\rho _{XB} \in {\cal S}({\cal H}_X \otimes {\cal H}_B)$ , the min-entropy of X conditioned on B [50] can be expressed in terms of the maximum probability that a measurement on B yields the correct value of X, i.e. the guessing probability. Formally, we define [34]

Here, the optimization is taken over all POVMs {Nx}x on B, and here and throughout this paper, log denotes the binary logarithm.

In case of a CQ-state ρXBΘ with classical X, and with additional classical side information Θ, we can write $\rho _{XB\Theta } = \sum _{\theta } p_{\theta }\, |\theta \rangle \!\langle \theta | \otimes \rho _{XB}^{\theta }$ for CQ states ρθXB. The min-entropy of X conditioned on B and Θ then evaluates to

Equation (2)

An intuitive explanation of the latter equality is that the optimal strategy to guess X simply chooses an optimal POVM on B depending on the value of Θ.

An overview of the min-entropy and its properties can be found in [50, 56]; we merely point out the chain rule here: for a CQ-state ρXBΘ with classical X and Y , where Y is over an arbitrary set $\mathcal {Y}$ with cardinality $|\mathcal {Y}|$ , it holds that $H_{\min }(X|BY)_{\rho } \geqslant H_{\min }(X|B)_{\rho } - \log |\mathcal {Y}|$ .

3. Parallel repetition of monogamy games

In this section, we investigate and show strong parallel repetition for the game GBB84. Then, we generalize our analysis to allow arbitrary measurements for Alice and consider the situation where Bob and Charlie are allowed to make some errors. But to start with, we need some formal definitions.

Definition 1. A monogamy-of-entanglement game G consists of a finite dimensional Hilbert space ${\cal H}_A$ and a list of measurements $\mathcal {M}^\theta = \{ F_x^{\theta } \}_{x \in \mathcal {X}}$ on a ${\cal H}_A$ , indexed by θ∈Θ, where $\mathcal {X}$ and Θ are finite sets.

We typically use less bulky terminology and simply call G a monogamy game. Note that for any positive integer n, the n-fold parallel repetition of G, denoted as G×n and naturally specified by ${\cal H}_A^{\otimes n}$ and {Fθ1x 1⊗···⊗Fθnxn}x1,...,xn for θ1,...,θn∈Θ, is again a monogamy game.

Definition 2. We define a strategy ${\cal S}$ for a monogamy game G as a list

Equation (3)

where $\rho _{ABC} \in {\cal S}({\cal H}_{A} \otimes {\cal H}_B \otimes {\cal H}_C)$ , and ${\cal H}_B$ and ${\cal H}_C$ are arbitrary finite dimensional Hilbert spaces. Furthermore, for all θ∈Θ, $\{ P^\theta _x \}_{x \in \mathcal {X}}$ and $\{ Q^\theta _x \}_{x \in \mathcal {X}}$ are POVMs on ${\cal H}_B$ and ${\cal H}_C$ , respectively. A strategy is called pure if the state ρABC is pure and all the POVMs are projective.

If ${\cal S}$ is a strategy for game G, then the n-fold parallel repetition of $\cal S$ , which is naturally given, is a particular strategy for the parallel repetition G×n; however, it is important to realize that there exist strategies for G×n that are not of this form. In general, a strategy ${\cal S}_n$ for G×n is given by an arbitrary state $\rho _{{A}_1 \ldots {A}_n {BC}} \in {\cal S}({\cal H}_A^{\otimes n} \otimes {\cal H}_B \otimes {\cal H}_C)$ (with arbitrary ${\cal H}_B$ and ${\cal H}_C$ ) and by arbitrary POVM elements on ${\cal H}_B$ and ${\cal H}_C$ , respectively not necessarily in product form.

The winning probability for a game G and a fixed strategy ${\cal S}$ , denoted by $p_{\mathrm {win}}({\sf G}, {\cal S})$ , is defined as the probability that the measurement outcomes of Alice, Bob and Charlie agree when Alice measures in the basis determined by a randomly chosen θ∈Θ and Bob and Charlie apply their respective POVMs {Pθx}x and {Qθx}x. The optimal winning probability, pwin(G), maximizes the winning probability over all strategies. The following makes this formal.

Definition 3. The winning probability for a monogamy game G and a strategy ${\cal S}$ is defined as

Equation (4)

The optimal winning probability is

Equation (5)

where the supremum is taken over all strategies ${\cal S}$ for G.

In fact, due to a standard purification argument and Neumark's dilation theorem, we can restrict the supremum to pure strategies (cf lemma 9 in appendix A).

3.1. Strong parallel repetition for GBB84

We are particularly interested in the game GBB84 and its parallel repetition G×nBB84. The latter is given by ${\cal H}_A = (\mathbb {C}^2)^{\otimes n}$ and the projectors Fθx = |xθ〉〈xθ| = Hθ1|x1〉〈x1|Hθ1⊗···⊗Hθn|xn〉〈xn|Hθn for θ,x∈{0,1}n. The following is our main result.

Theorem 3 For any $n \in \mathbb {N}$ , n ⩾ 1, we have

Equation (6)

Proof. We first show that this guessing probability can be achieved. For n = 1, consider the following strategy. Bob and Charlie prepare the state $| \phi \rangle := \cos \frac {\pi }{8} | 0 \rangle + \sin \frac {\pi }{8} | 1 \rangle $ and send it to Alice. Then, they guess that Alice measures outcome 0, independent of θ. Formally, this is the strategy ${\cal S}_1 = \big \{ |\phi \rangle \!\langle \phi |, P_x^\theta = \delta _{x0}, Q_x^\theta = \delta _{x0} \big \}$ . The optimal winning probability is thus bounded by the winning probability of this strategy

and the lower bound on pwin implied by equation (6) follows by repeating this simple strategy n times.

To show that this simple strategy is optimal, let us now fix an arbitrary, pure strategy ${\cal S}_n= \{ \rho _{{A}_1 \ldots {A}_n {BC}}, P_x^{\theta },Q_x^{\theta } \}$ . From the definition of the norm, we have tr(MρABC) ⩽ ∥M∥ for any M ⩾ 0. Using this and lemma 2, we find

Equation (7)

where the optimal permutations πk are to be determined later. Hence, the problem is reduced to bounding the norms ∥ΠθΠθ'∥, where θ' = πk(θ). The trivial upper bound on these norms, 1, leads to $p_{\mathrm {win}}({\sf G}_{{\mathrm { BB84}}}^{\times n}, \mathcal {S}_n) \leqslant 1$ . However, most of these norms are actually very small as we see below.

For fixed θ and k, we denote by $\mathcal {T}$ the set of indices where θ and θ' differ, by $\mathcal {T}^{\mathrm {c}}$ its complement, and by t the Hamming distance between θ and θ' (hence, $t = | \mathcal {T} |$ ). We consider the projectors

where $| x^\theta _{\mathcal {T}} \rangle $ is |xθ〉 restricted to the systems corresponding to rounds with index in $\mathcal {T}$ , and $1_{\mathcal {T}^{\mathrm {c}}}$ is the identity on the remaining systems.

Since $\Pi ^\theta \leqslant \bar {P}$ and $\Pi ^{\theta '}\! \leqslant \bar {Q}$ , we can bound $\big \| \Pi ^\theta \Pi ^{\theta '} \big \|^2 \leqslant \big \| \bar {P} \bar {Q} \big \|^{2} = \big \| \bar {P} \bar {Q} \bar {P} \big \|$ using lemma 1. Moreover, it turns out that the operator $\bar {P} \bar {Q} \bar {P}$ has a particularly simple form, namely

where we used that PθxPθz = δxzPθx and $| \langle x_{\mathcal {T}}^\theta | y_{\mathcal {T}}^{\theta '} \rangle |^2 = 2^{-t}$ . The latter relation follows from the fact that the two bases are diagonal to each other on each qubit with index in $\mathcal {T}$ . From this follows directly that $\| \bar {P} \bar {Q} \bar {P} \| = 2^{-t}$ . Hence, we find $\big \| \Pi ^\theta \Pi ^{\theta '} \big \| \leqslant \sqrt {2^{-t}}$ . Note that this bound is independent of the strategy and only depends on the Hamming distance between θ and θ'.

To minimize the upper bound in (7), we should choose permutations πk that produce tuples (θ,θ' = πk(θ)) with the same Hamming distance as this means that the maximization is over a uniform set of elements. A complete mutually orthogonal set of permutations with this property is given by the bitwise XOR, πk(θ) = θk, where we interpret k as an element of {0,1}n. Using this construction, we get exactly (n t) permutations that create pairs with Hamming distance t, and the bound in equation (7) evaluates to

Since this bound applies to all pure strategies, lemma 9 concludes the proof.   □

3.2. Arbitrary games, and imperfect guessing

The above upper-bound techniques can be generalized to an arbitrary monogamy game, G, specified by an arbitrary finite dimensional Hilbert space ${\cal H}_A$ and arbitrary measurements $\{ F_x^{\theta } \}_{x \in \cal X}$ , indexed by θ∈Θ, and with arbitrary finite $\cal X$ and Θ. The only additional parameter relevant for the analysis is the maximal overlap of the measurements

which satisfies $1/| \mathcal {X} | \leqslant c({\sf G}) \leqslant 1$ and c(G×n) = c(G)n. This is in accordance with the definition of the overlap as it appears in entropic uncertainty relations, e.g. in [35]. Note also that in the case of GBB84, we have $c({\sf G}_{{\mathrm {BB84}}}) = \frac {1}{2}$ .

In addition to considering arbitrary monogamy games, we also generalize theorem 3 to the case where Bob and Charlie are not required to guess the outcomes perfectly but are allowed to make some errors. The maximal winning probability in this case is defined as follows, where we employ an argument analogous to lemma 9 in order to restrict to pure strategies.

Definition 4. Let $\mathcal {Q} = \{ ( \pi _B^q, \pi _C^q ) \}_q$ be a set of pairs of permutations of $\mathcal {X}$ , indexed by q, with the meaning that in order to win, Bob and Charlie's respective guesses for x must form a pair in {(πqB(x),πqC(x))}q. Then, the optimal winning probability of G with respect to $\mathcal {Q}$ is

where the supremum is taken over all pure strategies ${\cal S}$ for G.

We find the following upper bound on the guessing probability, generalizing the upper bound on the optimal winning probability established in theorem 3.

Theorem 4. For any positive $n \in \mathbb {N}$ , we have

Recall that in case of GBB84, we have $| \mathcal {Q} | = 1$ , |Θ| = 2, and $c({\sf G}_{{\mathrm {BB84}}}) = \frac {1}{2}$ , leading to the bound stated in theorem 3.

Proof. We closely follow the proof of the upper bound in theorem 3. For any pure strategy ${\cal S}_n = \{ \rho _{{A}_1 \ldots {A}_n {BC}}, P_x^{\theta }, Q_x^{\theta }\}$ , we bound

Equation (8)

where we introduce $A_q^\theta := \sum _{x} \big ( \bigotimes _{\ell =1}^nF_{x_\ell }^{\theta _\ell } \big ) \otimes P_{\pi _B^q(x)}^\theta \otimes Q_{\pi _C^q(x)}^\theta $ . We now fix θ and θ' and bound the norms $\| \sqrt {A_q^\theta } \sqrt {A_q^{\theta '}} \|$ . Let $\mathcal {T}$ be the set of indices where θ and θ' differ. We choose

which satisfy B ⩾ Aθq and C ⩾ Aθ'q. Hence, from lemma 1 we obtain $ \| \sqrt {A_q^\theta } \sqrt {A_q^{\theta '}} \| \leqslant \big \| \sqrt {B}\sqrt {C} \big \|$ . We evaluate

It remains to find suitable permutations πk and substitute the above bound into (8). Again, we choose permutations with the property that the Hamming distance between θ and πk(θ) is the same for all θ∈Θn. It is easy to verify that there are (n t) (|Θ| − 1)t permutations for which the (θ-independent) Hamming distance between θ and πk(θ) is t. Hence

which concludes the proof.   □

One particularly interesting example of the above theorem considers binary measurements, i.e. $\mathcal {X} = \{0,1\}$ , where Alice will accept Bob's and Charlie's answers if and only if they get less than a certain fraction of bits wrong. More precisely, she accepts if d(x,y) ⩽ γn and d(x,z) ⩽ γ' n, where d(·,·) denotes the Hamming distance and y, z are Bob's and Charlie's guesses, respectively. In this case, we introduce the set $\mathcal {Q}_{\gamma ,\gamma '}^n$ that contains all pairs of permutations (πqB,πqC) on {0,1}n of the form πqB(x) = xk, πqC(x) = xk', where q = {k,k'}, and k,k'∈{0,1}n have Hamming weight at most γn and γ'n, respectively. For γ,γ' ⩽ 1/2, one can upper bound $| \mathcal {Q}_{\gamma ,\gamma '}^n | \leqslant 2^{n h(\gamma ) + n h(\gamma ')}$ , where h(·) denotes the binary entropy. We thus find

Equation (9)

Similarly, if we additionally require that Charlie guesses the same string as Bob, we analogously define the corresponding set $\mathcal {Q}_{\gamma }^n$ , with reduced cardinality, and

4. Application I. One-sided device-independent QKD

In the following, we assume some familiarity with QKD. For simplicity, we consider an entanglement-based [20] variant of the BB84 QKD scheme [7], where Bob waits with performing the measurement until Alice tells him the right bases. This protocol is impractical because it requires Bob to store qubits. However, it is well known that security of this impractical version implies security of the original, more practical BB84 QKD scheme [6]. It is straightforward to verify that this implication also holds in the one-sided DI setting we consider here.

The entanglement-based QKD scheme, E-QKD, is described in figure 1. It is (implicitly) parameterized by positive integers 0 < t,s,ℓ < n and a real number $0 \leqslant \gamma < \frac 12$ . Here, n is the number of qubits exchanged between Alice and Bob, t is the size of the sample used for parameter estimation, s is the leakage (in bits) due to error correction, ℓ is the length (in bits) of the final key and γ is the tolerated error in Bob's measurement results. Furthermore, the scheme makes use of a universal2 family $\cal F$ of hash functions F:{0,1}nt → {0,1}.

Figure 1.

Figure 1. An entanglement-based QKD scheme E-QKD.

Standard image High-resolution image

A QKD protocol is called perfectly secure if it either aborts and outputs an empty key, K = ⊥, or it produces a key that is uniformly random and independent of Eve's (quantum and classical) information E+ gathered during the execution of the protocol. Formally, this means that the final state must be of the form $\rho _{KE^+} = \Pr _{\rho }[K\neq \,\perp ] \cdot \mu _K \otimes \rho _{E^+|K\neq \perp } + \Pr _{\rho }[K =\,\perp ] \cdot |\!\!\perp \rangle \!\langle \perp \!\!|_K \otimes \rho _{E^+|K=\perp }$ , where μK is a 2-dimensional completely mixed state, and |⊥〉〈⊥|K is orthogonal to μK.

Relaxing this condition, a protocol is called δ-secure if ρKE+ is δ-close to the above form in trace distance, meaning that ρKE+ satisfies

Equation (10)

It is well known and has been proven in various ways that E-QKD is δ-secure (with small δ) with a suitable choice of parameters, assuming that all quantum operations are correctly performed by Alice and Bob. We now show that the protocol remains secure even if Bob's measurement device behaves arbitrarily and possibly maliciously. The only assumption is that Bob's device does not communicate with Eve after it received Alice's quantum signals. This restriction is clearly necessary as there would otherwise not be any asymmetry between Bob and Eve's information about Alice's key. Note that the scheme is well known to satisfy correctness and robustness; hence, we do not argue these here.

Theorem 5. Consider an execution of E-QKD, with an arbitrary measurement device for Bob. Then, for any ε > 0, protocol E-QKD is δ-secure with

Note that with an optimal error correcting code, the size of the syndrome for large n approaches the Shannon limit s = nh(γ). The security error δ can then be made negligible in n with suitable choices of parameters if log(1/β°) > 2 h(γ), which roughly requires that γ ⩽ 0.015. Hence, the scheme can tolerate a noise level up to 1.5% asymptotically7.

The formal proof is given below. The idea is rather simple. We consider a gedankenexperiment where Eve measures her system, using an arbitrary POVM, with the goal to guess X. The execution of E-QKD then pretty much coincides with G×nBB84, and we can conclude from our results that if Bob's measurement outcome Y is close to X, then Eve must have a hard time in guessing X. Since this holds for any measurement she may perform, this means her min-entropy on X is large and hence the extracted key K is secure.

Proof. Let ρΘTABE = ρΘρT ⊗|ψABE〉〈ψABE| be the state before Alice and Bob perform the measurements on A and B, respectively, where system E is held by the adversary Eve. Here, the random variable Θ contains the choice of basis for the measurement, whereas the random variable T contains the choice of subset on which the strings are compared (see the protocol description in figure 1). Moreover, let ρΘTXY E be the state after Alice and Bob measured, where—for every possible value θ—Alice's measurement is given by the projectors {|xθ〉〈xθ|}x, and Bob's measurement by an arbitrary but fixed POVM {Pθx}x.

As a gedankenexperiment, we consider the scenario where Eve wants to guess the value of Alice's raw key, X. Eve wants to do this during the parameter estimation step of the protocol, exactly after Alice broadcast T but before she broadcasts XT .8 For this purpose, we consider an arbitrary measurement strategy of Eve that aims to guess X. Such a strategy is given by—for every basis choice, θ, and every choice of sample, τ—a POVM {Qθ,τx}x. The values of θ and τ have been broadcast over a public channel, and are hence known to Eve at this point of the protocol. She will thus choose a POVM depending on these values to measure E and use the measurement outcome as her guess.

For our gedankenexperiment, we will use the state, ρΘTXY Z, which is the (purely classical) state that results after Eve applied her measurement on E. Let ε > 0 be an arbitrary constant. By our results from section 3, it follows that for any choices of {Pθx}x and {Qθ,τx}x, we have

with β = 2h(γ+ε)β°, where drel denotes the relative Hamming distance. This uses the fact that Alice's measurement outcome is independent of T, and T can in fact be seen as part of Eve's system for the purpose of the monogamy game.

We now construct a state $\tilde {\rho }_{\Theta T XYE}$ as follows:

where Ω denotes the event Ω = {drel(X,Y ) ⩽ drel(XT ,YT ) + ε}, and we take σTΘXY E to be an arbitrary state with classical Θ, T, X and Y for which drel(X,Y ) = 1, and hence drel(XT ,YT ) = 1. Informally, the event Ω indicates that the relative Hamming distance of the sample strings XT and YT determined by T was representative of the relative Hamming distance between the whole strings, X and Y , and the state $\tilde {\rho }_{\Theta T XYE}$ is so that this is satisfied with certainty. By construction of $ \tilde {\rho }_{\Theta T XYE}$ , we have $\Delta (\rho _{\Theta T XYE}, \tilde {\rho }_{\Theta T XYE})\leqslant 1 - \Pr _{\rho }[\Omega ]$ , and by Hoeffding's inequality:

Moreover, note that the event drel(XT ,YT ) ⩽ γ implies drel(X,Y ) ⩽ γ + ε under $\tilde {\rho }_{\Theta T XYE}$ . Thus, for every choice of strategy {Qθ,τx}x by the eavesdropper, the resulting state $\tilde {\rho }_{\Theta T XYZ}$ , obtained by applying {Qθ,τx}x to E, satisfies

Equation (11)

The second inequality follows from the definition of $\tilde {\rho }$ , in particular the fact that $\Pr _{\sigma } [ d_{\mathrm {rel}}(X,Y) \leqslant \gamma + \varepsilon ] = 0$ .

Next, we introduce the event Γ = {drel(XT ,YT ) ⩽ γ}, which corresponds to the event that Bob does not abort the protocol. Expanding the left-hand side of (11) to $\Pr _{\tilde {\rho }}[\Gamma ] \cdot \Pr _{\tilde {\rho }}[Z \! = \! X | \Gamma ]$ and observing that $\Pr _{\tilde {\rho }}[\Gamma ]$ does not depend on the strategy {Qθ,τx}x, we can conclude that

where α ⩾ 0 is determined by $\Pr _{\tilde {\rho }}[\Gamma ] = \beta ^{\alpha n}$ . Therefore, by definition of the min-entropy, $H_{\mathrm {min}}(X | \Theta T E, \Gamma )_{\tilde {\rho }} \geqslant n (1\!-\!\alpha ) \log (1/\beta )$ . (This notation means that the min-entropy of X given Θ, T and E is evaluated for the state $\tilde {\rho }_{\Theta T X Y E | \Gamma }$ , conditioned on not aborting.) By the chain rule, it now follows that

Equation (12)

Here, the min-entropy is evaluated for the state $\tilde {\rho }_{X \Theta T X_T S E}$ that is constructed from $\tilde {\rho }_{X \Theta T E}$ by calculating the error syndrome and copying XT from X as done in the prescription of the protocol. In particular, $\Delta (\tilde {\rho }_{X \Theta T X_T S E}, \rho _{X \Theta T X_T S E}) \leqslant \mathrm {e}^{-2\varepsilon ^2t}$ . Finally, privacy amplification with universal2 hashing applied to the state $\tilde {\rho }_{X \Theta T X_T S E}$ ensures that the key K satisfies [50, corollary 5.5.2]

And, in particular, recalling that $\Pr _{\tilde {\rho }}[\Gamma ] = \beta ^{\alpha n}$ , we have

Using β = 2h(γ+ε)β° and applying lemma 10 in appendix B concludes the proof.   □

5. Application II. A one-round position-verification scheme

The scheme we consider is the parallel repetition of the simple single-qubit scheme that was analyzed in the setting of no pre-shared entanglement in [12]. The analysis shows that the soundness error of the one-round single-qubit scheme is bounded by roughly 89%, and it is suggested to repeat the scheme sequentially in order to reduce this soundness error. We now show that also the parallel repetition has an exponentially small soundness error9. Finally, we use a simple observation from [3] to argue that the scheme is also secure against adversaries with a linearly bounded amount of entanglement.

The scheme, parameterized by a positive integer n, consists of the following steps.

  • 1.  
    V0 and V1 agree on random x,θ∈{0,1}n. V0 prepares a quantum system Q of n qubits in the state $H^\theta | x \rangle = H^{\theta _1} | x_1 \rangle \otimes \cdots \otimes H^{\theta _n} | x_n \rangle \in {\cal H}_Q = (\mathbb {C}^2)^{\otimes n}$ and sends it to P. V1 sends θ to P, so that both arrive at P's claimed position pos at the same time.
  • 2.  
    As soon as Q and θ arrive, P measures the ith qubit in basis {Hθi|0〉,Hθi|1〉} for i = 1,...,n. Let x'∈{0,1}n collect the observed bits. P sends x' to V0 and V1.
  • 3.  
    If V0 and V1 receive x' at the respective time consistent with pos, and if x' = x, then V0 and V1 accept; otherwise, they reject.

It is straightforward to verify that this protocol is correct, meaning that the verifiers accept honest P at position pos with certainty (assuming a perfect setting with no noise, etc).

Proposition 6 The above position verification scheme is $(\frac {1}{2}\!+\!\frac {1}{2\sqrt {2}})^n$ -sound against adversaries (E0,E1) that hold no entangled state at the time they receive Q and θ, respectively.

We stress that a restriction on the entanglement is necessary, as with unbounded entanglement the general impossibility result from [12] applies. In fact, for the specific scheme considered here, already n shared EPR-pairs are sufficient to break it, as shown in [31]. Below, we will extend the security of the scheme to a setting where the adversaries share at most αn entangled qubits, for any constant α ≲ 0.22.

We also point out that our adversary model (with linearly bounded entanglement) is stronger than the one considered by Beigi and König [3] for their schemes: their model not only prohibits quantum communication between the adversaries before they obtain the initial messages from the verifiers (in order to prevent the exchange of entangled states), but also afterwards. Here, we allow full quantum communication between the adversaries after they have received the initial respective messages Q and θ.

Proof (sketch). As the colluding dishonest parties E0 and E1 share no entanglement, the most general attack is of the following form, where we may assume Ei to be located between Vi and the position pos, for i∈{0,1}. Upon receiving the n-qubit system Q (in state Hθ|x〉) from V0, the adversary E0 applies an isometry ${\cal H}_Q \to {\cal H}_B \otimes {\cal H}_C$ to Q in order to obtain a bipartite system B and C, and forwards C to E1. Adversary E1, upon receiving θ from V1, simply forwards θ to E0.10 Then, when E0 receives θ from E1, he measures B (using an arbitrary measurement that may depend on θ) and sends the measurement outcome x'0∈{0,1}n to V0, and, similarly, when E1 receives system C from E0, he measures C and sends the measurement outcome x'1∈{0,1}n to V1. The probability ε that V0 and V1 accept is then given by the probability that x'0 = x = x'1.

From a standard purification argument it follows that the probability ε does not change if in the first step of the protocol, instead of sending Q in state Hθ|x〉, V0 prepares n EPR pairs, sends one half of each pair toward P and only at some later point in time measures the remaining n qubits in the basis {Hθ|y〉}y∈{0,1}n to obtain x∈{0,1}n.

Let us now consider the state $| \psi _{ABC} \rangle \in {\cal H}_A \otimes {\cal H}_B \otimes {\cal H}_C$ , consisting of system A with the n qubits that V0 kept, and the systems B and C obtained by applying the isometry to the qubits E0 received from V0. Since the isometry is independent of θE0 needs to decide on it before he finds out what θ is—so is the state |ψABC〉. It is clear that in order to pass the position verification test the adversaries must win a restricted version of the game G×nBB84.11 Therefore, the probability ε that x'0 = x = x'1 is bounded by pwin(G×nBB84). Our theorem 3 thus concludes the proof.   □

The security of the position verification scheme can be immediately extended to adversaries that hold a linear amount of shared entanglement.

Corollary 7 The above position verification scheme is $d \cdot (\frac {1}{2}\!+\!\frac {1}{2\sqrt {2}})^n$ -sound against adversaries (E0,E1) that share an arbitrary (possibly entangled) state ηE0E1, such that $\dim \eta _{E_{0} E_{1}} = d$ , at the time they receive Q and θ, respectively.

Thus, for any α strictly smaller than $\log (\frac {1}{2}\!+\!\frac {1}{2\sqrt {2}})$ , for instance for α = 0.2, the position verification scheme has exponentially small soundness error (in n) against adversaries that hold at most αn pre-shared entangled qubits.

Corollary 7 is an immediate consequence of proposition 6 above and of lemma V.3 of [3]. The latter states that ε-soundness with no entanglement implies (dε)-soundness for adversaries that pre-share a d-dimensional state. This follows immediately from the fact that the pre-shared state can be extended to a basis of the d-dimensional state space, and the uniform mixture of all these basis states gives a non-entangled state (namely the completely mixed state). As a consequence, applying the attack, which is based on the entangled state, to the setting with no entanglement, reduces the success probability by at most a factor of d.

By the results on imperfect guessing (see section 3.2), at the price of correspondingly weaker parameters, the above results extend to a noise-tolerant version of the scheme, where it is sufficient for x' to be close, rather than equal, to x for V0 and V1 to accept.

6. Application III. Entropic uncertainty relation

Let ρ be an arbitrary state of a qubit and Θ a uniformly random bit. Then, we may consider the min-entropy of X, where X is the outcome when ρ is measured in either one of two bases with overlap c, as determined by Θ. For this example, it is known that [18, 52]

Equation (13)

A similar relation follows directly from results by Maassen and Uffink [41], namely

Equation (14)

where $H_{\max }$ denotes the Rényi entropy [51] of order $\frac {1}{2}$ .

Recently, entropic uncertainty relations have been generalized to the case where the party guessing X has access to quantum side information [8]. However, note that a party that is maximally entangled with the state of the system to be measured can always guess the outcome of X by applying an appropriate measurement (depending on Θ) on the entangled state. Thus, there cannot be any non-trivial state-independent bound on the entropies above conditioned on quantum side information. Nonetheless, if two disjoint quantum memories are considered, the following generalization of (14) was shown. For an arbitrary tripartite state ρABC and X measured on A as prescribed above, one finds [60]

Equation (15)

In the following, we show a similar generalization of the uncertainty relation in (13) to quantum side information.

Theorem 8 Let ρABC be a quantum state and Θ a uniformly random bit. Given two POVMs {F0x} and {F1x} with overlap $c := \max _{x, z} \big \| \sqrt {F_{x}^{0}} \sqrt {F_{z}^{1}} \big \|^{2}$ , we find

and

where the quantities are evaluated for the post-measurement state

Equation (16)

Proof. First, recall that the min-entropy is defined as (cf equation (2))

where we used the fact that the post-measurement states given by (16) satisfy $p_{x,\theta }\, \rho _{BC}^{x,\theta } = \frac {1}{2} \mathrm {tr}_{{A}} \big ( F_x^{\theta } \rho _{ABC} \big )$ .

In the following argument, we restrict ourselves to the case where the optimal guessing strategies for the min-entropy, {Pθx} for Bob and {Qθx} for Charlie, are projective. To see that this is sufficient, note that we can always embed the state ρXBC into a larger system ρXB'C' such that the optimal POVMs on B and C can be diluted into an equivalent projective measurement strategy on B' and C', respectively. The data-processing inequality of the min-entropy then tells us that $H_{\min }(X|B\Theta ) \geqslant H_{\min }(X|B'\Theta )$ and $H_{\min }(X|C\Theta ) \geqslant H_{\min }(X|C'\Theta )$ , i.e. it is sufficient to find a lower bound on the smaller quantities, for which the optimal strategy is projective.

For an arbitrary state ρABC and optimal projective POVMs {Pθx} and {Qθx}, we have

We now upper-bound this norm. First, we rewrite

where $A_0^{\theta } = \sum _x F_x^{\theta } \otimes P_x^{\theta } \otimes 1_C$ and $A_1^{\theta } = \sum _x F_x^{\theta } \otimes 1_{B} \otimes Q_x^{\theta }$ are projectors. Applying lemma 2 twice then yields

where we used that ∥Aθi∥ ⩽ 1. Hence,

and, using the relation between arithmetic and geometric mean, we finally get

which implies the statement of the lemma after taking the logarithm on both sides.   □

Note that, for n measurements, each in a basis chosen uniformly at random, the above result still only guarantees one bit of uncertainty. In fact, an adaptation of the proof of theorem 8 yields the bound

This bound can be approximately achieved using a state that is maximally entangled between A and B with probability $\frac {1}{2}$ and maximally entangled between A and C otherwise. This construction ensures that both conditional min-entropies are low and we thus cannot expect a stronger result. This is in stark contrast to the situation with classical side information in (13) and the alternative uncertainty relation (15), where the lower bound on the uncertainty can be shown to scale linearly in n (cf [60, 62]). Due to this restriction, we expect that the applicability of theorem 8 to quantum cryptography is limited.

7. Conclusion

We introduce the notion of a monogamy-of-entanglement game, and we show a general parallel repetition theorem. For a BB84-based example game, we actually show strong parallel repetition, and that a non-entangled strategy is sufficient to achieve the optimal winning probability. Our results have various applications to quantum cryptography.

It remains open to understand which monogamy-of-entanglement games satisfy strong parallel repetition. Another open question is whether (or in what cases) a concentration theorem holds, which states that with high probability the fraction of won executions in a parallel repetition cannot be much larger than the probability of winning a single execution.

With respect to our applications, an interesting open problem is to increase the noise level that can be tolerated for one-sided DI security of BB84. It is not clear at all that the rather low noise level of 1.5% we obtain in our analysis is inherent; this may very well be an artifact of our technique. Finally, it would be interesting to extend our analysis to incorporate channel losses following the work of Branciard et al [9]. As suggested there, we expect that such an analysis would reveal a higher tolerance for losses as compared to fully DI QKD.

Acknowledgments

We thank Renato Renner for early discussions and Niek J Bouman for bringing this problem to the attention of some of us. MT, JK and SW are funded by the Ministry of Education (MOE) and National Research Foundation Singapore, as well as MOE Tier 3 Grant 'Random numbers from quantum processes' (MOE2012-T3-1-009).

Appendix A.: Pure strategies are sufficient

Lemma 9 In the supremum over strategies in (5), it is sufficient to consider pure strategies.

Proof. Given any strategy ${\cal S} = \{\rho _{ABC}, P_x^{\theta }, Q_x^{\theta } \}$ for a game G, we construct a pure strategy $\tilde {\cal S} = \{|\tilde {\varphi } \rangle \!\langle \tilde {\varphi } |, \tilde {P}_x^{\theta }, \tilde {Q}_x^{\theta } \}$ with $p_{\mathrm {win}}({\sf G}, \tilde {\cal S}) = p_{\mathrm {win}}({\sf G}, {\cal S})$ . First, it is clear that purifying ρABC, with a purifying register that is appended to C, does not change the value of $p_{\mathrm {win}}({\sf G}, {\cal S})$ . Hence, we may assume that ρABC is already pure: ρABC = |φ〉〈φ|. In this case, $p_{\mathrm {win}}({\sf G}, {\cal S})$ simplifies to

Let ${\cal H}_X$ be a Hilbert space of dimension $|\mathcal {X}|$ and with basis {|x〉}x, and let |ψ0〉 be an arbitrary, fixed vector in ${\cal H}_X$ . We now set $| \tilde {\varphi } \rangle = | \varphi \rangle \otimes | \psi _0 \rangle \in {\cal H}_A \otimes {\cal H}_B \otimes {\cal H}_C \otimes {\cal H}_X$ as well as $\tilde {P}_x^{\theta } = U_\theta ^\dagger (1_B \otimes |x \rangle \!\langle x |) U_\theta $ , where $U_\theta \in \mathcal {L}({\cal H}_B \otimes {\cal H}_X)$ is a Neumark dilation unitary that maps

for every $| \psi \rangle \in {\cal H}_B$ . Then, $\tilde {P}_x^{\theta }$ is indeed a projection and hence $\tilde {P}_x^{\theta } = (\tilde {P}_x^{\theta })^\dagger \tilde {P}_x^{\theta }$ , and 12

Similarly, we define the projection $\tilde {Q}_x^{\theta }$ (and extend the state $| \tilde {\varphi } \rangle $ ). It then follows immediately that $p_{\mathrm {win}}({\sf G}, \tilde {\cal S}) = p_{\mathrm {win}}({\sf G}, {\cal S})$ .   □

Appendix B.: Equivalence of QKD security definitions

To prove security of a protocol, it is sufficient to show that the security criterion is satisfied by a state close to the true output state of the protocol. This is due to the following lemma.

Lemma 10 Let $\rho _{XB},\, \tilde {\rho }_{XB} \in {\cal S}({\cal H}_X \otimes {\cal H}_B)$ be two CQ states with X over $\cal X$ . Also, let $\lambda : {\cal X} \to \{0,1\}$ be a predicate on $\cal X$ and Λ = λ(X), and let $\tau _X \in {\cal S}({\cal H}_X)$ be arbitrary. Then

Proof. We set $\delta := \Delta (\rho _{XB}, \tilde {\rho }_{XB})$ . From $\Delta (\rho _{XB}, \tilde {\rho }_{XB}) = \delta $ it follows in particular that the two distributions PX and $\tilde {P}_X$ are δ-close, and thus that the state

is δ-close to $\tilde {\rho }_{XB}$ , and hence 2δ-close to ρXB, where ¬Λ is the negation of the event Λ. Since Λ is determined by X, we can write

from which it follows that $\Pr _{\rho }[\Lambda ] \cdot \Delta (\rho _{XB|\Lambda }, \,\tilde {\rho }_{XB|\Lambda }) \leqslant 2 \delta $ , and, by tracing out X, also that $\Pr _{\rho }[\Lambda ] \cdot \Delta (\rho _{B|\Lambda },\tilde {\rho }_{B|\Lambda }) \leqslant 2 \delta $ . We can now conclude that

which proves the claim.   □

Footnotes

  • For example, this follows from a proof of an entropic uncertainty relation by Deutsch [18].

  • However, neither the techniques from [14] nor from [15] work for parallel repetitions.

  • There, the protocol of [59] was amended to account for photon losses.

  • This can be improved slightly by instead considering a six-state protocol [11], where the measurement is randomly chosen among three mutually unbiased bases on the qubit.

  • Note that the effect of Eve learning XT is taken into account later, in equation (12).

  • We stress that this was to be expected and does not come as a surprise. However, until now it was unclear how to prove it.

  • 10 

    This is where the restriction of no entanglement comes into play. If the adversaries shared entanglement their most general strategy would be to perform some joint operation on the respective part of the entangled state and the data they have just received. The impossibility result states that in a scenario with an unlimited amount of entanglement no position verification scheme can be secure.

  • 11 

    The extra restriction comes from the fact that they have no access to the qubits kept by V0 and so the reduced state on those must be fully mixed. It turns out that this restriction does not affect the optimal winning probability.

  • 12 

    It is implicitly understood that $\tilde {P}_x^{\theta }$ only acts on the BX part of $| \tilde {\varphi } \rangle $ , and similarly for Uθ, etc.

Please wait… references are loading.