the protocol. Otherwise they proceed to the extraction phase.
For this they exchange their inputs in all rounds and discard
rounds in which the inputs were not (xi, yi) = ( 2, 0). Outputs
from the remaining rounds, called the check rounds C, are
kept private by each user and designated as the raw key, KA and
KB respectively. Based on these strings the users perform post-processing steps of error reconciliation and privacy amplification to obtain the final shared key K. Information reconciliation
is a procedure, based on error-correcting codes, which aims to
ensure that KA = KB after a small correction performed publicly.
We will not discuss this standard procedure here. The goal of
privacy amplification is to amplify the secrecy present in the
raw key, from partially unknown to the Eavesdropper, to
indistinguishable from uniform from the point of view of the
Eavesdropper. We will describe this procedure in detail later.
The most important point of departure from Ekert’s protocol lies in the small fraction γ of rounds in which the CHSH
game correlations are tested. Skimping on testing may appear
to weaken the security of the protocol: why not use all possible
correlations for the test? On the other hand, testing involves
publicly revealing the input/output pairs for those rounds, and
this runs the risk of dishonest devices leaking information to
the eavesdropper. Indeed, as we will see the proof of security
of the protocol will require us to set a small, constant upper
bound on the fraction γ of rounds selected for testing.
We formalize the intuition underlying protocol E1 in terms
of two concepts, neither of which had been clearly formulated
at the time of Ekert’s paper. The first is known as rigidity. This
is the observation that there is an essentially unique way to
achieve the optimal success probability of cos2 π/8 in the CHSH
game: any optimal strategy for the devices DA and DB in the game
is locally equivalent to the specific strategy based on the Bell
state described earlier. The second concept is the monogamy
of correlations. This idea builds on the first by stating that maximally entangled qubits are necessarily pure, thus cannot share
their “maximally entangled degrees of freedom” with any other
qubits. It is a formalization of Ekert’s intuition that, by witnessing correlations that certify that their devices share a Bell state,
the users effectively preclude the possibility of entanglement
between the devices and any malicious eavesdropper.
One possible approach to a formal proof of security of the
protocol would be to give a quantitative formulation of both
concepts. While this can be done within the mathematical
formalism of quantum mechanics, there are strong impediments to the use of the resulting theory for proving security
in any practically meaningful sense. First of all, achieving
device independence prevents us from making any a priori
assumption on the quantum systems used, such as a bound
on the dimension of the underlying Hilbert space. Without
such bound it is not a priori obvious how the distance to the
optimal strategy scales as a function of the deviation from
optimality of the statistics observed, a difficulty already
faced by Mayers and Yao.
22 More importantly, the interaction
scenario which takes places in the QKD protocol is complex
and involves multiple sources of information leaked to the
eavesdropper. While a proof of security along these lines was
given in Ref. Reichardt et al.,
27 the bounds obtained are too
weak to tolerate any errors in the execution of the protocol
(such as unavoidable photon losses, false detection events, etc).
4. OVERVIEW OF PROOF OF SECURITY
The proof of security can be decomposed into two parts. The
first analyzes a single randomly chosen round of the protocol. It
shows that if the protocol succeeds, then with high probability
the devices’ output in the chosen round must be at least partially
unknown to the Eavesdropper. To do so, the challenge faced by
the Eavesdropper is formulated in terms of a two player guessing
game, and the information of the Eavesdropper is bounded by
means of a reduction to a trivial guessing game. The maximum
success probability in the latter game is bounded by virtue of the
no-signaling principle, that is, in the absence of communication
between the two players, the output distribution of one player
must be independent of the other player’s input. This part of the
proof does not resort to the quantum formalism at all (though
doing so can be used to give stronger quantitative bounds).
The second part of the proof shows that over a large number
N of rounds, the protocol yields Ω(N) bits of shared random key
that are secure against the eavesdropper. Analyzing multiple
rounds of the protocol runs into fundamental obstacles having to do with the quantum nature of the Eavesdropper and
her attack. Ideally we would like to associate the extraction of
fewer than Ω(N) bits of shared random key with the failure of
the guessing game argument in some round, resulting in a contradiction. The issue is that the Eavesdropper’s attack could
be a global measurement on her part of the quantum state
based on the classical information exchanged in all rounds
of the protocol, leading to a loss of control over the sequential
nature of the protocol. 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.
Roughly, this paradigm allows us to directly conclude that if
the key generated by the protocol 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 perform a reduction to the guessing game.
5. GUESSING GAMES
At its heart the security guarantees provided by a single round of
protocol E1 hinge on the following guessing game (Figure 4).
We start with an augmented variant of the CHSH game, where
in addition to the CHSH game inputs Alice can be provided
DA DB
xy
a b, c
(i) a⊕b=x∧y?
(ii) x= 2⇒c=a?
Figure 4. The guessing game. Any devices satisfying both the CHSH
condition a ⊕ b = xy and the guessing condition c = a with high
enough probability must allow signaling between DA and DB.