And we'll say that capital F is a pseudorandom function.
If these two worlds, world 0 and world 1,
are indistinguishable from the point of the attacker.
That is, the attacker can't tell whether it's interacting with a black box
containing a, an F chosen uniformly from the set of all functions in Funcn.
Or if it's interacting with a box containing F sub k.
For a uniformly chosen key k.
One thing I want to stress is that in the first case in,
in world 0, that function f is being chosen from a huge space of possibilities.
Remember the size of func n was 2 to the n times 2 to the n.
W explanation to n.
Where then the bottom the number of possibilities for
f k is at most 2 to the n because k is an n-bit key.
And so there are, there are most 2 to the n choices for k.
So on the top we have a distribution over a doubly
exponential size set of functions.
And on the bottom we have the sub-distribution over an exponential size
set of functions.
Nevertheless capital F is pseudorandom if the attacker can't distinguish these two
possibilities apart.
[SOUND] Now we can try to connect our
notion of pseudorandom functions with the earlier notion of pseudorandom generators.
And if you think about it a pseudorandom function is actually much stronger than
a pseudorandom generator.
And it immediately implies,
in particular, a construction of a pseudorandom generator.
That is if we have pseudo random function f
then we can very easily define the following pseudo random generator.