Certified finite randomness expansion

Randomness expansion is a protocol for Quantum Random Number Generator which takes as input a private, uniformly random string and outputs a longer string which is (close to) private and uniformly random. The protocol of Pironio et. al. enables randomness expansion of such an input using only two identical untrusted (i.e. provided by an adversary) measurement devices. Privacy of the output string is guaranteed to a given confidence level and its length depends on the stochastic outcome of a CHSH game, the confidence level desired and the randomness extractor used in post-processing.

Such a protocol is useful in the case where one already has access to a private source for true randomness, but whose use is prohibitively expensive or whose access is limited. By applying randomness expansion, it is possible to make this resource go further using potentially much cheaper or more simple methods.

Assumptions

• Quantum theory is correct.
• The measurement devices do not interact during measurements.
• The measurement devices are not correlated with the input string.
• The adversary does not have access to a quantum memory.

Outline

In this protocol, Alice has an initial private random string (the seed) and has been provided with two identical measurement devices by Eve. Each of the devices has two settings and can produce two outputs. Prior to beginning the protocol, Alice has to decide with which confidence she would like her output string to be private from Eve, and which strong randomness extractor she would like to perform post-processing with. She then splits her seed into two portions - the sizes of which are determined by the chosen randomness extractor.

Alice then takes two bits from the start of the first portion of her initial string and uses these to choose the settings of her measurement devices (i.e. if the pair is $(0,1)$ then she sets the first device to setting $0$ and the second device to setting $1$). She prepares an EPR state and shares it across the two measurement devices, then performs measurements using each device with the chosen settings and records the output. She repeats this process until this portion of her input string has been exhausted, resulting in a binary string of recorded outputs of equal length to the input.

Using the input and output strings, Alice estimates the violation of the CHSH inequality her experiment has produced. This allows her to place a bound on the conditional min-entropy of the output string with respect to both the input string and any information Eve may have.

Finally, Alice passes her output string, the second portion of her initial seed and the determined min-entropy bound to a strong randomness extractor to generate a processed string which is (close to) uniform and private from Eve with the confidence specified at the beginning of the protocol. As Alice has kept her seed private throughout and the randomness extractor used is a strong one, she can then simply append her entire seed to the output of the randomness extractor to produce a final expanded string, which is guaranteed to be longer than the seed so long as a super-classical CHSH game has occurred.

Notation

• $n$: number of measurement iterations
• $x_{i}$: measurement setting for device A on iteration $i$
• $y_{i}$: measurement setting for device B on iteration $i$
• $A_{bases}$: tuple of measurement bases for device A; $A_{bases}=\{X,Z\}$
• $B_{bases}$: tuple of measurement bases for device B; $B_{bases}=\{1/{\sqrt {2}}(X+Z),1/{\sqrt {2}}(X-Z)\}$
• $a_{i}$: measurement result for device A on iteration $i$ (0 or 1)
• $b_{i}$: measurement result for device B on iteration $i$ (0 or 1)
• $s$: string of measurement basis pairs; $s=(x_{1},y_{1};\ldots ;x_{n},y_{n})$
• $r$: string of measurement result pairs; $r=(a_{1},b_{1};\ldots ;a_{n},b_{n})$
• ${\overline {r}}$: output string from classical randomness extraction of $r$
• $t$: initial private random seed
• $u$: final randomness expanded string
• ${\hat {I}}$: experimental estimate of CHSH correlation
• $k$: lower bound on conditional min-entropy of measurement results $r$ with respect to measurement settings $s$ and any information held by an adversary
• $f$: function which takes as input a(n estimated) CHSH correlation and returns a per-use lower bound on the conditional min-entropy of the measurement results with respect to measurement settings and any information held by an adversary in the limit of a large number of uses (determined using semi-definite programming in Pironio et. al.)
• $\epsilon$: term to account for finite statistics effects
• $\alpha$: the chosen confidence with which the returned entropy lower bound is correct
• ${\textrm {Ext}}$: strong seeded (classical) randomness extractor

Neil Mcblane