- Randomness extractor
A randomness extractor is a function which, when applied to a high-entropy source (such as radioactive decay, or thermal noise), generates a random output that is shorter, yet uniformly distributed. In other words, outputting a completely random sample from a semi-random input. [http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=796582]
The goal of this process is to generate a truly random output stream, which could then be considered as being a true random number generator (
TRNG ).The only restriction for successful application of the extractor is that the high-entropy source is
nondeterministic , in other words, there is no way in which the source can be fully controlled, calculated or predicted.No single randomness extractor currently exists that has been proven to work when applied to "any" type of high-entropy source.
Examples
Von Neumann extractor
Perhaps the earliest example is due to
John Von Neumann . His extractor took successive pairs of consecutive bits from the input stream. If the two bits matched, no output was generated. If the bits differed, the value of the first bit was output. The Von Neumann extractor can be shown to produce a uniform output even if the distribution of input bits is not uniform so long as each bit has the same probability of being one and there is nocorrelation between successive bits. [John von Neumann. Various techniques used in connection with random digits. Applied Math Series, 12:36–38, 1951.]Cryptographic hash
Another approach is to fill a buffer with bits from the input stream and then apply a
cryptographic hash to the buffer and use its output. This approach generally depends on assumed properties of the hash function.Applications
Randomness extractors are used most widely in cryptographic applications, whereby a
cryptographic hash function would be applied to a high-entropy source to yield an encrypted result. The result is expected to be truly random, however due to the fact that the source in most cases is a known or constructed input, the security and/or 'randomness' of the source data can never be guaranteed.Randomness extractors have played a part in recent developments in
quantum cryptography , where photons are used by the randomness extractor to generate secure random bits. [http://newsroom.spie.org/x4741.xml?highlight=x535]Randomness extraction is also used in some branches of
complexity theory .References
* [http://www.cs.haifa.ac.il/~ronen/online_papers/survey.ps Recent developments in explicit constructions of extractors] , Ronen Shaltiel
ee also
*
Decorrelation
*Extractor
*Hardware random number generator
Wikimedia Foundation. 2010.
