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)?

$\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$ 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$ 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$
    – Anindya De
    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$ Mar 2, 2012 at 16:01

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.