<p>I came across this late. Don't know if this question still matters. I am posting this as an answer since it is too long for a comment. </p>

<p>If n can be 1 but m is not too large (say, at most a small exponential in the min-entropy), a random function will be a good extractor with high probability. It will cost you a factor of something like log m in the min-entropy. </p>

<p>However, for large values of n, you should be able to find a good deterministic  extractor no matter how large m is since, once you condition on x, the distribution on outputs is IID. In particular, it is symmetric, so you can use as idea like von Neumann's trick or its generalizations to extract a small number of random bits just from the <em>ordering</em> of the elements. That might be enough to get the seed for a strong randomness extractor which could extract the rest of the randomness from the source. You have to be careful, but the idea would be to rely heavily on the IID structure to get a a deterministic extractor. Don't know if that's good enough for the application. </p>

CC BY-SA 3.0
2016-04-13T13:52:43.987Z
2016-04-13T13:52:43.987Z
Adam Smith
<p>Suppose $X$ is a message which takes values on the set $\{x_1, \dots, x_m\}$ with probability distribution $P_X$. We transmit the message $X$ over  the channel $P_{Y|X}$ which outputs $Y$ taking values on finite alphabet $\mathcal{Y}$. Suppose we take $n$ independent samples from channel output; namely, $Y^n=(Y_1, Y_2, \dots, Y_n)$ with distribution $\prod_{i=1}^nP_{Y|X}(y_k|x)$ where $x$ is the message sent over the channel.</p>

<p>Hence, we have $m$ distributions $\{P_{Y^n|X}(\cdot|x_1), \dots, P_{Y^n|X}(\cdot|x_m)\}$. I am looking for a deterministic randomness extractor which works for all of these $m$ distributions, that is, a randomness $Ext:\mathcal{Y^n}$ such that for given $Y^n$ distributed as one of these $m$ distribution $Ext(Y^n)$ is $\epsilon-$close to uniform distribution over $\{0,1\}^r$ (in total variation distance sense). </p>

<p>What is the largest random bits that we can extract, i.e., the largest $r$? 
Is that $\min_{x}H_{\infty}(P_{Y^n|X}(\cdot|x))$?</p>

<p>The motivation of this comes from privacy.  </p>

CC BY-SA 3.0
2014-04-24T03:50:32.160Z
What if $Y=x$ deterministically? Then there is no entropy in $Y^m$. I don't see how your assumptions give anything beyond the usual problem of extraction. You want to deterministically extract from m iid samples from one of m distributions.
Thomas Steinke
CC BY-SA 3.0
2014-04-24T15:54:13.213Z
@Thomas, can you plz specify which assumption you mean? yes this is so similar to the usual extraction, I just wanted to make sure that if instead of one distribution, we want to extract pure random bits from a class of distribution, then we can extract at best the minimum over the class of distribution  of many random bits, i.e., minimum over $m$ distributions of min-entropy. Is that true?
SAmath
CC BY-SA 3.0
2014-04-24T20:35:05.907Z
@RickyDemer thanks, but i cant get why we cant achieve this. Suppose we apply the extractor to the the worst distribution which yields the shortest random bits, why we can not achieve this when we apply that extractor to any other distribution
SAmath
CC BY-SA 3.0
2014-04-24T21:22:03.930Z
we have finite number of distribution, so one of them yields shorter random bits, right?
SAmath
CC BY-SA 3.0
2014-04-27T18:35:02.853Z
@RickyDemer do you have any idea on how to prove the converse result, no deterministic result for the family of distribution can extract more random bits than min of min-entropy?
SAmath
<cr.crypto-security><randomness><it.information-theory><extractors><privacy>
deterministic randomness extractor and privacy
SAmath
# deterministic randomness extractor and privacy

(Asked by: username_0 on 2014-04-23)

Suppose $X$ is a message which takes values on the set $\{x\_1, \dots, x\_m\}$ with probability distribution $P\_X$. We transmit the message $X$ over the channel $P\_{Y|X}$ which outputs $Y$ taking values on finite alphabet $\mathcal{Y}$. Suppose we take $n$ independent samples from channel output; namely, $Y^n=(Y\_1, Y\_2, \dots, Y\_n)$ with distribution $\prod\_{i=1}^nP\_{Y|X}(y\_k|x)$ where $x$ is the message sent over the channel.

Hence, we have $m$ distributions $\{P\_{Y^n|X}(\cdot|x\_1), \dots, P\_{Y^n|X}(\cdot|x\_m)\}$. I am looking for a deterministic randomness extractor which works for all of these $m$ distributions, that is, a randomness $Ext:\mathcal{Y^n}$ such that for given $Y^n$ distributed as one of these $m$ distribution $Ext(Y^n)$ is $\epsilon-$close to uniform distribution over $\{0,1\}^r$ (in total variation distance sense).

What is the largest random bits that we can extract, i.e., the largest $r$?
Is that $\min\_{x}H\_{\infty}(P\_{Y^n|X}(\cdot|x))$?

The motivation of this comes from privacy.

**Tags:** cr.crypto-security, randomness, it.information-theory, extractors, privacy

> **Comments:**
> **username_1**: What if $Y=x$ deterministically? Then there is no entropy in $Y^m$. I don't see how your assumptions give anything beyond the usual problem of extraction. You want to deterministically extract from m iid samples from one of m distributions.  
> **username_0**: @Thomas, can you plz specify which assumption you mean? yes this is so similar to the usual extraction, I just wanted to make sure that if instead of one distribution, we want to extract pure random bits from a class of distribution, then we can extract at best the minimum over the class of distribution  of many random bits, i.e., minimum over $m$ distributions of min-entropy. Is that true?  
> **username_0**: @RickyDemer thanks, but i cant get why we cant achieve this. Suppose we apply the extractor to the the worst distribution which yields the shortest random bits, why we can not achieve this when we apply that extractor to any other distribution  
> **username_0**: we have finite number of distribution, so one of them yields shorter random bits, right?  
> **username_0**: @RickyDemer do you have any idea on how to prove the converse result, no deterministic result for the family of distribution can extract more random bits than min of min-entropy?  

---

## 1 answers

### Answer by username_2 on 2016-04-13. Score: 1

I came across this late. Don't know if this question still matters. I am posting this as an answer since it is too long for a comment.

If n can be 1 but m is not too large (say, at most a small exponential in the min-entropy), a random function will be a good extractor with high probability. It will cost you a factor of something like log m in the min-entropy.

However, for large values of n, you should be able to find a good deterministic extractor no matter how large m is since, once you condition on x, the distribution on outputs is IID. In particular, it is symmetric, so you can use as idea like von Neumann's trick or its generalizations to extract a small number of random bits just from the *ordering* of the elements. That might be enough to get the seed for a strong randomness extractor which could extract the rest of the randomness from the source. You have to be careful, but the idea would be to rely heavily on the IID structure to get a a deterministic extractor. Don't know if that's good enough for the application.


---

