chunks sent by Bob to Alice are close to uniformly distributed,
irrespective of y.
This concludes the proof for the case of η = 0. It is not difficult to reproduce the same proof to make the reasoning
more quantitative in the more general case that η > 0. We
leave this as an exercise to the reader.
Before continuing with the multi-round analysis, we note
that the guessing lemma already gives an “in principle”
proof of security for quantum key distribution, following an
argument due to Barrett et al.
4 (though they used a different,
more complex Bell inequality to achieve a security parameter
that scales inverse proportionally to the number of rounds).
Consider the following simplified variant of Protocol E1.
The users instruct their devices to sequentially play Θ(N)
instances of the augmented the CHSH game. Alice chooses
a random time at which to stop the games, and announces it
(publicly) to Bob. The users publicly exchange their inputs.
Once this has been done, they determine the last round,
prior to the stopping time, where they used the input pair
( 2, 0), and should thus have matching outputs; call this the
key round. They exchange their outputs in all rounds prior
to the key round and estimate the (augmented) CHSH game
correlations. Provided these correlations come close enough
to the CHSH game bound they use their output in the key
round for the final key. Based on a simple martingale argument it is not hard to show that, conditioned on the devices
producing outputs that satisfy the CHSH game correlations
in all rounds prior to the key round, the devices in the key
round have a high probability of satisfying the CHSH game
condition as well (even if it is not checked). Using the guessing lemma it must be that, in that round, the eavesdropper
has a bounded probability of guessing the users’ shared bit.
Note that the above argument provides a complete proof of
security (for a single bit of key), without having to resort to the
quantum formalism at all: the only assumption needed for
security is the no-signaling principle. Going beyond a single
round, however, will require us to assume in addition that the
devices’ behavior can be modeled using quantum mechanics.
6. EXTRACTING A SECURE KEY
We proceed to analyze the complete protocold. Our goal is
to provide a reduction: we aim to show that any global strategy for the Eavesdropper that yields even partial information about the users’ final shared key implies an attack on
a single round of the protocol of the form described, and
ruled out, in the previous section. As mentioned earlier,
analyzing multiple rounds of the protocol runs into fundamental obstacles having to do with the quantum nature of
the Eavesdropper and her attack. We will get around these
obstacles by appealing to powerful results from the theory
of randomness extractors to directly deal with correlations
between the classical information generated by Alice, Bob
and the Eavesdropper.
The first step is to formalize exactly what constitutes a
strategy for the Eavesdropper. Recall that protocol E1 includes
an ultimate post-processing step called privacy amplification. This task converts the raw key K shared by Alice and Bob
(which they derived from KA and KB by performing information
reconciliation) into a shorter string Z. Privacy amplification
guarantees that as long as K contains enough entropy from
the viewpoint of the Eavesdropper, Z is indistinguishable
from uniform, again from the Eavesdropper’s point of view.
Privacy amplification is achieved by using a strong (
quantum-proof) randomness extractor:
12, 32 a procedure Ext which takes
two strings of bits as input, the source X (whose role will be
played by K) and a short uniformly random seed Y (that will be
generated using private randomness, and shared publicly),
and combines them to produce an output Z = Ext(X, Y). Think
of the seed as a short tag used to select a hash function from
a publicly specified family; the output is given by the evaluation of the chosen hash function on the source. The security
condition for a strong extractor guarantees that no adversary,
even given access to the seed, is able to distinguish the output
of the extractor from a uniformly random string of the same
length. This guarantee will be met, provided the source contains enough entropy from the viewpoint of the adversary.
The major challenge thus remains to establish that the
source, K, contains enough entropy from the viewpoint of
the Eavesdropper. Our approach to showing this is based on (the
quantum generalization of) a proof technique from the theory
of pseudo-randomness called the “reconstruction paradigm,”
originally introduced by Trevisan33 towards the analysis of a
class of strong randomness extractors. Roughly, this paradigm
allows us to make a stronger statement than the generic
strong extractor reduction sketched above: it allows us to
show directly that if the key generated by the protocol (after
privacy amplification) is distinguishable from random by the
eavesdropper, then there is an (efficient) classical procedure
to reconstruct Alice’s raw key with non-negligible probability. This allows us to use classical information-theoretic tools
to complete a reduction to the guessing game.
6. 1. Global attacks
Before delving into more details about the reconstruction
paradigm, we first review some of the difficulties to be overcome by the analysis.
Recall that the main difference introduced in protocol E1
compared to Ekert’s protocol is the presence of only a small
fraction of test rounds. The following simple attack demonstrates that the restriction is necessary for security. Note that
Alice’s device DA is able to distinguish key rounds from test
rounds, since it is given a special input, 2, for the former type
of round. Suppose the eavesdropper programs DA in a way that
the device systematically outputs any bit on which its input is
x = 2 twice: in the key round, as required, as well as in the round
that immediately follows. Assuming there are comparatively few
key rounds, it is likely that the second round will be a test round.
The devices will probably fail the CHSH game condition in that
round, but provided there are sufficiently many test rounds the
effect on their average success probability will remain small.
But outputs in test rounds are publicly exchanged by the users:
the complete raw key is leaked to the Eavesdropper! This
d The appropriate notion of entropy is the quantum conditional minentro-
py, which has an operational interpretation: it is simply the maximum prob-
ability with which the Eavesdropper can successfully make a correct guess
for the complete string K, by performing an arbitrary measurement on her
quantum side information.
