Categories: Cryptography.

Von Neumann extractor

The Von Neumann extractor is a simple example of a randomness extractor: given a stream of “imperfectly random” bits, it extracts the entropy, and outputs a “perfectly random” stream.

As input, the Von Neumann extractor expects a stream of independent (uncorrelated) bits, i.e. the result of a Bernoulli process, where each bit is 00 with probability pp, and 11 with probability 1 ⁣ ⁣p1 \!-\! p. Crucially, pp does not need to be 1/21/2; there may be a bias.

The extractor will output a uniformly random stream with p=1/2p = 1/2. Given input bits a1,a2,...a_1, a_2, ..., it achieves this by looking at the bits in pairs (a1,a2)(a_1, a_2), (a3,a4)(a_3, a_4), etc. Then:

Evidently, the first case an=an+1a_n = a_{n+1} occurs with the following probabilities:

P(0,0)=p2P(1,1)=(1p)2\begin{aligned} P(0, 0) = p^2 \qquad \qquad P(1, 1) = (1 - p)^2 \end{aligned}

Meanwhile, the second case anan+1a_n \neq a_{n+1} occurs with probabilities given by:

P(0,1)=p(p1)P(1,0)=(p1)p\begin{aligned} P(0, 1) = p (p - 1) \qquad \qquad P(1, 0) = (p - 1) p \end{aligned}

Crucially, they are equal; P(0,1)=P(1,0)P(0, 1) = P(1, 0). Therefore, if the extractor encounters an input pair satisfying anan+1a_n \neq a_{n+1}, the first bit ana_n is 00 or 11 with a 50-50 probability, regardless of pp. Since the extractor only keeps those bits, its output is guaranteed to be “perfectly random”.

Clearly, because it discards many of the bits, the output stream will have a length Nout<NinN_\mathrm{out} < N_\mathrm{in}. The exact value of NoutN_\mathrm{out} is as follows, where P(0,1)+P(1,0)P(0, 1) + P(1, 0) is the probability that we keep a bit, and the factor 1/21/2 is due to us discarding half of the pair even in that case:

Nout=12Nin(P(0,1)+P(1,0))=12Nin(2p(p1))=Ninp(p1)\begin{aligned} N_\mathrm{out} = \frac{1}{2} N_\mathrm{in} \Big( P(0, 1) + P(1, 0) \Big) = \frac{1}{2} N_\mathrm{in} \Big( 2 p (p - 1) \Big) = N_\mathrm{in} p (p - 1) \end{aligned}

The key assumption that allows the Von Neumann extractor to work is that there is no correlation at all between the bits. In practice, this may be difficult to achieve, in which case a more complex randomness extraction scheme is needed.


  1. J.B. Brask, Quantum information: lecture notes, 2021, unpublished.