Although in general optimization over quantum strategies is intractable, good upper bounds can often be obtained by considering convex relaxations of the set of valid quantum strategies for the players (using e.g. semidefinite programming). Here the game is sufficiently simple that an intuitive argument can be given which already provides a meaningful bound.

Proof. For simplicity, we start by showing that when η = 0, then Bob cannot guess Alice’s output with probability 1. A more careful accounting of the parameters then provides the claimed bound. Note that is the maximum probability with which Alice and Bob can succeed in the augmented CHSH game—for this to happen they must win the CHSH game with optimal probability ω, and on inputs x = 2 and y = 0, the outputs a and b must be equal. We assume for contradiction that Bob can guess Alice’s output (on input x = 2) with probability 1.

We imagine repeated sequential execution of the devices, with the same fixed inputs x and y, for some number k of executions. Let , denote Bob’s outputs, and denote Alice’s outputs, over these k executions. Then the condition on the augmented CHSH game implies that the players’ outputs should match when the inputs are (x, y) = ( 2, 0): . Also by the assumption of successful guessing, on inputs ( 2, y) for any y the players’ outputs satisfy . It follows that . The fact that Alice and Bob win the CHSH game with probability ω implies that for any x ∈ {0, 1}, the relative Hamming distance (by the Chernoff bound this is sharply concentrated as k grow). It follows that .

Now suppose Alice knew Bob’s output (we will justify this assumption later). We claim that this gives Alice an advantage in guessing Bob’s input y thus providing a contradiction with the elementary guessing game described at the start of the section. Alice’s strategy is as follows: if given her input x and output , she guesses y = 0 if , and y = 1 otherwise, where ε is an arbitrarily small constant (depending on k).

First note that if y = 0 then she succeeds with probability close to 1. This is because as shown above, since , for any . On the other hand, when y = 1, by the CHSH game condition it should be the case that and . By the triangle inequality, . It follows that and cannot both be close to any fixed : i.e. both conditions and cannot be simultaneously satisfied. This means that in the case y = 1, Alice must succeed with probability about 1/2, and therefore overall Alice can guess Bob’s output with probability close to 3/4. Contradiction.

To justify the assumption that Alice knows Bob’s output
Bob always chooses the same secret input y. Bob select a value
uniformly at random and post-selects on those chunks
where . He communicates the indices of those chunks
to Alice. The information this leaks about y is very small, since
the marginal distribution of must match the marginal dis-
tribution obtained when DA is provided input x = 2, which
does not depend on y; as a consequence the indices of the
with a third input, labeled 2 (each input is chosen with prob-
ability 1/3). If inputs to the players are (x, y) = ( 2, 0) then their
outputs should match. Assuming the no-signaling principle
and the validity of quantum mechanics (specifically, that ω =
cos2 π/8 is the optimal bound in the CHSH game), it is easy to
see that Alice and Bob can win the augmented CHSH game
with probability , which is optimal.

Now we consider adding one more rule to the game, the “guessing rule”: Bob should always produce a second output, c ∈ {0, 1}. The guessing rule requires that c should match Alice’s output a whenever her input is x = 2 (if x ∈ {0, 1} then there is no requirement on c). We will show that Alice and Bob cannot achieve close to the optimal probability of in the extended CHSH game, and simultaneously satisfy the guessing rule on Bob’s output c with probability close to 1: whatever Bob does, he cannot collaborate with Alice to succeed in the CHSH game, while simultaneously producing a valid guess for her output. This is a manifestation of the phenomenon of monogamy of quantum correlations alluded to earlier. To understand the significance of this result for the security of protocol E1, note that it also implies that Alice’s output bit must look somewhat random to the eavesdropper, even when provided with Alice and Bob’s inputs. To see this, observe that any such eavesdropper could be lumped together with Bob to derive a successful strategy in the guessing game described above.

The proof is in the form of a reduction to the following trivial guessing game. There are two cooperating players, Alice and Bob. At the start of the game, Bob receives a single bit y ∈ {0, 1} chosen uniformly at random. The players are then allowed to perform arbitrary computations, but are not allowed to communicate. At the end of the game, Alice outputs a bit a, and the players win if a = y. Clearly, any strategy with success probability that deviates from indicates a violation of the no-signaling assumption between Alice and Bob. The idea behind the use of guessing games is to show that any undesirable outcome in the cryptographic protocol—such as a successful strategy for the Eavesdropper—can be bootstrapped into a successful strategy for Alice and Bob in the trivial guessing game, thereby contradicting the no-signaling assumption.

Guessing lemma. Suppose that Alice and Bob succeed in the augmented CHSH game with probability at least , where . Then the maximum probability with which Bob can successfully guess Alice’s output on input x = 2 is at most 1 − C(η0 − η), where C and η0 are universal constants.

c1 a1a0

 

≤ 1 − ω

≈ 0.15

≥ 2( 1 – ω) ≈ 0.7

Figure 5. The proof of the guessing lemma. Using the winning condition for the CHSH game, wherever b1 is the distance between a0 and a1 must be at least 2( 1 – ω). This implies the balls of radius ( 1 – ω) centered are a0 and a1 are disjoint.