The Von Neumann randomness extractor is explicitly mentioned in the randomness extractor page of Wikipedia, but strangely enough that page does not contain any reference to whitening the results of an entropy source.

Two intrinsically related questions:

  1. Is this Von Neumann randomness extractor indeed a form of whitening?
  2. Is whitening simply a part of randomness extractor, or is there another relation between whitening and randomness extraction?
  • $\begingroup$ What definition of whitening would you like us to use? I have not heard the term "whitening" used in this particular context, so you'll probably need to define your terms (or provide some more context and more information about why you're asking and how you will use the answer) before I could answer this. $\endgroup$
    – D.W.
    Jul 28 '14 at 3:15
  • $\begingroup$ @D.W. That's probably part of my problem. Up to now I had in mind that whitening is something that is a relatively simple method such as performing a XOR on the output of one or two RNG's, but I sometimes see it use as a more general method of (at least) creating a good distribution of values given by an RNG. $\endgroup$
    – Maarten Bodewes
    Jul 28 '14 at 7:42
  • 1
    $\begingroup$ The title of this question made me think I was on dentists.stackexchange.com $\endgroup$ Aug 1 '14 at 1:16
  • 2
    $\begingroup$ @l19 Really? I would not want to have randomness extraction at a dentist :) $\endgroup$
    – Maarten Bodewes
    Aug 1 '14 at 1:30

I would say that whitening is a more general concept than randomness extraction.

In randomness extraction you have an input with some entropy that isn't perfectly random and an output that should be perfectly random and full entropy. In whitening there is not necessarily an entropy requirement on the output, it just needs to look perfectly random to an adversary.

For example, suppose you have a $b$-bit input $I$ with at least $e$ bits of entropy:

  • A randomness extractor would map it to at most an $e$-bit output, for example the first $e$ bits of $H(I)$. (Better yet, an $\frac{e}{2}$-bit output, as NIST recommends in 800-90B.)
  • A whitener could instead use encryption with a secret key $E_k(I)$. This gives a $b$-bit output that may only have $e$ bits of entropy, but still looks random as long as the key is secret.

With the above definitions, Von Neumann is both a randomness extractor and a whitener (when the input is a Bernoulli sequence).


Taking your two questions sequentially:

  1. Von Neumann (VN) is not really a randomness extractor or whitener per se. It is used to de bias an entropy source that is inherently biased. Most entropy sources output bits in all sorts of weird ways. Consider the common entropy source that is a well trained monkey typing English words at a keyboard. It sits there typing out full proper English words, totally at random. This is a good entropy source. But the source is very biased as "E" will occur with probability 0.12, whilst "W" occurs with probability 0.02. Putting these words through VN will reduce the output to a string of 1s and 0s with no bias.

    However, the bit stream will not be random as for every "Q" you get a "U". This means that the letters are not independent, but have a correlation. That correlation extends to higher dimensions as well when you consider all the rules of English grammar. So all you have is a series of 1s and 0s that have a strong correlation. VN doesn't work on correlated entropy.

  2. To get good randomness, you could whiten the bit stream. I think that "whiten" refers to all frequencies being equal, as in white light. So you'd be looking to get independent 0 to 255 ranging bytes from the monkey. Therefore that bit stream would then need to be processed. You could XOR it with a RNG or perform some sort of hashing operation; it's the same thing fundamentally. This is whitening.

There are non hashed based extractors that will generate fully random output directly from the monkey, but they appear to be few and far between. Perhaps How to extract randomness from a file? will have been answered when you read this.

  • $\begingroup$ Thanks, interesting new point of view compared to the other answer. I wonder if they can be reconciled. $\endgroup$
    – Maarten Bodewes
    Sep 6 '15 at 12:46
  • $\begingroup$ While Von Neumann doesn't correct correlations, when run on an uncorrelated input it does both extract the entropy and result in a "white" output. So rather than saying it's neither, I would (and did) just say it has requirements on the input. Otherwise, I do agree with what you wrote. $\endgroup$
    – otus
    Sep 6 '15 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.