Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  D.W. Jul 28 at 3:15
    
@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. –  owlstead Jul 28 at 7:42
    
The title of this question made me think I was on dentists.stackexchange.com –  l19 Aug 1 at 1:16
    
@l19 Really? I would not want to have randomness extraction at a dentist :) –  owlstead Aug 1 at 1:30

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
I guess without format definition of "whitening" this is the best it can get... –  owlstead Jul 28 at 19:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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