[fenomas]

Can someone in the know post a conceptual description of roughly what's going on here?

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?

[ThrustVectoring]

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."

[bbrazil]

To expand on that a little, the main property you're looking for is that if I give you the N random numbers that have already been generated you can't predict what the next one will be with certainty beyond random chance.

https://en.wikipedia.org/wiki/Cryptographically_secure_pseud... has more detail.

[fenomas]

Naturally, but what does that have to do with what I asked?

[henrytcs]

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.

I hope this makes sense.

[fenomas]

Ahh, so it's basically the difference between theory and practice. Thanks for explaining!