2
$\begingroup$

Assume that we have a probability distribution $P(X,Y)$ for the joint probability of random variables $X$ and $Y$. Let $P(Y, Z)$ be analogous distribution for $Z$ and $Y$. Based on these we can define a joint probability distribution of $P(X,Y,Z)$.

Let, $P'(X,Y)$ and $P'(Y,Z)$ be analogously probability distributions where it is known that $P'(X,Y)$ is computationally indistinguishable from $P(X,Y)$ and $P(Y, Z)$ is computationally indistinguishable from $P'(Y,Z)$. Based on these we define a joint probability distribution $P'(X,Y,Z)$.

Do the indistinguishability conditions on the initial distributions imply that $P(X,Y,Z)$ is computationally indistinguishable from $P'(X,Y,Z)$?

$\endgroup$

1 Answer 1

1
$\begingroup$

Obviously not; one can easily define probability distributions $P$ and $P'$ such that $P(X,Y)=P'(X,Y)$ and $P(Y,Z)=P'(Y,Z)$, but $P(X,Y,Z) \ne P'(X,Y,Z)$

For one such example, take $P$ be the probability distinguish where $X$, $Y$ and $Z$ are uniformly and independently distributed boolean variables; and $P'$ be the probability distribution that $X$ and $Y$ are uniformly and independently distributed boolean variables, and $X=Z$ with probability 1.

Now, $P(X,Y)=P'(X,Y)$ (because, in both probability distributions, each possible combination of boolean variables will occur with probability 0.25), and similarly $P(Y,Z)=P'(Y,Z)$.

However, $P(X,Y,Z) \ne P'(X,Y,Z)$ in an computationally easy manner, because with a single sample of the probability distribution, we can check if $X = Z$ (can guess $P$ if it is false, and $P'$ if it is true); that gives us a distinguisher that succeeds with high probability.

$\endgroup$
1
  • $\begingroup$ Yes, your answer is clearly correct in terms that were used in the question. However, it seems that I have put it wrong in the first place. What about the case when we are interested in $P((X,Y),(Y,Z))$ such that $P((X=x,Y=y), (Y=y, Z=z)) = P((X=x, Y=y)) P((Y=y, Z=z)|X=x, Y=y)$ and $P((X=x,Y=y), (Y=y_2, Z=z)) = 0$ if $y \neq y_2$? $\endgroup$
    – student
    Commented Oct 29, 2013 at 6:41

Your Answer

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

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