# Question about proof of pseudo-random random generators being one way functions

I've been looking over this proposition and proof in the book "Introduction to modern cryptography" and am a little confused. Picture is attached at the bottom).

Why is it that we do not multiply the $2^{-n}$ by $\varepsilon$.

It is true that the probability of being in the generator range is $2^{-n}$ but even once we're there the chances of A giving the correct inverse are not $1$.

Should the equation not be $\leq \varepsilon ~ 2^{-n}$ instead?

• We don't multiply by epsilon because it is not necessary; the argument is fine as it is. Nov 27, 2016 at 21:24
• That much is clear... My question is why is it not necessary? Nov 28, 2016 at 7:40
• Because the argument is correct without it. Or do you see a flaw? Nov 28, 2016 at 7:45
• Yes I do. Like I said, they claim that we take that value because that's the probability of w being in the range. But even if it is in the range we still run w through A and depending on what it replies we make our choice. And A guesses correctly with probability epsilon. Nov 28, 2016 at 7:53
• No, that's not how it works. A flaw in a mathematical argument is a statement that is false, or at least sufficiently lacking in justification that a competent reader would find its truth dubious. Do you see such a statement in the text? If so, quote it exactly. You have several highlighted parts in your question. Nov 28, 2016 at 7:59

It's analyzed in this way because it is tricky to correctly conclude much more than what's written here. The issue is that a uniformly random string $w$ in the image of $G$ is not necessarily distributed like $G(x)$ for a uniformly random $x$. We know that $\mathcal{A}(y)$ succeeds with $\varepsilon$ probability for a random input $y=G(x)$ of the latter form, but that doesn't tell us much about how it behaves in the former case.
More precisely, conditioned on $w$ being in the image of $G$, it is uniformly random in that image. This does not necessarily imply that $\mathcal{A}(w)$ ouputs an element of the preimage set $G^{-1}(w) = \{x : G(x)=w\}$ with probability $\varepsilon$. For example, $G$ could be highly "irregular," meaning that some preimage sets are much larger than others. But $\mathcal{A}$ might only successfully invert on, say, those $y$ that have very large preimage sets. This would give it good inverting probability on $y=G(x)$ for uniformly random $x$, but its probability of inverting on a uniform $w$ in the image of $G$ would be much less than $\varepsilon$.
It seems to me that the case here is simply that they chose to not give a very tight bound. What they say is that at most the probability is ${2^{-n}}$. That is that even for a perfect A, one that is right all the time, the probability cannot go above that value. that's why the do not multiply by ${\epsilon}$.