2
$\begingroup$

One of the main parameters in the construction of extractors is $k$, the min-entropy of the source distribution. In practice, suppose we want to extract randomness from a given source $S$. How do we determine $k$ in this source $S$? More generally, how do we quantify the amount of (extracted) randomness in the output distribution of the extractor.

$\endgroup$
1
$\begingroup$

In practice, if you want to extract randomness from a source $S$, you don't use an extractor. Instead, you use a cryptographic hash function and hash the data from the source. (This is how cryptographic-strength pseudo-random number generators distill randomness from many non-uniformly distributed sources of randomness.) This can be proven safe in the random oracle model.

Of course, if you care mostly about theoretical bounds, extractors are better because they provide provable bounds without requiring cryptographic assumptions, so theoretical work will naturally focus on extractors -- but if you want to do this in practice, that consideration is less important. If you want to do this in practice, I recommend you use a cryptographic hash function, as the assumptions are reasonable and you get something that does not waste any entropy. (And before you reject the idea of depending upon cryptographic assumptions: Hey, if it's good enough to protect e-commerce and banks and classified documents, it's probably good enough for your purposes.)

If you use a cryptographic hash function, the bottom line (essentially) is that all of the entropy of the source is preserved (up to the security level of the cryptographic hash function). So, quantifying the amount of extracted randomness comes down to quantifying how much randomness is present in the source.

There is no good black-box way to determine the min-entropy of the source distribution. So, in practice, you don't try to determine the min-entropy of a source through observational methods (e.g., observing many samples and then doing something). Instead, you need to have a model of how the source works, and to derive estimates of its entropy based upon that model. That model might be based upon the physics of the source or other domain-specific assumptions. This is not a question that algorithms can help you with much.

Why is it hard to estimate the min-entropy of a source? Consider two sources: $S_1$ outputs a random $1000$-bit value $x$ (distributed uniformly at random); $S_2$ picks a random $128$-bit value $k$, then uses AES in CTR mode (a secure pseudorandom generator) to stretch $k$ to a $1000$-bit value $y$, and outputs $y$. Notice that, assuming AES is secure, there is no feasible way to distinguish source $S_1$ from source $S_2$ by just observing their outputs: any algorithm for distinguishing the two sources would require something like $2^{128}$ steps of computation. However, the min-entropy of $S_1$ is very different from the min-entropy of $S_2$ ($1000$ bits vs $128$ bits). This example shows that computing the min-entropy of a source is a difficult in general, so you should not expect to find any efficient algorithm to do that for you based solely on observing some outputs from the source.

For a more rigorous treatment of the complexity of estimating the min-entropy, see e.g. the following paper:

The bottom line is that it's hard. (Thanks to epsfooling for pointing me to this paper.)

The literature on cryptographic pseudorandom number generators has lots more on this topic.

$\endgroup$
  • $\begingroup$ I don't really understand your answer. There are non-trivial algorithms for estimating entropy based on samples generated by a source (cseweb.ucsd.edu/~dasgupta/papers/jent0409.pdf). For estimating min-entropy, you could use the relation $-\frac{1}{2}\log \|p\|_2^2 \leq H_\infty(p) \leq - \log \|p\|_2^2$, where $\|p\|_2^2$ is the collision probability and then estimate $\|p\|_2^2$ (as in Lemma 4 of people.cs.umass.edu/~mcgregor/papers/06-oracles.pdf). I haven't worked out details though. $\endgroup$ – arnab Jan 13 '15 at 15:50
  • $\begingroup$ @arnab, yes, there are algorithms, but they all require exponentially many samples (exponential in the entropy), so I would not consider them efficient algorithms. Your proposed approach falls into that category. If we have a uniform distribution with $k$ bits of entropy, the collision probability is $1/2^k$, so to estimate the collision probability, you'll need $\Omega(2^k)$ samples. My example in the next-to-last paragraph shows that this has to be the case, no matter what algorithm you consider (assuming the existence of strong crypto / one-way functions). $\endgroup$ – D.W. Jan 13 '15 at 17:28
  • $\begingroup$ Here is more on the complexity of estimating the min-entropy cs.toronto.edu/~thomasw/papers/min.pdf. The upshot is it's hard, particularly $\mathsf{SBP}$-complete. $\endgroup$ – epsfooling Jan 13 '15 at 17:32
  • $\begingroup$ Thanks, @epsfooling! I've updated my answer accordingly. $\endgroup$ – D.W. Jan 13 '15 at 17:37
  • $\begingroup$ @D.W., epsfooling : thanks! I guess our definitions of "efficient" differ :) For me, any algorithm with $o(n)$ sample complexity and a provable approximation factor is non-trivial, and the techniques of Batu et al. should yield such an algorithm. $\endgroup$ – arnab Jan 13 '15 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.