some times when see a problem like : if some G is a PRG then G' is also a PRG. we prove this by reduction in the following way: we assume there is a Distinguisher A for G' and we construct distinguisher D for G. and then we prove that the probability that D returns 1 is negligible using out assumption about A. my questions is : shouldn't we also need to prove that D we constructed works as a real distinguisher for the specific G?

  • $\begingroup$ "and then we prove that the probability that D returns 1 is negligible using out assumption about A" Ehm no. In fact, the step is: We show that if there is a non-negligible advantage for $A$, then there is a non-negligible advantage for $D$ - and that is a contradiction to $G$ being a PRF. The whole argument here is a logical contraposition on "$G$ is a PRF $\rightarrow G'$ is a PRF ". $\endgroup$ – tylo Nov 7 '16 at 10:48
  • $\begingroup$ yes , but also i think we need to show why D is indeed distinguishing G , by viewing it works on a random string and on a pseudorandom string. $\endgroup$ – odu9 Nov 7 '16 at 10:51
  • 1
    $\begingroup$ A distinguisher does not distinguish single strings. A distinguisher can query the PRF on many inputs and then make that decision - and we don't know or care how, we just use the generalization that he can. $\endgroup$ – tylo Nov 7 '16 at 10:54
  • $\begingroup$ thanks , just to make sure about the distinguisher of the PRG , if the distinguisher got G(s) , it has access to G right? and it doesn't know s of course right? $\endgroup$ – odu9 Nov 8 '16 at 14:34
  • $\begingroup$ A distinguisher is a polynomial time algorithm, which can win the according crypotgraphic game (if no such algorithm exists, we call that indistinguishability). In order to distinguish a PRF $G$, he needs oracle access to it - meaning he can query $x$ and gets $G(x)$or randomness back (and it is always $G$ or always random), for as many inputs as he wants. But that's it, usually there is no statement about the number of queries (except that it is polynomial, because the distinguisher is also polynomial) or how he actually can distinguish based on those queries. $\endgroup$ – tylo Nov 8 '16 at 23:35

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.