Using Hybrid Argument, I want to prove following equivalence: $$\{X,Y,Z\}\equiv \{X',Y',Z'\}$$

by proving following equivalences:
$\{X,Y,Z\}\equiv \{X,Y,Z'\}$(1)
$\{X,Y,Z'\}\equiv \{X,Y',Z'\}$(2)
$\{X,Y',Z'\}\equiv \{X',Y',Z'\}$ (3)
I know how to prove $\{Z\}\equiv\{Z'\}$, under what condition $\{Z\}\equiv\{Z'\}$ implies (1) ?

(I've changed my post since my problem has nothing to do with SMC (maybe it has nothing to do with cryptography either) and the way I presented the problem was confusing. )

  • $\begingroup$ In the third line what is $c(k.y)$? $\endgroup$
    – pg1989
    Jul 16, 2016 at 1:11
  • $\begingroup$ If X and Y are independent from Z you can make a simple reduction showing that distinguishing between {X,Y,Z} and {X,Y,Z′} implies distinguishing between Z and Z' (i.e. a proof by contradiction). If not, it is still possible that your claim holds, but you cannot use such a generic argument. $\endgroup$
    – antosecret
    Jul 17, 2016 at 5:40
  • $\begingroup$ For example, here is a case where your claim does not hold: if you choose z' at random (independently of x and y) and z as x + y where x comes from X and y comes from Y, then the two distributions in (1) are distinguishable while Z and Z' aren't. $\endgroup$
    – antosecret
    Jul 17, 2016 at 5:42
  • $\begingroup$ @antosecret Thanks, more specifically my question is, should Z be independent from {X} and {Y}, or be independent from {X,Y}. I guess (considering your example) the second one is correct $\endgroup$
    – Mhy
    Jul 17, 2016 at 13:13
  • $\begingroup$ @Mhy You are right. $\endgroup$
    – antosecret
    Jul 17, 2016 at 19:36


Your Answer

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

Browse other questions tagged or ask your own question.