<p>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.</p>

<p>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.)</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

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

<ul>
<li><a href="http://www.cs.toronto.edu/~thomasw/papers/min.pdf" rel="nofollow">The Complexity of Estimating Min-Entropy</a>.  Thomas Watson.  CC 2015.</li>
</ul>

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

<p>The literature on cryptographic pseudorandom number generators has lots more on this topic.</p>

CC BY-SA 3.0
2015-01-13T15:50:48.437Z
I don't really understand your answer. There are non-trivial algorithms for estimating entropy based on samples generated by a source (http://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 https://people.cs.umass.edu/~mcgregor/papers/06-oracles.pdf). I haven't worked out details though.
arnab
CC BY-SA 3.0
2015-01-13T17:28:17.820Z
@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).
D.W.
CC BY-SA 3.0
2015-01-13T17:32:17.847Z
Here is more on the complexity of estimating the min-entropy http://www.cs.toronto.edu/~thomasw/papers/min.pdf. The upshot is it's hard, particularly $\mathsf{SBP}$-complete.
epsfooling
CC BY-SA 3.0
2015-01-13T17:37:02.540Z
Thanks, @epsfooling!  I've updated my answer accordingly.
D.W.
CC BY-SA 3.0
2015-01-13T19:31:31.833Z
@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.
arnab
CC BY-SA 3.0
2015-01-13T19:32:50.650Z
@arnab, what's your $n$?  In other words, what does $n$ represent, in your statement?  How are you getting $o(n)$ complexity?  The number of samples needed is exponential in the entropy of the source.
D.W.
CC BY-SA 3.0
2015-01-13T14:53:49.510Z
2015-01-13T17:36:52.807Z
2015-01-13T17:36:52.807Z
D.W.
<p>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.</p>

<cc.complexity-theory><randomness><derandomization>
Extractors in Practice: How to Determine the Min-Entropy in the Source Distribution
epsfooling
# Extractors in Practice: How to Determine the Min-Entropy in the Source Distribution

(Asked by: username_0 on 2015-01-12)

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.

**Tags:** cc.complexity-theory, randomness, derandomization

---

## 1 answers

### Answer by username_1 on 2015-01-13. Score: 1 | Accepted answer

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 Complexity of Estimating Min-Entropy](http://www.cs.toronto.edu/~thomasw/papers/min.pdf). Thomas Watson. CC 2015.

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.

> **Comments:**
> **username_2**: I don't really understand your answer. There are non-trivial algorithms for estimating entropy based on samples generated by a source (http://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 https://people.cs.umass.edu/~mcgregor/papers/06-oracles.pdf). I haven't worked out details though.  
> **username_1**: @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).  
> **username_0**: Here is more on the complexity of estimating the min-entropy http://www.cs.toronto.edu/~thomasw/papers/min.pdf. The upshot is it's hard, particularly $\mathsf{SBP}$-complete.  
> **username_1**: Thanks, @epsfooling!  I've updated my answer accordingly.  
> **username_2**: @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.  
> **username_1**: @arnab, what's your $n$?  In other words, what does $n$ represent, in your statement?  How are you getting $o(n)$ complexity?  The number of samples needed is exponential in the entropy of the source.  

---

