And so the probability with which t the value output by the attacker being
run as a sub routine within D, happens to be equal to the value t*.
That is the value that D gets back from its oracle, is exactly 2 to the minus n.
So here, we're assuming that we have a length preserving pseudorandom function,
f, whose input and output length are both end bit strings.
Whose input and output range and domain are both end bit strings.
So the probability that we can predict in advance, the value,
of the n-bit string t* is exactly 2 to the -n.
We're almost done.
By assumption that F is a pseudorandom function,
we know that the difference between the probability with which D outputs 1 when
interacting with Fk and the probability that D outputs 1 when interacting with
a random function must be negligible.
And so, plugging in what we have from the previous slide,
we see that the probability that the attacker succeeds
in the forage experiment, which is equal to the probability with which D outputs 1
when interacting with F sub k, is at most 2 to the minus n plus negligible.
And because 2 to the minus n is itself a negligible function.
That means that indeed we've shown that the probability that the attacker can
succeed in the original forgery experiment is negligible.
