Randomness extractor
From Wikipedia, the free encyclopedia
 |
This article is uncategorized.
Please help improve this article by adding it to one or more categories, so it may be associated with related articles (how?). Please remove this tag after categorizing. |
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.
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 non-deterministic, 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.
[edit] 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.
Randomness extraction is also used in some branches of complexity theory
