Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
up vote 1 down vote accepted

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.

share|improve this answer
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$? – student Oct 29 '13 at 6:41

Your Answer


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

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