Randomness Extractor

A randomness extractor, often simply called "an extractor," is a certain kind of pseudorandom generator which, when applied to a sufficient quantity of output from a (possibly) weakly random, entropy source (such as radioactive decay, or thermal noise), generates a highly random output that is independent and uniformly distributed. The only restrictions on possible sources is that they are nondeterministic to the extent that there is no way the source can be fully controlled, calculated or predicted and that a lower bound on their entropy rate can be established. For a given source, a randomness extractor can even be considered to be a true random number generator (TRNG); but there is no single extractor which has been proven to produce truly random output from any type of weakly random source.

The weakly random source is longer than the extractor's output, thus a practical goal in constructing extractors is to obtain a truly random output with a uniform distribution which is as long as possible while using a source that is as short as possible. This, in turn, is related to the problem of the efficiency with which the extractor converts information from the weakly random source (sometimes the term bias is used to denote its departure from uniformity) into output which is acceptably uniform. An efficient extractor is one in which the ratio of the bits used to the bits produced is as close as possible to unity. In older literature some extractors are called unbiasing algorithms. One of the earliest extractors is the one proposed by von Neumann which is described in the section on examples.

NIST Special Publication 800-90B (draft) recommends several extractors, including the SHA hash family and states that if the amount of entropy input is twice the number of bits output from them, that output can be considered essentially fully random.