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.