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?

enter image description here

  • $\begingroup$ We don't multiply by epsilon because it is not necessary; the argument is fine as it is. $\endgroup$
    – fkraiem
    Nov 27, 2016 at 21:24
  • $\begingroup$ That much is clear... My question is why is it not necessary? $\endgroup$ Nov 28, 2016 at 7:40
  • $\begingroup$ Because the argument is correct without it. Or do you see a flaw? $\endgroup$
    – fkraiem
    Nov 28, 2016 at 7:45
  • $\begingroup$ 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. $\endgroup$ Nov 28, 2016 at 7:53
  • $\begingroup$ 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. $\endgroup$
    – fkraiem
    Nov 28, 2016 at 7:59

2 Answers 2


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}$.

I assume this choice is made for the sake of some other proof further down the line, or maybe just some convention.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.