APRIL 2019 | VOL. 62 | NO. 4 | COMMUNICATIONS OF THE ACM 141 is on the event that the adversary’s guesses in rounds prior to i0 are correct. The guesses in turn depend on the choice of inputs (x, y) that were “hard-wired” into the adversary as part of the reduction described above. Thus correctness of the adversary’s guesses can bias the distribution of inputs in round i0, which is no longer uniform and may be jointly correlated with the state of the devices and . For example, it could be that the inputs in a fixed round i0 are forced to a specific choice such as (0, 0), making the guarantee (i) all but useless (if the inputs are fixed, it is easy to win the CHSH game). This difficulty is similar to one encountered in the analysis of the parallel repetition of multiplayer games. The standard approach for this problem was introduced in work of Raz26 showing a parallel repetition theorem for the value of classical two-player games. The main idea consists in arguing that conditioning on an event with large enough probability cannot introduce strong correlations in all, or even most, coordinates of a distribution that is initially in product form. At a technical level, the analysis uses the chain rule for mutual information and Pinsker’s inequality.

In our scenario a very similar approach can be employed to show that conditioning on the adversary’s success, provided success happens with large enough probability, cannot bias the users’ input distribution in most rounds by too much. This uses that initially (before the conditioning) the distribution is a product distribution, sampled independently in each of the large number of rounds of the protocol.

Unfortunately this statement is not sufficient for our purposes. We need to show, not only that the inputs to the devices in the round i0 are close to uniformly random, but also that the post-measurement state of the devices ( conditioned on the same success event) is not correlated to the users’ choice of input. To show that this cannot happen we expand on Raz’ technique by introducing a coding argument to deal with the quantum correlations. Assume for contradiction that the devices’ state has a non-trivial correlation with their input (after a successful guess of the eavesdropper), and that this holds in most rounds. We show that such devices, including the eavesdropper’s strategy, could be used to transmit classical information from Bob and the eavesdropper to Alice at a more efficient rate than is allowed by standard arguments from quantum information theory, thereby reaching a contradiction. For a further discussion of this step we refer to previous work of the authors. 35

7. OUTLOOK

From their origins in the EPR thought experiment, through
their formulation in Bell’s work and the CHSH test, to their
use in device-independent cryptography, the non-local corre-
lations of quantum mechanics have gone from undesirable
paradox to operationally desirable certificates, not only of
quantumness but also of randomness and privacy.f
Our proof of security inscribes itself in a long sequence of
works demonstrating progressively stronger uses of quantum
that Eve is unable to produce a correct guess for the sub-string
aC, where C contains those rounds in which (xi, yi) = ( 2, 0), with
non-negligible probability.

To show this we perform a reduction to the single-round guessing game. We seek to identify a round i0 ∈ { 1, . . ., N} such that the following holds. Let and denote the state of Alice and Bob’s devices at the beginning of round i0, conditioned on all past events. This includes fixing values for all prior input and output bits, and making those values available to the three players. It should then be the case that (i) the devices and have a large success probability in the augmented CHSH game, when provided uniformly random inputs (x, y) ∈ {0, 1, 2} × {0, 1}, and (ii) Eve has a strategy which allows her to produce a correct guess for the output a obtained by , when given the input x = 2, with high probability. If both conditions can be shown to hold simultaneously, the single-round guessing lemma, Lemma 1, will give a contraction.

As explained earlier, the main difficulty in completing the reduction is that the adversary’s attack in the original, multi-round protocol is based on a global measurement on her side information, which includes the classical information gleaned throughout the protocol, as well as her initial quantum state. The application of the quantum reconstruction paradigm dispenses with the need to deal with the adversary’s quantum state at the expense of providing her with a small number of advice bits. We separate this information in two parts: first, the users’ input strings (x, y). Second, the user’s outputs (aB, bB) in test rounds, and the advice bits g(aC). This second part of the information can be handled using a standard trick: instead of waiting for the bits to be available, we modify the adversary into one which makes a uniformly random choice for them. Using that the number of rounds used as checks is small compared to |C|, her success probability remains non-negligible.

The other part of the side information, the inputs (x, y), cannot be eliminated in the same way, as it contains too many bits. We can split the inputs in two parts: those to be chosen before round i0, and those chosen after. The inputs chosen before round i0 will be made publicly available as part of the specification of the devices and , so there is no need to worry about them. Regarding the inputs to be chosen after round i0, it is enough to argue that a “good” choice of inputs exist: indeed, the device’s output in round i 0 cannot depend on inputs provided to the device after round i0; here the sequential nature of the protocol is used in an important way.

Now that we have a single, fixed measurement for the adversary, with hard-wired values for (x, y) and the advice bits, we are finally in a position to apply the (classical!) Bayes’ rule in order to identify the round i0 satisfying conditions (i) and (ii). This provides the following straightforward implication: ( 1)

for some small constant δ > 0.

The conditioning implied by Bayes’ rule, however, presents
a last difficulty: it may introduce correlations between the state
of the devices at the beginning of the i0-th round, and the inputs
that the devices “expect” in that round. Indeed, the conditioning
f Note that the conditioning is performed jointly on an event involving Alice and
Bob (the CHSH violation observed in previous rounds being sufficiently large)
on the one hand, and Bob and Eve (Eve’s guess being correct) on the other, so
it can certainly introduce correlations across the whole input distribution.