Purifying spoiled randomness with spoiled randomness (opens in new tab)

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!

You're on the right track with randomness. "Random number" is a bad word - it implies that randomness is a property of the number, rather than the more complete picture of "you can expect that people will be unable to predict the number, given a certain set of background information."

Whether a hash function is cryptographic or not is irrelevant: either way, it's computable, therefore you can reverse it and get information about the original data you hashed. Because that data was only weakly random, it's not independent of future data from the same sources, so you can compute what future results of the hashing algorithm are likely to be.

Obviously this is impractical in the real world, but in TCS randomness is defined as algorithmic randomness, which completely ignores the question of running time. Randomness is a mathematical concept, something can't suddenly become non-random because you gained a faster computer. For more information see: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogor...

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.