Editing Certified infinite randomness expansion (section)

==Outline==

In this protocol, Alice has her initial private random string (the seed) and has been provided with eight identical measurement devices by Eve. Each of the devices has four settings and can produce two outputs. Alice first groups these devices into two `clusters', each containing four devices. With her seed as the initial input, she then iterates through a repeated procedure of passing a string to one of the clusters, performing a set of subroutines (defined below), then passing the output of this to the other cluster, where the same subroutines are carried out. She is free to stop the process at on any cluster output (though the whole protocol may abort prematurely if privacy can no longer be guaranteed).

Each passage through one cluster corresponds to the application of two sub-protocols: one to expand the length of the input string, and the other to generate a new, private string. The second step reduces the length of the output from the first, but by a significantly smaller factor so overall the length is still increased. As the output is private, it can be used to seed a repeated application of the protocol.

The clusters themselves are also used in pairs. First, two of the devices are used to apply the protocol of [https://arxiv.org/abs/1111.6054 Vazirani and Vidick]. First, Alice splits her input string into two equal portions and stashes the second half for later use. Using the first half as a source of randomness for making probabilistic decisions, she performs an adaptation of the [https://wiki.veriqloud.fr/index.php?title=Glossary CHSH game]. In this version, both of her devices can make four measurements, in the original game corresponding to:

* The honest measurement that party A would make given an input of 0
* The honest measurement that party A would make given an input of 1
* The honest measurement that party B would make given an input of 0
* The honest measurement that party B would make given an input of 1

Alice must first set up a series of `blocks` with size and count related to the confidence with which she seeks protocol correctness - these are effectively tables for storing her measurement results. She then designates a subset of these to be `Bell blocks` with probability determined by the count she has chosen. This selection is done at random using some of her input seed to generate indices. 

To perform the game, Alice steps through each block in turn. If a given block has not been designated as a Bell block, for each position in the block she has her devices prepare an [https://wiki.veriqloud.fr/index.php?title=Glossary EPR pair] entangled across themselves and measures both qubits with the same setting applied to each device. If her results from each device do not perfectly match, she aborts the protocol as this implies the devices contain something other than an EPR pair. For any block that has been designated as a Bell block, she first takes two bits from her seed and uses these to determine measurement settings: if the first is zero she applies the setting corresponding to measurement (1.) from above, if if is one she applies setting (2.). For the second device, if the second bit is zero she also applies setting (1.), if it is one she applies setting (4.). For each position in the block she has her devices prepare and EPR pair as above and measures with in the prior settings applied. As the outcomes are now correlated but stochastic, she accepts if the agreement of her results are within some threshold.

Having completed the adapted CHSH game, Alice concatenates all of her measurement results into a single output string. To remove any correlations this may have with an eavesdropper, she passes this string to a quantum-strong [https://wiki.veriqloud.fr/index.php?title=Glossary randomness extractor], using the remaining half of the initial input as a seed. The resulting output is an exponentially expanded, still (close to) uniformly random and private string.

This string is then used as the input to another (thankfully much simpler) protocol: using the other two devices in the cluster, Alice plays a standard CHSH game. The string is split into a half and two quarters. Until her seeds have been exhausted, Alice has her devices prepare an EPR state then makes a measurement based on the next bit in each of the seed quarters - for example, if the next bits taken from each sections are 0 and 1, then the first device will be set to (1.) as described above and the second to (4.). Once the game has been completed, she compares the results obtained from each: if they are not close to the results that would have been obtained with the private quantum strategy then she aborts the protocol. If the protocol is not aborted, Alice divides up the measurement results from her first device into a series of equal sized chunks and, using the remaining half-string of seed to generate a random index, selects one of these chunks to be returned as the protocol output.

The above constitutes one full run through a single `cluster expansion` step. This can then be repeated by Alice indefinitely, with the output of each step being used as the input to the next, so long as she alternates between the clusters she uses.