# Does concatenation of two pair computational indistinguishable distributions still indistinguishable?

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)

• 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. Mar 28 '16 at 11:14
• 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$ ? Mar 28 '16 at 12:18
• 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?
– Paul
Mar 28 '16 at 22:08

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'$.
• 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?