Royal Society Publishing

Certifiable quantum dice

Umesh Vazirani, Thomas Vidick


We introduce a protocol through which a pair of quantum mechanical devices may be used to generate n random bits that are ε-close in statistical distance from n uniformly distributed bits, starting from a seed of Embedded Image uniform bits. The bits generated are certifiably random, based only on a simple statistical test that can be performed by the user, and on the assumption that the devices obey the no-signalling principle. No other assumptions are placed on the devices' inner workings: it is not necessary to even assume the validity of quantum mechanics.

1. Introduction

A source of independent and uniform random bits is a basic resource in many computational tasks, such as cryptography, game-theoretical protocols, algorithms and physical simulations. The quest for good hardware number generators goes as far back as the first commercially available computer, the Ferranti Mark I, a project in which Turing himself was very involved. That project was ultimately unsuccessful [1], and indeed constructing a physical source of randomness is an unexpectedly tricky task1 —one that touches on fundamental questions about the nature of randomness. The focus of this paper is the fundamental philosophical issue: how can one certify whether one has succeeded? In other words, suppose someone were to claim that a particular device outputs uniformly random bits; is there a feasible test to verify that claim? In this paper, we report progress on this issue, in the form of a specific construction of a device for generating randomness, and an associated test that certifies (convincingly to a user who is afraid that the device was tampered with by an adversary) that the particular output produced by the device was drawn from a distribution that is statistically close to uniform.

This might sound far fetched, because a uniform random number generator must output every n-bit sequence with equal probability 1/2n, and there seems to be no basis on which to reject any particular output in favour of any other. On the face of it, testing the output of the box amounts to classifying a single n-bit string x (or a very small sample of the exponentially many n-bit strings) as being random or not random. This naturally brings to mind the work of Kolmogorov, Chaitin and Martin-Löf on algorithmic randomness, which provides a foundation for probability theory based on a precise definition for what it means for a particular string x to be random: it is random if it is incompressible, or, as was shown to be essentially equivalent, it passes all computable statistical tests for randomness (we refer to the excellent book [3] for a comprehensive treatment of this aspect). Unfortunately, under this definition, whether or not x is random is in fact uncomputable, and even restricting the definition to efficient statistical tests (i.e. polynomial time) renders the randomness certification problem co-NP-complete. The theory of complexity-based pseudo-randomness suggests a way around this impasse, by showing that the outputs of certain cryptographically secure pseudo-random generators pass all polynomial time statistical tests (see Goldreich [4] for a recent survey). However, this very strong guarantee on the distribution of strings output by the generator is based on unproven cryptographic assumptions. Moreover, the generator only stretches randomness by a polynomial factor: to output an n-bit pseudo-random sequence, the generator must be fed nc uniformly random bits, for some constant c>0.

Starting in the mid-1980s, computer scientists explored a different approach to the question of designing a uniform random number generator. To avoid grappling with difficult philosophical questions about the nature of randomness, they assumed that they already had access to a physical device that was guaranteed to output random strings, except that the randomness was of ‘low quality’. They modelled such devices as adversarially controlled sources of randomness, starting with the semi-random source [5], and weak random sources [6]. This sequence of papers has culminated in sophisticated algorithms called randomness extractors that are guaranteed to output a sequence that is arbitrarily close to truly random bits from physical sources of low-quality randomness (see Shaltiel [7] for a survey). It was clear, in a classical world, that these results were the best one could hope for—because it was necessary to assume that randomness in some form was output by the device in the first place, the only progress could be in minimizing the assumptions placed on the quality of that randomness.

Unlike classical physics, where randomness is implicitly an assertion about our lack of knowledge or computational ability, quantum mechanics offers a source of intrinsic randomness, ensconced in the Born rule, one of the fundamental axioms of the theory. So, in principle, it is very simple to design a quantum device that outputs a sequence of independent unbiased bits. In fact, there have been several concrete proposals for implementing random generators based on quantum mechanics [8,9], and testing whether the outputs of the generators pass certain simple statistical tests [10,11], or even tests specifically designed towards detecting algorithmic randomness [12]. Of course, success in passing a handful of such tests in no way certifies that the output distribution of the generator is close to uniformly random—the best that one can hope to say is that failure to pass the tests certifies that the generator's output distribution is not uniform.

This brings us back to the main question addressed in this paper: is it possible to positively certify that the output of a randomness-generating device (based on quantum mechanics) is ‘really random’ even though the user does not trust the experimental skills of the manufacturer, the calibration of the device, the manufacturer's motivations (particularly in cryptographic settings) or even the correctness of quantum mechanics. We describe the construction of a specific kind of quantum random number generator for which the answer to these questions is affirmative. This construction builds upon a proposal of Colbeck [13] and follow-up work by Pironio et al. [14] that provides a link between randomness certification and quantum non-locality. Before we can describe the actual construction, we must introduce some basic ideas behind quantum non-locality.

(a) The Clauser–Horne–Shimony–Holt game

Non-locality is one of the most interesting features of quantum mechanics and was explored in the famous work by Einstein, Podolsky and Rosen [15], and later in the work of Bell [16,17]. We focus here on a concrete realization of an experiment inspired by Bell's work that is best phrased as a game, the Clauser–Horne–Shimony–Holt (CHSH) game, named after its inventors Clauser et al. [18]. The CHSH game is played by two cooperating players, Alice and Bob, who we model using two spatially separated boxes Embedded Image and Embedded Image. Each of the boxes may contain parts of an entangled quantum system,2 and, in general, they can be described through the underlying probability distribution Embedded Image, the probability of the boxes producing outputs a and b when provided inputs x and y, respectively.

The spatial separation between the boxes reflects the fact that Alice and Bob are not allowed to communicate during the game. Mathematically, this assumption is enforced through a no-signalling condition placed on the distribution Embedded Image. This condition states that the marginal distribution on Embedded Image's outputs (respectively, Embedded Image's outputs) should be independent of Embedded Image's input (respectively, Embedded Image's input), Embedded Image 1.1 and a symmetric equation should hold when summing over a.

At the start of the game, each player is given an input x,y∈{0,1} chosen uniformly at random. They are allowed to perform arbitrary measurements on their share of the entangled state, but are not allowed to communicate. Their goal is to produce outputs a,b that satisfy the CHSH condition Embedded Image 1.2

It is not hard to see that, if the boxes are only classically correlated (i.e. their only non-local resource is shared randomness), the best strategy for the players will lead to a success probability of Embedded Image—in fact, systematically outputting 0 is the best one can do. However, there are quantum measurements on a 2-qubit entangled state that allow the players to obtain a strictly higher success probability of Embedded Image. The entangled state is a Bell pair Embedded Image This notation describes the joint state of a pair of two-dimensional systems that are in an equal superposition of two identical states: the |0〉|0〉 state and the |1〉|1〉 state. Each party will measure its own half of |Ψ〉 using one of the two possible choices of basis, depending on the input bit. These bases are such that, out of the four pairs of bases, those corresponding to input pairs (x,y) such that xy=0 make an angle π/8 with each other, while the pair corresponding to the inputs (1,1) make an angle π/2−π/8 (see figure 1 for an illustration). The resulting measurements have the property that, for every possible pair of inputs, the pair of outputs obtained by making the corresponding measurements on both halves of |Ψ〉 will be correct with probability Embedded Image.

Figure 1.

The bases used in the CHSH game. Solid lines correspond to the basis used on input x=0 (a) and y=0 (b). Dotted lines correspond to the basis used on input x=1 (a) and y=1 (b). Pairs of vectors corresponding to valid outputs always make an angle of π/8.

In fact, for any number Embedded Image, there is a quantum strategy achieving exactly that success probability. Hence, we may define the quantum regime for the CHSH game as this range of probabilities: for any value in that range, there is a simple quantum-mechanical pair of boxes, whose underlying distribution Embedded Image obeys the no-signalling condition (1.1), which achieves that success probability.

These well-known facts have a striking consequence, first made explicit in Colbeck's PhD thesis [13] (see also Colbeck & Kent [19] for an expanded version): any boxes producing correlations that fall in the quantum regime must generate randomness!3 Indeed, deterministic boxes—boxes whose underlying distribution Embedded Image is concentrated on a unique pair of outputs (a,b) for every possible input pair (x,y)—are inherently classical, so that their success probability must fall in the classical regime Embedded Image. This observation provides a first glimpse of a possible test for randomness. The test would be based on the use of two spatially separated boxes. Inputs to the boxes would be chosen independently and uniformly at random, and their outputs would be checked for the CHSH constraint (1.2). Repeating the experiment many times, and verifying that the CHSH constraint is satisfied more than 75 per cent of the time, would guarantee that the sequence of outputs produced by the boxes contains (some) randomness. Moreover, the certified presence of randomness would not depend on any assumption on the physical nature of the boxes—it is guaranteed by a simple statistical test, together with the no-signalling condition (1.1).

(b) A randomness-expansion protocol

The main drawback of the procedure described above is that in order to test the device one needs more randomness than is actually produced. Indeed, selecting inputs to the boxes in the CHSH game requires two bits of randomness, while certainly no more than two bits will be produced. Hence, while the bits output are certifiably random, one needs to start with an equal, if not larger, number of random bits prior to the experiment. In a recent paper published in Nature, Pironio et al. [14] showed that one could reliably (up to some error ε) certify that the average value of pCHSH across n steps of interaction with the boxes is higher than Embedded Image by choosing inputs to the boxes according to a very biased distribution. n pairs of inputs following this biased distribution may be sampled using only Embedded Image uniformly random bits, resulting in a protocol that uses approximately Embedded Image random bits to certifiably generate n bits that are ε-close in statistical distance to being uniformly distributed.4 (An extractor could then be applied to produce linearly many near-uniform bits.) Pironio et al. [14] also reported an experimental realization of their scheme, demonstrating the generation of 42 new random numbers, in addition to the randomness used to execute the protocol.

Ideally, one would like a randomness-generating device that requires very few or no random bits as input to get started. Indeed, a small amount of randomness is necessary, because if the tests were totally deterministic they would be passed by a box that outputs a predetermined sequence of bits. Quantitatively, one can argue that Embedded Image bits are necessary to guarantee that the output is ε-close to uniform in statistical distance. This is because a malicious device could attempt to guess the experimenter's private random bits, and behave accordingly. If the experimenter uses only s random bits, the device's guess will be successful with probability 2s, and, in that case, it can deterministically satisfy all the experimenter's requirements (since they are known in advance). One can also argue (perhaps a little less emphatically) that Embedded Image bits are necessary, since at best the device acts like a weak random source, and a random seed of Embedded Image bits is necessary to extract that randomness.

In this paper, we describe a very simple protocol that comes close to achieving this, using a random seed of length Embedded Image to generate an n-bit string that is ε-close to uniformly random in statistical distance. This exponentially improves upon the quadratic expansion of Pironio et al. [14]. The protocol to achieve this prescribes the interaction of a trusted user with an untrusted physical device, which we assume is made of two separate boxes, Embedded Image and Embedded Image. The protocol consists of m=O(n) phases. Each phase lasts for Embedded Image rounds, during each of which the user inputs a single bit to each box and collects a single bit as output. This sequence of mk interactions is non-adaptive: the user can generate the 2mk input bits in advance from his Embedded Image-bit random seed before the interaction. It is of critical importance that he reveals the input bits of phase i+1 only after the completion of phase i. In each phase, the user also performs a very simple statistical test (which simply checks that the fraction of rounds that satisfy the CHSH condition lie in the quantum range, as described in §1a). If the test is passed in all phases, then the output of box Embedded Image, say, is efficiently (and classically) post-processed to output an n-bit string. If the test is failed in any phase, then the user outputs a special ‘fail’ symbol. (We refer to §2 for a more detailed description of the protocol and the relevant parameters.)

The bits produced in the protocol are guaranteed to be statistically close to uniformly distributed provided the following conditions are met:

  • — the user's private random bits are uniformly random;

  • — the simple statistical test is passed in all m phases of the protocol; and

  • — there is no communication between Embedded Image and Embedded Image in the middle of any phase. Formally, this requirement states the following: for each phase i, the marginal distribution of outputs produced by Embedded Image (respectively, Embedded Image) during phase i is independent of all inputs to Embedded Image (respectively, Embedded Image) during phase i.

As we shall see, it is possible to implement using very simple quantum mechanics a pair of boxes Embedded Image and Embedded Image that pass the statistical tests in all m phases with high probability. Equally interesting is the fact that the three conditions listed above made no mention of quantum mechanics. The main condition is that there must be no communication between the two boxes during the execution of a single phase. There are many ways one could imagine enforcing this condition, most markedly by ensuring that they are separated by a distance greater than that light can travel during each time interval. In this sense, the randomness in the output could be said to be ‘Einstein certified’—it is certifiable even to a quantum-sceptic (Einstein's oft repeated quote ‘God does not play dice with the Universe’ comes to mind), as it only relies on special relativity together with a simple statistical test on the actual output of the device.

The proof of the guarantee on the randomness of the output of the boxes outlined above is based on a simple guessing game introduced in §3. In the guessing game, Bob is given an input y∈{0,1}, and Alice is asked to produce a guess for that input. Clearly, any strategy with success probability larger than Embedded Image (over the choice of Bob's input) indicates communication between Alice and Bob. Our analysis proceeds by showing that a pair of boxes Embedded Image and Embedded Image that pass the simple statistical test in every phase while not outputting sufficient randomness can actually be used to devise a successful strategy in the guessing game, thus contradicting the assumption that the boxes did not communicate in the middle of any phase.

(c) Classical and quantum adversaries

Among the many applications for random bits, some of the most prominent pertain to the area of cryptography. For instance, the most widely studied key distribution protocol, BB84 [23], requires a large number of uniformly distributed bits in order to make an initial choice of basis. In such an application, it is crucial that the bits generated appear close to uniform not only to the (honest) user of the cryptographic protocol, but also to any external adversary to the protocol.

A limited type of adversary is a classical adversary, who may share classical correlations with the device used in order to generate the random bits. Such an adversary can, for instance, be used to model a situation in which the device has been prepared by a malicious opponent using an arbitrary procedure. The classical correlations correspond to the information that the adversary has kept about the workings of the device. Recently, Pironio & Massar [24] and independently Fehr et al. [22] extended the results of Pironio et al. [14] to show that the same protocol could be used to produce bits secure against such classical adversaries.

A stronger type of adversary is a quantum adversary. Such an adversary can potentially be much more powerful than a classical adversary. For instance, she could in addition have decided to initialize the device in an entangled quantum state that extends into her own laboratory. This opens the possibility that the adversary may be able to perform specific measurements on her share of the entanglement, producing outcomes that are correlated with whatever bits the device may have produced in the protocol.

A reason to doubt that the adversary may gain much information in this way comes from a delicate property of entanglement, its monogamy [25]. Informally, monogamy states that a tripartite entangled state |ΨABE cannot be maximally entangled both between A and B and between B and E. Since our protocol enforces very strict correlations between the outputs of Embedded Image and Embedded Image, one may hope that these correlations will pre-empt any strong correlation between either of them and an arbitrary adversary.

In Vazirani & Vidick [26], we show that this scenario can indeed be ruled out by proving an analogue to theorem 4.1, which also holds in the presence of a quantum adversary. The theorem applies to a slight variant of the protocol described in figure 2, based on using an ‘extended’ version of the CHSH game with four possible inputs per box. It also requires an additional assumption on the boxes, in addition to the no-signalling condition: that their inner workings may be described by quantum mechanics. Such an assumption is necessary if we wish to quantify the correlations between the boxes and a quantum adversary; however, the absence of such a requirement is one of the strengths of the procedure described in this paper.

Figure 2.

Protocol A uses Embedded Image bits of randomness and makes Embedded Image uses of the boxes. Theorem 4.1 (in §4) shows that n bits of randomness are produced with confidence 1−ε. The threshold 0.2k in steps 3.1.2 and 3.2.2 is arbitrary, and any value strictly lower than k/4 would work.

2. Exponential expansion of randomness

Let n and ε be two fixed parameters: n is the target number of random bits that the user would like to generate at the end of the protocol, and ε>0 is an ‘error’ parameter bounding the statistical distance between the output bits eventually produced and the uniform distribution on n bits.

Our protocol, summarized in figure 2, uses two main ideas in order to save on the randomness required for the user to execute it. The first idea is to restrict the inputs to (0,0) most of the time. Only a few randomly placed checks (the Bell rounds) are performed in order to verify that the boxes are generating their inputs honestly. There are about Embedded Image such blocks. Note that the boxes usually do not know when they are being checked: for instance, if the input is (0,1) then, even though box Embedded Image knows that it is in a Bell round, box Embedded Image by itself cannot differentiate that particular round from one in which both inputs are 0. This implies, in particular, that the strategy it uses to determine its output cannot be different from what it would have been had the inputs been the more frequent (0,0).5

The second main idea consists of decomposing the protocol into blocks, which are consecutive sequences of a fixed number Embedded Image of rounds of interaction between the user and the boxes. Each box always receives identical inputs throughout all rounds of a given block. The blocks' purpose is to enable the user to perform a robust verification of the CHSH condition: his final test will enforce that, in every block, a significantly larger than Embedded Image fraction of pairs of outputs satisfy the CHSH condition (with respect to the corresponding pair of inputs). This lets us argue about the Hamming distance between Alice and Bob's k-bit outputs in any block: if the CHSH constraint was of the form ab=0 then the outputs should be close in Hamming distance, whereas if it had the form ab=1 then they should be far apart.

Altogether, protocol A requires only the use of random bits in order to select the position of the Bell blocks, as well as to select inputs in these blocks. The Embedded Image Bell blocks can be chosen among the O(n) rounds using Embedded Image random bits [27], and corresponding uniformly distributed inputs may be generated using an additional Embedded Image random bits.

Before proceeding, we should ensure that ‘honest’ boxes, which play the optimal quantum strategy for the CHSH game (as described in figure 1) independently in every round, are accepted by the user with very high probability. Indeed, we have seen that such boxes will satisfy the CHSH constraint independently with probability Embedded Image in each round. Hence, when one considers a block of k successive rounds, the probability that the CHSH constraint is not satisfied in more than 20 per cent of those rounds will be exponentially small in k. Precisely, a simple Chernoff bound shows that the probability that the honest strategy satisfies the CHSH condition in less than 80 per cent of any k successive rounds is at most Embedded Image. Given our choice of Embedded Image, it can be verified that, for large enough n, this expression is smaller than ε/m, where m=400n is the total number of blocks in the protocol. By a union bound, such boxes will fail to produce correlations satisfying the user in even just one of these blocks with probability at most ε.

The key part of the proof of our result consists of analysing the case of arbitrary non-signalling boxes: we need to show that any such boxes that are accepted in the protocol must produce n bits of randomness. This requires that we define more precisely what we mean by ‘n bits of randomness’. Recall that our ultimate goal is to produce bits that are uniformly random, as this will make them suitable for most applications. We will achieve this in two stages. In the first stage, we will show that the bits produced by one of the boxes, say Embedded Image, in the protocol must contain a linear amount of smooth min-entropy. In the second stage, we will observe that this condition is enough to guarantee that Embedded Image's outputs may then be massaged into bits that are close to being uniformly distributed.

The min-entropy measures the highest ‘peak’ of a distribution: a random variable with min-entropy k never takes any given value with probability larger than 2k. Given a random variable B, it is defined as Embedded Image.6 The smooth min-entropy is a ‘robust’ variant of the min-entropy, defined as Embedded Image where Embedded Image is the statistical distance and ε>0 is a ‘smoothness’ parameter.

It turns out that the choice of the smooth min-entropy is the right one with respect to the task of producing bits that are indistinguishable from uniform. Indeed, one of the major achievements of the field of randomness extraction is the demonstration that a random variable B with smooth min-entropy Embedded Image may be efficiently transformed into a string of approximately K bits that are ε-close to being uniformly distributed. This task can be accomplished using a combinatorial construction known as an extractor. An extractor usually takes two inputs. The first, called the source, is the random variable B from which we wish to extract uniformly random bits. The second is a random variable Y called the seed. It can be much shorter than the source, but is required to be uniformly distributed. The extractor maps the pair (X,Y) to a single random variable Z, over K bits, with the promise that Z is statistically close to uniform as long as B has at least K bits of min-entropy. In order to do so, the best extractors require the seed to be of length about Embedded Image [28].

To summarize, our protocol will use a source of fresh random bits in each of its two stages. In the first stage, Embedded Image bits will be used in order to select roughly Embedded Image pairs of inputs to the boxes, as described in figure 2. The user will then collect as many pairs of outputs, and verify that they satisfy the CHSH correlations. If not, he will reject the outputs. If so, he will use an additional Embedded Image uniform bits to play the role of the seed Y in a specific extractor construction. He will apply the extractor to the bits B produced by the box Embedded Image and Y , producing a string Z of n bits. The final output of the protocol is Z itself. Our main result, theorem 4.1 below, guarantees that Z is statistically close to a uniformly distributed n-bit string.

3. The guessing game

The analysis of our protocol is based on the definition of a simple ‘guessing game’. In this game, there are two cooperating players, Alice and Bob. At the start of the game, Bob receives a single bit y∈{0,1} chosen uniformly at random. The players are then allowed to perform arbitrary computations, but are not allowed to communicate. At the end of the game, Alice outputs a bit a, and the players win if a=y.

Clearly, any strategy with success probability larger than Embedded Image indicates a violation of the no-communication assumption between Alice and Bob. At the heart of the proof of theorem 4.1 is a reduction to the guessing game. Assuming that there existed a pair of boxes violating the conclusions of the theorem, we will show how these boxes may be used to devise a successful strategy in the guessing game, contradicting the no-signalling assumption placed on the boxes.

To illustrate the main features of the strategies we will design later, consider the following simplified setting. Let Embedded Image be a given pair of boxes taking inputs X,Y ∈{0,1} and producing outputs A,B∈{0,1}k, respectively. Assume the following two properties hold. First, if the input to Embedded Image is Y =0, then its output B is essentially deterministic, in the sense that B=b0 with high probability. Second, whatever their inputs, the boxes' outputs satisfy the CHSH constraint on average with a slightly higher probability than could any classical boxes: there is a fixed δ>0 such that a fraction at least Embedded Image of i∈[k] are such that AiBi=XY . Then we claim that there is a strategy for Alice and Bob in the guessing game, using Embedded Image and Embedded Image, that succeeds with probability strictly larger than Embedded Image, demonstrating that the boxes must be signalling.

Alice and Bob's strategy is the following. Alice is given access to Embedded Image and Bob to Embedded Image. Upon receiving his secret bit y, Bob inputs it to Embedded Image, collecting outputs b∈{0,1}k. Alice chooses an x∈{0,1} uniformly at random, and inputs it to Embedded Image, collecting outputs a∈{0,1}k. Let b0 be the k-bit string with the highest probability of being output by Embedded Image, conditioned on y=0. Alice makes a decision as follows: she computes the relative Hamming distance d=dH(a,b0). If Embedded Image she claims ‘Bob's input was 0’. Otherwise, she claims ‘Bob's input was 1’.

By assumption, if Bob's secret bit was y=0, then his output is almost certainly b0. By the CHSH constraint, independently of her input Alice's output a lies in a Hamming ball of radius Embedded Image around b0. So in this case she correctly decides to claim ‘Bob's input was 0’.

In the case that Bob's secret bit was y=1, the analysis is more interesting. Let b be the actual output of Embedded Image. Let a0 and a1 be Embedded Image's output in the two cases x=0 and x=1, respectively. We claim that the Hamming distance Embedded Image. This is because, by the CHSH constraint, Embedded Image, while Embedded Image. Applying the triangle inequality Embedded Image as claimed. Hence both a0 and a1 cannot lie in the Hamming ball of radius Embedded Image around the fixed string b0 (observe that this argument makes no use of the actual location of b0!). Thus, in the case y=1, Alice correctly outputs ‘Bob's input was 1’ with probability at least Embedded Image.

Overall, Alice and Bob succeed in the guessing game with probability Embedded Image, implying the boxes Embedded Image, Embedded Image allowed them to communicate, and hence do not satisfy the no-signalling condition.

Clearly, there is a lot of slack in the above reasoning, because for contradiction it suffices to succeed in the guessing game with any probability strictly greater than Embedded Image. By being more careful, it is possible to allow Bob's output on y=0 to have more min-entropy, as well as allow for a small probability that the boxes' outputs may not satisfy the CHSH constraint:

Lemma 3.1

Let β,γ>0 be such that Embedded Image and k an integer. Suppose given a pair of boxes Embedded Image taking inputs X,Y ∈{0,1} and producing outputs A,B∈{0,1}k each. Suppose the following conditions hold:

  1. When given input 0, the distribution of outputs of Embedded Image has low min-entropy: there exists a b0∈{0,1}k such that Embedded Image

  2. The boxes' outputs fall in the ‘quantum regime’ of the CHSH inequality: there exists a constant δ>0 such that Embedded Image where the probability is taken over the choice of uniformly random X,Y, and the boxes' internal randomness.

Then there is a strategy for Alice and Bob, using Embedded Image and Embedded Image which gives them success probability strictly greater than Embedded Image in the guessing game.


Alice and Bob's strategy in the guessing game is as described above. Let b0 be the k-bit string that is most likely to be output by Embedded Image, conditioned on y=0.

We first show that, if Bob's input was y=0, then Alice claims that Bob had a 0 with probability at least 1−γ−2β. By the first condition in the lemma, Bob obtains the output b0 with probability at least 1−γ. Moreover, by the second condition, the CHSH constraint will be satisfied with probability at least 1−2β on average over Alice's choice of input, given that Bob's input was y=0. Given y=0, whatever the input to Embedded Image, the CHSH constraint implies that Embedded Image. Hence by a union bound Alice will obtain an output string a at relative Hamming distance at most Embedded Image from b0 with probability at least 1−γ−2β.

Next we show that, in the case where Bob's input in the guessing game is y=1, Alice claims that Bob had a 1 with probability at least Embedded Image. The second condition in the lemma implies that, for any of the two possible choices for Alice's input X=x∈{0,1}, it holds that Embedded Image 3.1 Let b′ be Bob's output, and suppose that b′ is such that, for every x∈{0,1}, Embedded Image holds. It follows from (3.1) and Markov's inequality that this condition holds with probability at least 1−4β over b′.

If Alice chooses x=0, then the CHSH constraint indicates that the corresponding a0 should be such that Embedded Image, while in the case that she chooses x=1 her output a1 should satisfy Embedded Image. By the triangle inequality, Embedded Image so that, whatever the value of b′, at most one of a0 or a1 can be at distance less than Embedded Image from b0. Because Alice's input is chosen uniformly at random, taking into account the choice of b′ we have shown that with probability at least (1−4β)/2 Alice will choose an input that will make her correctly claim that Bob had a 1.

The two bounds proved earlier together show that Alice's probability of correctly guessing Bob's input in the guessing game is at least Embedded Image which is greater than Embedded Image whenever Embedded Image, proving lemma 3.1.

4. Analysis

In this section, we state and prove our main theorem.

Theorem 4.1

Let ε>0 be given, and n an integer. Let Embedded Image be an arbitrary pair of no-signalling boxes used to execute protocol A, as described in figure 2, B the random variable describing the bits output by Embedded Image, and CHSH the event that the boxes' outputs are accepted in the final test described in the protocol. Then for all large enough n at least one of the following holds:

  • either Embedded Image

  • or Embedded Image.

Furthermore, inputs in protocol A can be generated using Embedded Image bits of randomness, and it makes Embedded Image uses of the boxes. Finally, there exist honest, quantum-mechanical boxes that, when used in protocol A, are such that Embedded Image.

Theorem 4.1 asserts that, given any pair Embedded Image of non-signalling boxes, if the outputs of Embedded Image do not contain large enough min-entropy (when its inputs are chosen as specified in the protocol) then the boxes will fail the CHSH constraints imposed in the protocol with a high probability.

The second part of the theorem follows from the definition of the protocol and the fact that there exists a good quantum strategy in the CHSH game, as was already demonstrated in §2. We prove the first, and main, part of theorem 4.1 by a reduction to the guessing game introduced in §3. Suppose that there existed a pair of boxes such that neither of the theorem's conclusions was satisfied. Recall that the protocol calls for a total of mk uses of the boxes, divided into m blocks of k pairs of identical inputs each. We show that, provided the CHSH constraints are satisfied in all blocks with non-negligible probability, there must exist a special block in which the boxes' outputs, conditioned on specific past values, have the properties required in lemma 3.1. This will in turn lead to a contradiction of the no-signalling assumption. The exact properties of the special block that we obtain are described in claim 4.2.

Modelling events in the protocol. Let x=(xi),y=(yi),a=(ai),b=(bi)∈({0,1}k)m denote the boxes' respective input and output strings in an execution of protocol A, as described in figure 2. Let X,Y,A,B be the corresponding random variables. The boxes' behaviour is characterized by a probability distribution pAB|XY(a,b|x,y). The iterative structure of the protocol implies that pAB|XY can be factored as follows: Embedded Image where Hi=(A<i,B<i,X<i,Y<i) and hi=(a<i,b<i,x<i,y<i). We impose a single additional condition on pAB|XY: that it obeys the no-signalling condition in every block, that is, for every i∈[mk], ai,xi,yi,yi and hi, it holds that Embedded Image and a symmetric condition holds when marginalizing over ai. For i∈[m], let CHSHi be the event that dH(AiBi,XiYi)≤0.2, and Embedded Image. We will also use the shorthand Embedded Image. Finally, we let Tj be a random variable denoting the j-th Bell block, i.e. the j-th element of the set T chosen by the user in step 2 of protocol A.

Claim 4.2

Let n be an integer, and Embedded Image. Suppose that (i) Embedded Image and (ii) Embedded Image. Then for all large enough n there exists an index j0 and a subset G of output strings satisfying Embedded Image such that the following hold:

  • — Conditioned on Embedded Image's input in the j0-th Bell block Tj0 being 0, its output in that block is essentially deterministic: Embedded Image 4.1

  • — The CHSH condition is satisfied with high probability in the j0-th Bell block Tj0: Embedded Image 4.2

The proof of claim 4.2 follows from an appropriate chained application of Baye's rule, and it is given in appendix A. In order to conclude the proof of theorem 4.1, it remains to show how the special block identified in claim 4.2 can lead to a successful strategy in the guessing game.

Consider the following strategy for Alice and Bob in the guessing game. In a preparatory phase (before Bob receives his secret bit y), Alice and Bob execute protocol A with the boxes Embedded Image and Embedded Image, up to the Tj0-th block (excluded). Bob communicates Embedded Image's outputs up till that block to Alice. Together they check that the CHSH constraint is satisfied in all blocks preceding the Tj0-th; if not, they abort. They also verify that Bob's outputs are the prefix of a string bG; if not, they abort. The guessing game can now start: Alice and Bob are separated and Bob is given his secret input y.

Given the conditioning that Alice and Bob have performed, once they are ready to start the game the boxes Embedded Image and Embedded Image satisfy both conditions of lemma 3.1. Indeed, under the input distribution specified in the protocol, inputs in a Bell block are chosen according to the uniform distribution. Because the block Tj0 identified in claim 4.2 is a Bell block by definition, condition 1 in lemma 3.1 holds with Embedded Image as a consequence of item 1 in claim 4.2 and condition 2 in lemma 3.1 follows from item 2 in claim 4.2 with Embedded Image. Because Embedded Image, lemma 3.1 lets us conclude that the boxes Embedded Image and Embedded Image must be signalling in the Tj0-th block, a contradiction. This finishes the proof of theorem 4.1.


U.V. is supported in part by NSF grant CCF-0905626, ARO grant W911NF-09-1-0440 and NIST award 60NANB10D262. T.V. is supported by the National Science Foundation under grant no. 0844626. Most of this work was completed while T.V. was at U.C. Berkeley.

Appendix A. Proof of claim 4.2

Before proving claim 4.2, we introduce the following well-known claim that will be useful in understanding what it means for a random variable to have small smooth min-entropy.

Claim A.1

Let α,ε>0 and X a random variable such that Embedded Image. Then there exists a set B such that Embedded Image and, for every xB, it holds that Embedded Image.


Let B be the set of x such that Embedded Image, and suppose Embedded Image. Define Y so that Embedded Image for every x∉B, Embedded Image for every xB. In order to normalize Y , introduce new values z such that Embedded Image and extend Y by defining Embedded Image until it is properly normalized. Then ∥YX1<ε and Embedded Image, contradicting the assumption on the smooth min-entropy of X.

Proof of claim 4.2.

As in protocol A, set m=400n, Embedded Image and ℓ=m/Δ. Let BAD be the set of strings b∈({0,1}k)m such that Embedded Image. Assumption (i), together with claim A.1, shows that Embedded Image. Using (ii) and Baye's rule, we get that, for every b=(b1,…,bm)∈BAD, Embedded Image Taking logarithms on both sides, Embedded Image assuming as in the statement of the claim that ε is not too small. By an averaging argument, at least Embedded Image of all i∈[m] are such that a fraction at least Embedded Image (in probability) of all b∈BAD are such that Embedded Image A 1 Let S be the set of i∈[m] such that (A 1) holds for a fraction at least Embedded Image of b∈BAD. S is a random variable of size Embedded Image.

We apply the same reasoning once more, focusing on the CHSH constraint being satisfied in a Bell block. Let T be a random variable containing the indices of the blocks that have been designated as Bell blocks in the protocol. Let N=|TS|. We may write N as the sum of Boolean random variables Nj, where Nj=1 if and only if the j-th element of S falls in T. Because, for every i, the i-th block is chosen to be a Bell block independently with probability 1/ℓ=Δ/m (independently of past events such as CHSH<i and B<i=b<i), the random variables Nj, for j≤|S|, are independent. Recall that |S|≥9m/10, and by a Chernoff bound Embedded Image given our choice of Δ. Let K denote the event that this bound holds: Embedded Image, and conditioned on K it holds that N=|ST|≥9m/(100ℓ)≥9Δ/100. Starting from Embedded Image, further conditioning on K gives Embedded Image Using Baye's rule as before, we then obtain Embedded Image Using the lower bound on N, this implies that there exists an iTS such that Embedded Image A 2 given the choice of Δ made in the claim. Given our assumption on ε, removing the conditioning on K in this equation at most decreases the lower bound to 0.95. Let iTS be a Bell block for which (A 2) holds. By Markov's inequality, for a fraction at least Embedded Image of b∈BAD, it holds that Embedded Image A 3 By the union bound, at iteration i (A 3) will hold simultaneously with (A 1) for a subset G of BAD of size at least Embedded Image given our choice of parameters. Equation (A 3) implies (4.2) in the claim. To show that (A 1) implies (4.1), note that, in (A 1), the probability is taken for a random choice of inputs to the boxes in round i as specified in the protocol, while in (A 3), by definition of a Bell block, the probability is taken under the uniform distribution over inputs. We may not guarantee that (A 1) still holds under the uniform distribution, because in the protocol that distribution is chosen in round i only with probability 1/ℓ. However, because in the protocol Bob's input is a 0 with probability at least Embedded Image irrespective of the type of block, we may ensure that (A 1) holds conditioned on Yi=0, an event that is independent from both CHSH<i and B<i=b<i (for any b<i). Hence, given our choice of Δ and the upper bound on ε, (A 1) implies (4.1) in the claim.


  • One contribution of 18 to a Theme Issue ‘The foundations of computation, physics and mentality: the Turing legacy’.

  • 1 There has been extensive research into the design of practical hardware number generators. Intel recently announced the first digital such generator, as part of its new ‘Ivy bridge’ microprocessor [2].

  • 2 For the purposes of this introductory discussion, we assume that the players in the game obey the laws of quantum mechanics, although that assumption will be relaxed later on.

  • 3 The idea that the sole violation of a Bell inequality may be useful to cryptographic tasks by itself is not new, and dates back at least to the first proposals for device-independent quantum key distribution [20,21].

  • 4 The paper [14] contained an error that was later fixed in the work of Fehr et al. [22].

  • 5 This idea was already used in Pironio et al. [14], and led to their protocol with quadratic Embedded Image expansion of randomness.

  • 6 The min-entropy is a stronger notion of entropy than the Shannon entropy, in the sense that having large min-entropy implies having large Shannon entropy, but the converse is not true.


View Abstract