The Von Neumann randomness extractor is explicitly mentioned in the randomness e

Question

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?

Please only answer the second question if the terms are well defined enough to make a clear statement.

Explanation / Answer

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 e/2 - bit output, as NIST recommends in 800-90B.)
+ A whitener could instead use encryption with a secret key Ek(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).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.