Amit (guest) 30 Jan 2020 11:11
In the solution to question 3.b, it is mentioned that from witness indistinguishably, you deduce that you cannot distinguish between the following distributions:
1. {P(w_1),V*(x), P(w_1)V*(x)} =S_1,1
2. {P(w_o),V*(x), P(w_1)V*(x)} = S_0,1
I understand why if this claim is correct the claim in the question is correct.
But, I try to formulate why this claim is correct and do not manage to do so:
1. Assume there is a PPT A that can distinguish between S_1,1 and S_0,1 with non-negligible probability.
2. Now I would like to use A to distinguish between {P(w_1)V*(x)} and {P(w_0)V*(x)} and by witness indistinguishability deduce that this A does not exist.
3. Our distinguisher B will get y which is either from p(w_1)V*(x) or P(w_0)V*(x)
4. Now I would like to send A {y,P(w_1)V*(x)} and return whatever A does.
4. My problem is that I cannot really sample interaction with the P and be sure that he is using w_1. Or can I?
Thanks,
