A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weak entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed.[1] Examples of weakly random sources include radioactive decay or thermal noise; the only restriction on possible sources is that there is no way they 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 that has been proven to produce truly random output from any type of weakly random source.
Sometimes the term "bias" is used to denote a weakly random source's departure from uniformity, and in older literature, some extractors are called unbiasing algorithms,[2] as they take the randomness from a so-called "biased" source and output a distribution that appears unbiased. The weakly random source will always be longer than the extractor's output, but an efficient extractor is one that lowers this ratio of lengths as much as possible, while simultaneously keeping the seed length low. Intuitively, this means that as much randomness as possible has been "extracted" from the source.
Many hardware random number generators have one or more "noise source" that generates colored noise.
The process of combining them together and extracting unbiased uncorrelated random bits (similar to white noise) is often called software whitening.[3][4][5][6]
Note that an extractor has some conceptual similarities with a pseudorandom generator (PRG), but the two concepts are not identical. Both are functions that take as input a small, uniformly random seed and produce a longer output that "looks" uniformly random. Some pseudorandom generators are, in fact, also extractors. (When a PRG is based on the existence of hard-core predicates, one can think of the weakly random source as a set of truth tables of such predicates and prove that the output is statistically close to uniform.[7]) However, the general PRG definition does not specify that a weakly random source must be used, and while in the case of an extractor, the output should be statistically close to uniform, in a PRG it is only required to be computationally indistinguishable from uniform, a somewhat weaker concept.
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 will exhibit full entropy.[8]
^Extracting randomness from sampleable distributions. Portal.acm.org. 12 November 2000. p. 32. ISBN 9780769508504. Retrieved 2012-06-12.
^David K. Gifford, Natural Random Numbers, MIT/LCS/TM-371, Massachusetts Institute of Technology, August 1988.
^
"Applied Statistics: Testing random Number".
Troels C. Petersen.
^
"OneRNG: On Trust and Distrust".
^
"John von Neumann".
^
Graysen Cline.
"Nonparametric Statistical Methods Using R".
2019.
p. 24.
^Luca Trevisan. "Extractors and Pseudorandom Generators" (PDF). Retrieved 2013-10-21.
^Recommendation for the Entropy Sources Used for Random Bit Generation (draft) NIST SP800-90B, Barker and Kelsey, August 2012, Section 6.4.2
and 23 Related for: Randomness extractor information
A randomnessextractor, often simply called an "extractor", is a function, which being applied to output from a weak entropy source, together with a short...
representative values: Not every randomnessextractor will produce the desired results. For example, the Von Neumann extractor, while providing an unbiased...
into a binary representation; a conditioner (randomnessextractor) that improves the quality of the random bits; health tests. TRNGs are mostly used in...
Extractor may refer to: Extractor (firearms) Extractor (mathematics) Extractor (screws), a tool used to remove broken screws Randomnessextractor Soxhlet...
short of the goal of true randomness, although they may meet, with varying success, some of the statistical tests for randomness intended to measure how...
In extractor theory, a randomness merger is a function which extractsrandomness out of a set of random variables, provided that at least one of them is...
with p = 1/2 by the von Neumann extractor, the earliest randomnessextractor, which actually extracts uniform randomness. Represent the observed process...
a "randomnessextractor", taking a potentially non-uniform value of low min-entropy and generating a value indistinguishable from a uniform random value...
uniformly at random from the domain, the output f ( x ) {\displaystyle f(x)} is distributed uniformly over the range. (Randomnessextractor). SWIFFT is...
as a strong randomnessextractor. The randomized function Ext: M → { 0 , 1 } l {\displaystyle M\rightarrow \{0,1\}^{l}} , with randomness of length r...
Decorrelation theory) and in the design of hardware random number generators. Equalisation Randomnessextractor Eigenvalue decomposition Whitening transformation...
of the overlap of two distributions. Probabilistic metric space Randomnessextractor Similarity measure Zero-knowledge proof Dodge, Y. (2003)—entry for...
{1}{2(1-\rho ^{2})}}(x^{2}+y^{2}-2\rho xy)\right].} The von Neumann extractor is a randomnessextractor that depends on exchangeability: it gives a method to take...
Quantum key distribution). Randomnessextractors achieve the same result, but use (normally) less randomness. Let X be a random variable over X {\displaystyle...
including cryptographic hashes, message authentication codes and randomnessextractors. Merkle–Damgård construction Sponge function Blackledge, J M (March...
Lavarand.com from Archive.org (pictures do not work) Cloudflare Blog post - Randomness 101: LavaRand in Production Cloudflare Blog post - LavaRand in Production:...
key. This is performed using a randomnessextractor, for example, by applying a universal hash function, chosen at random from a publicly known set of such...
theory (or Kolmogorov complexity). Kolmogorov randomness defines a string (usually of bits) as being random if and only if every computer program that can...
machines, which enhance randomness beyond what manual shuffling can achieve. With the rise of online casinos, digital random number generators (RNGs)...
known for his research in cryptography, including traitor tracing, randomnessextractors, private information retrieval, the security level and single-bit...
Yeast extracts consist of the cell contents of yeast without the cell walls; they are used as food additives or flavorings, or as nutrients for bacterial...
otherwise: the most recent shuffling machines are computer-controlled. The randomness or otherwise of cards produced from automatic shuffling machines is the...
Global Information