Let $ PRG: \{ 0, 1\}^n \rightarrow \{ 0, 1\}^{n+s}$ be a pseudo random generator and let $A$ be an inverter that runs in polynomial time, specifically:

$\large \mathbb P_{d \leftarrow PRG(U_n)}[ A(d) = v, PRG(v) = d] \ \ge \ \delta$

Show how to construct a polynomial distinguisher $B$ that uses $A$ to distinguish $PRG(U_n)$ from $U_{n+s}$ with probability at least $\ \delta (1-2^{-s})$, namely that the following inequality holds:

$ \large | \ \mathbb P_{d \leftarrow PRG(U_n)}[ B(d) = 1] \ -\ \mathbb P_{d \leftarrow U_{n+s}}[B(d) = 1] \ | \ \ge \ \delta(1-2^{-s}) $

Note: $U_n$ denotes the uniform distribution on $\{ 0, 1\}^n$

The only thing I could think of is the following distinguisher $B$:
Given a string $\ d \in \{0,1\}^{n+s}$, $B(d) = 1$ if and only if $PRG(A(d)) = d$.

Now we mark $\ T = Img(PRG)$. According to the formula of total probability (in all the probabilities below $d \leftarrow U_{n+s}$ ):
$\mathbb P(B(d) = 1) \ = $
$\mathbb P(B(d) = 1|d \notin T) \ \mathbb P(d \notin T) + \mathbb P(B(d) = 1 | d \in T) \ \mathbb P(d \in T) \ =$
$\mathbb P(B(d) = 1 | d \in T) \ \mathbb P(d \in T)$

( the last equation is true because $\mathbb P(B(d) = 1|d \notin T) = 0 \ $)

This is where I got stuck. I think I could have solved it if I knew that the $PRG$ is a one to one function, but I don't...
I'm not even sure if my construction is right. Is there a better way to construct $B$ ? Or maybe there is something else that I'm missing ?

  • $\begingroup$ You are on the right track and you have the correct B. Your mistake is that you are just computing the probability of B answering 1 when the string has been chosen from the uniform distribution on n+s bits (which will only be smaller if PRG is not injective). You are supposed to compare this to the probability that B answers 1 on a string that was generated by PRG. $\endgroup$ – K.G. Nov 6 '13 at 8:14
  • $\begingroup$ @K.G. I'm sorry if that wasn't clear, but that's what I meant when I said I'm stuck (I thought it was obvious, I wasn't really trying to calculate the actual probability but simplify it so that it could easily be compared to the probability that you just mentioned). Do you know how is it possible to compare these probabilities ? I would appreciate any help... $\endgroup$ – Robert777 Nov 6 '13 at 17:41
  • $\begingroup$ Compute the difference. $\endgroup$ – K.G. Nov 7 '13 at 8:52

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.