randomness extractors (extremal objects from the computational complexity-based theory of pseudorandomness) and their quantum-proof extensions to bypass obstacles, such as the absence of a suitable Bayes’ rule more specifically, for analyzing quantum protocols generating multiple bits. Building upon previous work on certifiable quantum random number generation, 34 the proof of security uses an extraction-based proof technique called the “quantum reconstruction paradigm” to perform a reduction from global attacks of the Eavesdropper to attacks on a single round of the protocol. This component of the proof should be of broad interest to complexity theorists interested in randomness extractors and multi-player games, and the exposition tries to make these aspects accessible.

The second component of the proof rules out single-round attacks by the Eavesdropper. This involves arguing that any such attack would imply an impossibly good strategy for three players involved in a simple non-local “guessing game,” that would contradict the non-signaling principle. The proof takes the form of a reduction between guessing games, and may be particularly relevant to cryptographers in view of the recent interest in the properties of no-signaling distributions in the context of delegated computation. 19

Our security proof operates within a considerable generalization of the framework of Bell experiments that encompasses the study of correlations between the outputs of three quantum devices (the third device being used to model an Eavesdropper to the protocol) involved in a complex interaction which includes some limited communication between the devices. This generalization captures new physical phenomena, such as the monogamy of entanglement mentioned earlier. In our exposition we aim to abstract as much of the quantum formalism as possible by taking the point of view of classical users in the protocol, thereby also highlighting the classically understandable elements of the proof of security while postponing as far as possible any knowledge about the quantum formalism required to provide a low-level modeling of the quantum devices used.

To achieve device independent security in an experiment, it suffices to implement devices that can carry out the honest party’s protocol with sufficient fidelity that their input-output behavior passes the statistical test specified in the protocol. This is in contrast to traditional security proofs that require e.g. a device that is guaranteed to emit a single qubit at a time, a criterion that cannot be verified based on statistical data. The recent experimental demonstrations of Bell tests reproducing the desired correlations even under stringent adversarial assumptions (so-called “loophole-free”) 5, 18, 30 make it a near-certainty that device-independent protocols for QKD will soon be realized. An even bigger canvas for such experiments is provided by the recent demonstration of the feasibility of distributing entangled qubits from satellite to distant ground stations. 36 These are exciting times for quantum cryptography!

2. QUANTUM STATES, ENTANGLEMENT
AND THE CHSH GAME

The qubit is the fundamental unit of quantum information.
For our purposes it suffices to consider the following sim-
plified definition: a qubit is a particle that can be in a real
In pioneering work in the 1960s (see Bell6) the physicist
John Bell showed that suitable measurements on the two
qubits in a Bell state generate correlations between their
outputs that cannot be reproduced by non-communicating
classical devices. Such non-local correlations provide a “test
of quantumness,” one that distinguishes quantum mechan-
ics from the kinds of hidden variable theories that Einstein
championed. Non-local correlations of this form have been
been experimentally verified to exquisite precision in the
form of Bell inequality violations. 15, 18, 30

The simplest example of a Bell experiment was discovered by Clauser et al. 9 The experiment can be formulated as a game, the CHSH game, named after its inventors Clauser, Horne, Shimony, and Holt that plays an essential role in our protocol. In this game, devices DA and DB are given as input uniformly random bits, x and y respectively. Their goal is to return bits, a and b respectively, such that xy = a ⊕ b. An easy argument shows that if DA and DB are classical, that is, each device’s output is computed as a function of the device’s input only, they cannot succeed with probability greater than 3/4, even if the devices are allowed to access a common shared random string. By contrast, if DA and DB are quantum, each containing one qubit of a Bell state, then by performing suitable quantum measurements on their qubits they can achieve a success probability of cos2 π/8 ≈ 0.85 > 3/4.

The importance of non-local correlations for device independence lies in the intuition that under certain conditions these correlations, which can be tested classically via a Bell experiment, can pin down the entangled state shared by the two devices—a phenomenon known as rigidity—as well as preclude entanglement with a third party such as the Eavesdropper—a phenomenon known as monogamy. Unfortunately, beyond its intuitive formulation monogamy is notoriously difficult to quantify, and this has been one of the main obstacles to a formal proof of security in the device-independent framework.

A significant step was taken by Barrett et al., 5 who were able to show security of a protocol generating a single bit of key based only on the no-signaling assumption that no information is exchanged between the users’ devices, or between the devices and the eavesdropper. This is a weaker assumption than the quantum formalism, which implies non-signaling but is generally more restrictive. Their work inspired a large number of follo w-up papers1, 2, 29 which sought security for protocols generating multiple bits, and attempted to leverage the quantum formalism to obtain a more fine-grained security analysis, leading to potential improvements in key rates. Unfortunately all these attempts ran into a fundamental obstacle, which is that one cannot use Bayes’ rule for conditional probability in a quantum setting: the Eavesdropper’s maximum probability of guessing two bits of the key k1 k2 cannot be expressed as the product of her maximum probability of guessing k1 times her maximum probability of guessing k2 given that she guessed k1. This has to do with the quantum nature of the Eavesdropper, and the fact that different measurements on the same quantum state are not always compatible (they may not commute).

A complete proof of security of a variant of Ekert’s protocol was first given in previous work of the authors. 35 The goal of this paper is to highlight two key components of this security proof. The first is the use of deep properties of