<p>In conditional min-entropy extractor, there is a joint distribution $(X,Y)$ such that if the average min-entropy (for some appropriate notion of it) ${\rm H}_\infty(X|Y)$ is large, then ${\rm Ext}(X, Z)$, where $Z$ is a seed distribution that is <em>independent</em> from <em>both</em> $X$ and $Y$, looks random. This can be equivalently viewed as an "adversary", who has some limited knowledge $Y$ of $X$, cannot predict ${\rm Ext}(X, Z)$.</p>

<p>My question concerns the case where the adversary knows something about $Z$. I model this situation as that there is another random variable $M$ (say of $O(1)$ bits), that is allowed to be correlated with both $X$ and $Z$. Of course, if there is no structure about $M$, then there is no hope. As an example, suppose that $M = {\rm Ext}_1(X, Z)$ where $\rm Ext_1$ is the projection of $\rm Ext$ to its first bit, then clearly one cannot hope that the joint distribution $(M, Y, {\rm Ext}(X, Z))$ looks random.</p>

<p>My question is then the case where we do know something about $M$. Specifically, consider the case that the correlation between any bit of $M$ and any bit of ${\rm Ext}(X, Z)$ is small. In other words, $(M, {\rm Ext}(X, Z))$ is close to $(M, U)$ where $U$ is the uniform distribution (or modeling in another way, $(M, {\rm Ext}(X, Z))$ is close to $(U, {\rm Ext}(X, Z))$.</p>

<p>Do we know extractor constructions in this situation? Any pointer or reference? This problem seems pretty natural.</p>

<p>Thanks.</p>

CC BY-SA 3.0
2015-07-31T14:03:40.763Z
I'm not sure what you are asking. If you *assume* that $(M,Ext(X,Z))$ is close to $(M,U)$, you are done, correct? If you just assume that the correlation between $M$ and any bit if $Ext(X,Z)$ is small, then you cannot conclude that $Ext(X,Z)$ looks random given $M$ since, for example, $M$ could be the parity of all the bits of $Ext(X,Z)$. Can you clarify the assumption and the property you want from the construction?
Adam Smith
CC BY-SA 3.0
2015-07-31T14:14:40.297Z
Thank you Adam for the comments . Also thanks for the second part. It's my fault that I am not clear about the question at this point and sorry for confusion. Before I think more and edit, just raise a probably naive point: I want to conclude $(M, Y, Ext(X, Z))$ and $(M, Y, U)$ are close, from $(M, Ext(X, Z))$ is close to $(M, U)$. Would that additional Y possibly reveal more information then?
Xi Wu
<cr.crypto-security><pseudorandomness><pseudorandom-generators><extractors>
Extractor with somewhat corrupted seeds
Xi Wu
# Extractor with somewhat corrupted seeds

(Asked by: username_0 on 2015-07-29)

In conditional min-entropy extractor, there is a joint distribution $(X,Y)$ such that if the average min-entropy (for some appropriate notion of it) ${\rm H}\_\infty(X|Y)$ is large, then ${\rm Ext}(X, Z)$, where $Z$ is a seed distribution that is *independent* from *both* $X$ and $Y$, looks random. This can be equivalently viewed as an "adversary", who has some limited knowledge $Y$ of $X$, cannot predict ${\rm Ext}(X, Z)$.

My question concerns the case where the adversary knows something about $Z$. I model this situation as that there is another random variable $M$ (say of $O(1)$ bits), that is allowed to be correlated with both $X$ and $Z$. Of course, if there is no structure about $M$, then there is no hope. As an example, suppose that $M = {\rm Ext}\_1(X, Z)$ where $\rm Ext\_1$ is the projection of $\rm Ext$ to its first bit, then clearly one cannot hope that the joint distribution $(M, Y, {\rm Ext}(X, Z))$ looks random.

My question is then the case where we do know something about $M$. Specifically, consider the case that the correlation between any bit of $M$ and any bit of ${\rm Ext}(X, Z)$ is small. In other words, $(M, {\rm Ext}(X, Z))$ is close to $(M, U)$ where $U$ is the uniform distribution (or modeling in another way, $(M, {\rm Ext}(X, Z))$ is close to $(U, {\rm Ext}(X, Z))$.

Do we know extractor constructions in this situation? Any pointer or reference? This problem seems pretty natural.

Thanks.

**Tags:** cr.crypto-security, pseudorandomness, pseudorandom-generators, extractors
> **Comments:**
> **username_1**: I'm not sure what you are asking. If you *assume* that $(M,Ext(X,Z))$ is close to $(M,U)$, you are done, correct? If you just assume that the correlation between $M$ and any bit if $Ext(X,Z)$ is small, then you cannot conclude that $Ext(X,Z)$ looks random given $M$ since, for example, $M$ could be the parity of all the bits of $Ext(X,Z)$. Can you clarify the assumption and the property you want from the construction?  
> **username_0**: Thank you Adam for the comments . Also thanks for the second part. It's my fault that I am not clear about the question at this point and sorry for confusion. Before I think more and edit, just raise a probably naive point: I want to conclude $(M, Y, Ext(X, Z))$ and $(M, Y, U)$ are close, from $(M, Ext(X, Z))$ is close to $(M, U)$. Would that additional Y possibly reveal more information then?  

---

## 0 answers

