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.