4
$\begingroup$

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?
$\endgroup$
4
  • $\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, 2014 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, 2014 at 7:42
  • 1
    $\begingroup$ The title of this question made me think I was on dentists.stackexchange.com $\endgroup$ Aug 1, 2014 at 1:16
  • 2
    $\begingroup$ @l19 Really? I would not want to have randomness extraction at a dentist :) $\endgroup$
    – Maarten Bodewes
    Aug 1, 2014 at 1:30

1 Answer 1

4
$\begingroup$

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).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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