|
That's the right intuition. But here we have to distinguish between information theoretic randomness and computational randomness (also known as algorithmic randomness). In the former, we're guaranteed that the output is actually statistically close to uniform randomness, and no statistical test, no matter how much computing time it uses, can predict any bit of the output. In the latter, the output can actually be far from uniformly random, but it has the guarantee that no efficient program (i.e. polynomial time algorithm) can distinguish between the output, and true uniform randomness. A randomness extractor guarantees the former (i.e. information theoretic randomness), whereas a cryptographic hash function can only, at best, guarantee the latter (i.e. computational randomness). One might say, for all intents and purposes, we only care about computational randomness anyways. The problem is, cryptographic hash functions only work under complexity assumptions that we don't know to be true. These complexity assumptions have a similar flavor to the P vs NP question, which you might've heard of. On the other hand, we can actually outright prove that randomness extractors work, and they output information theoretic randomness -- no complexity assumptions required! So, long story short, we'd like to theoretically ensure, and prove outright, that we can take weak sources of randomness, and amplify them to strong sources of randomness. Randomness extractors do just that. |