5
$\begingroup$

Let $X,X',Y,Y'$ be some distribution ensembles such that $X\sim X'$ and $Y\sim Y'$, where $\sim$ means computational indistinguishable. Define $(X,Y)$ be the distribution ensemble over $\{0,1\}^{2n}$ for each $n$ such that $P[(X,Y)=(x,y)]=P[X=x]*P[Y=y]$ and $(X',Y')$ similarly.

My question is: Does $(X,Y)\sim (X', Y')$?

I can prove this if all the distributions are polynomial sampleable by a hybrid argument, that is we can show that $(X,Y)\sim (X,Y')$ since if there exist distinguisher $D$ to these ensembles then for a given $y$ we can first sample a $x$ from $X$ and feed $(x,y)$ to $D$, but what if $X$ is not polynomial sampleable?

(I'm new to cryptography, so I'm sorry if this is trivial)

$\endgroup$
  • $\begingroup$ I'm pretty sure that this isn't trivial to at least 99% of the population of the earth. We've got nothing against "trivial" questions here, as long as they aren't dupes. $\endgroup$ – Maarten Bodewes Mar 28 '16 at 11:14
  • $\begingroup$ What is the problem if $X$ is not polynomial sampleable? In this case cannot you sample that $x$ to send the pair $(x, y)$ to $D$ ? $\endgroup$ – Hilder Vítor Lima Pereira Mar 28 '16 at 12:18
  • $\begingroup$ Hi @Vitor: If $X$ is not efficiently sampleable, then you can only guess $x$ from some distribution, however in this case the probability $P[D(X,Y)=1]$ will not necessarily distinguishable from $P[D(X,Y')=1]$. My question is can we still prove they are distinct enough in this case? or to find some distribution to disapprove it? $\endgroup$ – Paul Mar 28 '16 at 22:08
3
$\begingroup$

If $(X \approx X')$ and $(Y \approx Y')$, then it holds that $(X \times Y) \approx (X' \times Y')$. Indeed, let us consider an adversary which is able to distinguish $(X \times Y)$ from $(X' \times Y')$ with probability $1/2+\varepsilon$; the adversary returns $0$ if he estimates that the sample comes from $(X' \times Y')$, and $1$ else. Indeed, let us consider an adversary which is able to distinguish $(X \times Y)$. Given access to such an adversary, we construct a distinguisher $D$ for both $(X,X')$ and $(Y,Y')$ as follows: $D$ asks for a challenge $x$ to the first challenger, which comes from $X$ with probability $1/2$, and from $X'$ with probability $1/2$. Similarly, $D$ asks for a challenge $y$ to the second challenger, which comes from $Y$ with probability $1/2$, and from $Y'$ with probability $1/2$. Then, it sends $(x,y)$ to the adversary, which returns a bit $b$. $D$ simply forward $b$ to both challengers. Note that with probability $1/2$, $x$ and $y$ come from the same side of their pair of distributions (id est, with probability $1/2$ either $(x,y)$ comes from $(X,Y)$ or $(x,y)$ comes from $(X',Y')$). In such a case, the adversary returns the correct guess $b$ with probability $1/2 + \varepsilon$; in the other case, which happens with probability $1/2$ too, the adversary returns the correct guess with probability (at least) $1/2$. Overall, given two challenges $x$ and $y$, and by feeding the pair $(x,y)$ to the adversary, $D$ wins the challenge against both challengers with probability $1/2(1/2 + 1/2+\varepsilon)=1/2+\varepsilon/2$. Hence, up to a factor $2$ in the distinguishing advantage, being able to between $(X,Y)$ and $(X',Y')$ implies being able to distinguish between $X$ and $X'$, as well as between $Y$ and $Y'$.

$\endgroup$
  • $\begingroup$ the proposition is true just when $X$ ans $Y$ are independent. (i.e. $P[(X,Y)=(x,y)]=P[X=x].P[Y=y]$ ). am I right? which part of your proof would change if $X$ and $Y$ where dependent? $\endgroup$ – Mhy Jul 15 '16 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.