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
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.
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.
goal of this paper is to highlight two key components of
this security proof. The first is the use of deep properties of