8
$\begingroup$

Person A has a source $W$ with min-entropy($W$) = $k$. He also has an extra piece of information about the random source, denoted with $y$, such that min-entropy($W|y$) = $k/3$.

The adversary doesn't know $y$.

Can person A use a (strong) randomness extractor on the source $W$, where the extractor requires the min-entropy to be $k$?

For person A the output would not be close to uniform since the min-entropy given $y$ is actually $k/3$. However, for the adversary the min-entropy of $W$ is $k$. So is my reasoning correct that for the adversary the output is still close to uniform (i.e. $\epsilon$-close)?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Maybe I’m missing something, but why should $y$ have anything to do with properties of the output if you apply an extractor just on $W$? $\endgroup$ Commented Apr 28, 2011 at 16:30
  • 2
    $\begingroup$ I believe the answer to 'Omega's question is yes. To answer 'none's question below, a "source" is just another term for a random variable. $\endgroup$ Commented May 27, 2011 at 23:51
  • $\begingroup$ Even if conditioned on y, the entropy of W is zero, the output would continue to look uniform to an adversary who does not know what y is. $\endgroup$ Commented Dec 10, 2011 at 17:24
  • $\begingroup$ none (mathoverflow.net/users/14785/none) says in an answer (now moved to this comment): I can't make much sense of this question. I thought min-entropy was something that applies to a (discrete) probability distribution, not a "source". So W|y is just a different distribution. Can you make the question more precise? $\endgroup$ Commented Mar 2, 2012 at 16:01

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.