will be important for us) the following stronger adversary. The stronger adversary has the ability, given as side information the information available to the original adversary (partial information about X and the seed Y) as well as a few additional “advice bits” about X, to produce a “ reconstructed” guess for the complete string X that is correct with probability of the order of (ε/m) 2, where m is the length of Z.

Our security proof relies on an adaptation of the reconstruction paradigm to the case of quantum side information. This allows us to argue that any eavesdropper who is able to distinguish the final key Z generated by the users from a uniformly random string can be “bootstrapped” into a stronger eavesdropper who, given a few additional bits of advice, is able to guess the complete string of outputs KA generated by Alice’s device in the protocol with non-trivial probability. Note that this probability is of the same order as the security parameter ε. To see that it is a strong bound, note that it is much larger than the easy bound of inverse exponential in the extracted key length, which follows (using any strong extractor) from the correspondence between quantum conditional min-entropy and guessing probability. Formally introducing the quantum reconstruction paradigm would require notation that is beyond the scope of this article. For the expert, we mention that the main tool used in the analysis is the “pretty good measurement” of Hausladen and Wooters, 17 which allows us to gain a handle on the Eavesdropper’s global measurement.

6. 3. Reduction to the guessing game

Recall that the raw key KA is formed from the bits KA = a1, . . ., a|C| generated by Alice’s device DA in the key rounds C ⊆ { 1, . . ., N}. Suppose for contradiction that, when an extractor ExtC built according to the specifications of the reconstruction paradigm is applied to KA, with a uniform choice of seed, the output Z is not indistinguishable from uniform: there is an attack for the adversary which uses all the quantum side information E available to the Eavesdropper at the end of protocol E1 to distinguish Z from uniform with some advantage ε. Our first step is to apply the quantum reconstruction paradigm to place ourselves in a stronger position: as argued in the previous section, it follows that there exists a “ bootstrapped” adversary whom, using a combination of the side information E and a small number of additional advice bits, is able to produce a guess for the string KA that is correct with probability of order (ε/m) 2, where m is the length of Z.

The second step in the analysis is to rule out such attacks.
We achieve this by performing a reduction to the guessing
game considered in Section 5. In order to present the reduc-
tion, it is convenient to abstract the present scenario as the
following multi-round form of the guessing game. Alice gets
an N-trit input x, and Bob an N-bit input y, chosen uniformly at
random. They use their respective devices, DA and DB, sequen-
tially to generate N-bit outputs a and b. A third player, Eve, is
given x, y, and a small number of arbitrary bits of advice about
Alice and Bob’s outputs. (This includes the outputs in the test
rounds and the bits of advice required for the reconstruction
procedure.) Alice and Bob’s devices are assumed to satisfy the
CHSH game correlations on average, when tested on a randomly
chosen fraction γ of the rounds, with non-negligible probability
of order ε over an execution of the protocol. The goal is to show
attack illustrates the main difficulty faced in our scenario:
the users’ devices may have memory, and behave adaptively
in each round, leveraging the users’ public communication
to covertly leak information about the final key.

Even setting the issue of adaptive devices aside, there is a second important difficulty. Assume the users had a way to enforce that their devices perform independent and identical operations in each round. It may still be the case that the Eavesdropper, on which no control is possible, benefits from a global measurement on all the side information she has collected throughout the protocol in order to implement her final attack on the key. Such an attack should be ruled out, even if its success probability is tiny, as long as it is higher than the security parameter for the protocol. So assume the Eavesdropper has performed a successful attack. Here begins the difficulty: conditioning on success of an unlikely event, which involves a measurement on the quantum side information and the public information leaked throughout the protocol, introduces correlations between the classical data observed by the users (including the devices’ inputs and outputs in all rounds) that need to be taken care of by the security proof.

The confounding factor here is that Bayes’ rule for conditional probabilities does not work in the presence of quantum side information. Informally, if Pg(K|E) is the maximum probability with which the Eavesdropper may guess the string K, given her quantum side information E, then it is not the case that Pg(K|E) = Pg(KN|KN− 1, ..., K1, E) ... Pg(K1|E). In fact, it is possible for the quantities on the right-hand side to all be very close to 1, while the quantity on the left-hand side is very small, the reason being that guessing measurements for K1, K2, ..., KN, cannot necessarily be “stitched together” into a guessing measurement for the complete string.

In order to side-step the issue we treat the combination of the joint quantum state of the devices and the eavesdropper, and the possible effects of the global measurement, as a black box, and focus on the classical information processed by Alice and Bob and the ways it which it can correlate with classical information generated by the Eavesdropper. The main tool in the analysis is the “reconstruction paradigm” mentioned above, which we discuss next.

6. 2. Security and the reconstruction paradigm

Let us first recall the main ideas behind the (classical) reconstruction paradigm. 33, e Consider a strong extractor Ext which takes two strings of bits as input, the source X and the seed Y, and combines them to produce an output Z = Ext(X, Y). Proceeding by contradiction, assume the adversary has the ability to distinguish the output of the extractor from uniform, with non-negligible advantage ε. Observe the weakness of this starting point: the adversary’s advantage could come from any kind of information; for example, she is able to predict, with small advantage ε, the parity of a small subset of the bits of Z, the location of which itself depends on other bits of Z, etc. The reconstruction paradigm uses properties of a specific construction of Ext to show that from any such adversary it is possible to construct (explicitly, and this e The parameters we give here are inaccurate, and are only meant to give an indication of the procedure.