Let $a,b,c,d$ be selected at random from $Z_q$. Consider the following two distributions $X_1$ and $Y_1$:

$X_1={(r_1\cdot a, r_2\cdot b, r_3\cdot c, (r_1+r_2-r_3)\cdot d)}$ where $r_1,r_2,r_3$ selected random from $Z_q$

$Y_1={(u_1,u_2,u_3,u_4)}$ where $u_1,u_2,u_3,u_4$ selected random from $Z_q$

I have two questions:

  • Are these two distributions computationally indistinguishable?
  • How should I formally write the proof?
  • 1
    $\begingroup$ Looks like homework; I'll give a hint: the first distribution seems to have less entropy, i.e., less random values picked. Can you invent a way to check that? $\endgroup$ – Ruben De Smet Jun 1 '18 at 20:10
  • 2
    $\begingroup$ No, this is not a homework assignment. I am working on a research project and things are boiled down to this. $\endgroup$ – mohsen pourpouneh Jun 1 '18 at 20:28
  • 3
    $\begingroup$ This question is curiously similar to crypto.stackexchange.com/questions/59722/leak-information so maybe you two can collaborate if you are taking the same class. $\endgroup$ – kodlu Jun 2 '18 at 2:08
  • 1
    $\begingroup$ Assuming that "selected (at) random" means with uniform distribution, what are the probabilities of the first components of $X_1$ rsp. $Y_1$ to be zero? What are the probabilities for $X_1$ rsp. $Y_1$ to be zero? $\endgroup$ – j.p. Jun 2 '18 at 19:25

Your Answer

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

Browse other questions tagged or ask your own question.