Purifying spoiled randomness with spoiled randomness(mittheory.wordpress.com) |
Purifying spoiled randomness with spoiled randomness(mittheory.wordpress.com) |
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!
The last time I read up on randomness, I was given to believe that it's not really an observable quantity - that is, a sequence of numbers is random only to the extent that nobody's found a pattern in them yet, and as such, the most rigorous way we have of testing strong RNGs is to run them through a battery of test for the sorts of patterns that are known to show up in weak RNGs. But that sounds far-removed from the situation the article describes, where this or that generator can be proven to be perfect or imperfect.
Is this the gap between theoretical analysis and real-world implementations, or am I misunderstanding something more fundamental?
https://en.wikipedia.org/wiki/Cryptographically_secure_pseud... has more detail.
Presumably I'm missing something. Can someone tell me what it is?
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...
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.
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.
I hope this makes sense.