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.
Hi gizmo686. Yes, what you propose is correct. But this requires that every time you iterate this process, you're required to find additional sources of weak data that is completely independent of the sources of weak data you used in the previous iterations. In that case, you're describing an extractor that requires multiple independent sources.
What the challenge was (and it looks like there was some progress a couple weeks ago), was that you'd like to produce multiple bits using only two independent sources, and no more than that!
Hi, this is the author of the blog post here. Fenomas raises a good point that I completely glossed over in my post, which is what it means for something to be random or unpredictable.
Indeed, one can't ever know for certain whether a sequence of numbers is random (after all, the universe we live in could be a deterministic finite state automaton). Instead, in this context of randomness extractors, we simply assume there is such thing as random numbers, and that there are sources of randomness that are more random than others. For example, a uniformly random sequence of 100 bits is more random than a random sequence of 100 bits where the last bit is always the XOR of the previous 99 bits.
Like someone else mentioned, we can quantify the quality of a random source by its entropy (more specifically, min-entropy, but ignore that for now). A randomness extractor operates under the premise that its inputs are sources with some amount of entropy (but maybe not full entropy). Its output is supposed to be a random source with full entropy (it distills "all the good stuff" from the sources).
One might find some philosophical difficulty with the idea that we can ever obtain sources with perfect randomness -- or know that we have. But the point of a randomness extractor is to say, if you believe that you have access to sources with some amount of entropy, then you can use an extractor to obtain sources with full entropy.
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.