I once asked on CSTheory how to do this. One comment pointed me to the paper you mention. There’s also an answer pointing to some more recent work on how to compute not just cardinalities but also the sets : http://cstheory.stackexchange.com/q/553/236

Yes, the first problem can be solved for any f. But see problem 2. :)

Hi npc,

Sorry for the late response!

Yes, you can think of weak randomness is that on average, there is less than 1 bit of entropy per bit of data. One example of this might be, even though the first three bits of the string are completely uniform, the fourth bit is a complicated function of the first three. However you have no way of knowing what that complicated function is, nor where this “dependent bit” may be.

Re: using cryptographic hash function. I think something like this is used in practice, but the problem is that this isn’t a theoretically sound method for extracting randomness. The problem is that if you’re given a fixed function (say, for example, SHA1 or AES), then there always *exists* a weak random source X such that SHA1(X) or AES(X) is not uniformly random. Whether we as human beings can find X or not is another question, but theoretically it is not a hard task.

This work instead focuses on getting sound theoretical guarantees. You need a function that takes in two independent sources of randomness and combines them together, such that no matter what sorts of dependencies exist within each source, the function will squeeze it out. Furthermore, there are no cryptographic assumptions needed!

Do you have to rewrite your RNG code? It depends on what sorts of guarantees you’re looking for. If you’re looking for sound mathematical guarantees that your randomness extractor is always going to give you near uniform randomness, then the RNG in the C compiler is not going to cut it, nor is using some fixed function such as SHA1 or AES. However, “in practice”, probably using a hash function such as SHA will work for most applications. It’s only when you’re writing code that will protect, say, a power plant that you might want to look into something a little more secure.

It seems to me that a weak source of randomness means you have less than 1 bit of entropy for each bit of data in a “random” string. Consequently, the trick is to “squeeze” out the predictable portion. My understanding is that in practice the most common way to do this is to use a cryptographically secure hash function. Why is this new method better? Is it because it doesn’t rely on the strength of the cryptography? Even if the hash could be reversed, it would merely reveal one (of several, probably) weakly random input strings. How does that help one predict the next set of random bits? Yes, there’s a correlation bit-by-bit with the next input string to be hashed, but the whole idea of hashing it is to eliminate that correlation, right? What am I missing? Should I be preparing to rewrite my RNG code? Feel free to point me to some place that already explains this. I couldn’t find such a thing on my own.

Thanks in advance.