Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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$? –  Emil Jeřábek Apr 28 '11 at 16:30
2  
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. –  Ryan O'Donnell May 27 '11 at 23:51
    
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. –  Anindya De Dec 10 '11 at 17:24
    
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? –  Anton Geraschenko Mar 2 '12 at 16:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.