# deterministic randomness extractor and privacy

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.

• 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 Apr 24 '14 at 3:50
• @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 Apr 24 '14 at 15:54
• Yes, because an extractor could in particular be applied to any particular member of that class. $\,$ However, you won't necessarily be able to achieve that upper bound. $\;\;\;$ – user6973 Apr 24 '14 at 17:01
• @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 Apr 24 '14 at 20:35
• There is not necessarily a worst distribution. $\:$ The uniform distributions on the sets {"00","10"},{"00","11"},{"00","01"} each have one bit of entropy and there is no deterministic extractor that works on all three of them. $\;\;\;\;$ – user6973 Apr 24 '14 at 21:21