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.

Tags: Building Blocks, Quantum Functionality, Specific Task

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (0,1)} then she sets the first device to setting $0$ and the second device to setting Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} : number of measurement iterations
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i} : measurement setting for device A on iteration Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i}
• $y_{i}$: measurement setting for device B on iteration Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i}
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{bases}} : tuple of measurement bases for device A; Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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)\}$
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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$
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} : initial private random seed
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} : final randomness expanded string
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{I}} : experimental estimate of CHSH correlation
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} : lower bound on conditional min-entropy of measurement results Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} with respect to measurement settings Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} and any information held by an adversary
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.)
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} : term to account for finite statistics effects
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} : the chosen confidence with which the returned entropy lower bound is correct
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{Ext}} : strong seeded (classical) randomness extractor

Requirements

• Network stage: Entanglement Distribution
• Random number generator
• Authenticated quantum channel
• Authenticated classical channel
• Hardware:
  • Multi qubit non-separable state preparation
  • Single qubit measurement
  • Single qubit gates

Properties

• Output string is of length Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \theta(n^2)}
• Requires only two measurement devices.
• Devices can be untrusted.
• Imposes no constraints on input states or measurements (i.e. Bell inequality tested can be changed from what is specified here).
• Allows for devices to have an internal quantum memory.
• Length of expanded string dependent on magnitude of CHSH correlation (as this tells us how much min-entropy can be contained in the results string) and the choice of randomness extractor (as different constructions have varying degrees of performance).

Pseudocode

Input: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{Ext}v '''Output''': <math>u}

• split Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} into Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t=(t^{(1)},t^{(2)})} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |t^{(1)}|} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |t^{(2)}|} are determined by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{Ext}}
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\leftarrow\big\lfloor\frac{|t^{(1)}|}{2}\big\rfloor}
• initialize arrays Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} of length Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n}
• For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i\leftarrow1} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} :
  • prepare state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\Psi^+\rangle} and share across devices A and B
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i\leftarrow t^{(1)}_i}
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_i\leftarrow t^{(1)}_{i+1}}
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i\leftarrow} measurement result from device A in basis Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{bases}[x_i]}
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i\leftarrow} measurement result from device B in basis Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_{bases}[y_i]}
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s[i]\leftarrow(x_i,y_i)}
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r[i]\leftarrow(a_i,b_i)}
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{I}\leftarrow0}
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i\leftarrow1} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} :
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i,y_i\leftarrow s[i]}
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i,b_i\leftarrow r[i]}
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{I}\leftarrow\hat{I}+\frac{4}{n}(-1)^{x_i\wedge y_i}(-1)^{a_i\oplus b_i}}
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon\leftarrow4\sqrt{-\frac{2\sqrt{2}}{n}\ln{(1-\alpha)}}}
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\leftarrow nf\big(\hat{I}-\epsilon\big)}
• flatten Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} into an array of bits
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline{r}\leftarrow\textrm{Ext}(r, t^{(2)},k)}
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u\leftarrow(t,\overline{r})}

Further Information

• Pironio et. al. implement the protocol using two ionic Yttrium qubits, separated by a distance of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} , and a uniform probability distribution (i.e. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(x,y)=\frac{1}{4}} ). Over the course of one month, they were able to produce Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=3016} entanglements and recorded a correlation of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{I}=2.414} ; implying at least 42 new random qubits had been produced with a confidence of 99%. The seed used in the experiment was generated from a combination of sources: radioactive decay, atmospheric noise and network activity on a remote computer.
• The protocol presented here implements the simplest design choices throughout. It is possible to use arbitrary Bell inequalities (rather than the CHSH inequality), to use the seed to generate Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_i} from some joint probability distribution Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(x,y)} , and to contsruct the protocol with more than two devices.

contributed by Neil Mcblane