let's go over one of the
proofs in the sample exam now
remember in this proof we had
a pseudorandom function family F and
using that we constructed a pseudorandom 
function family Z
Zk(x) was
computed as follows just
to remind you if x
is equal to the key K
then it returned 0 otherwise
it returned 
whatever Fk would have returns
so it returned Fk(x)
so this is how we define c
and the theorem we are trying to prove 
is that you if
F is a secure pseudorandom function
family then Z
defined as follows: will be a secure pseudorandom function family
let's remember our proof strategy
so whenever we are trying to prove
something
first start by writing down the thorem this is
step
number one. number two
is writing down the proof methodology
strategy essentially this is writing down the
contrapositive
so if there exists a probabilistic
polynomial-time adversary
A who has non negligible advantage
in distinguishing Zk from a random function so
essentially
A is breaking Z
then
we construct another
probabilistic polynomial-time adversary
B who has non-negligible advantage in
distinguishing
Fk from a random function so
essentially what we are saying is if
there exists a PPT A that
breaks the security of Z
then we are going to construct a PPT B
that breaks the security of F
so you eventually remember this would mean
if F is secure then Z must be secure
lets do this proof
now the third thing
we should do is to
define these interfaces so here is
A what's the game A is playing here remember
A is trying to break Z so this game
should be the game for Z when you think
about it the game for Z is a PRF
game so A is given the security
parameter
A can ask polynomially many
queries so it will give us some
X we need to give Y which is Zk of
so Y needs to be something of the form
Zk(x)
this is what it expects and
eventually
will tell us okay are we giving random or pseudorandom so
Y needs to be either Zk(x) or
it needs to be some
lets say Z'(x) for a random function Z
that's what A is expecting
now what's the game
B is playing here
B is trying to break F so
this is the game for F. For F again this is a PRF
distinguishing game B is giving security parameter
B can ask again polynomially many
queries to its challanger it will give X'
and it will get Y' such that
Y' is either Fk(x') for a randomly generated key K or
from the same
domain and F a domain and range
a function F' will be randomly
picked out of all possible such functions with
the same domain and range as Fk
and Y' will be computed as
F' of this x'
so either one of these will happen Y' will be given to be and
B needs to guess was this
function used for computing Y'
a random function or a pseudorandom function that's what is going to happen
so this is the third the forth
item is filling in
the code for B in this proof it turns
out to be extremely simple
B just passes this security parameter
to A
whatever query A makes as x
B will set x' the same as x
and then query its own challenger
remember for this challenger  we know
exactly how it will behave
this here. we know it will be either the blue way
or the green way
and it will return Y'
B will set this Y the same as Y'
and then give back to the adversary so for
every query of the adversary B will do
this and then
at the end its job is again simple if the adversary says random
B will say random, the adversary says pseudorandom
B will say pseudorandom. This is the code for B.
now we switch
to the fifth item showing that B
is PPT. let's say
A makes P(n) queries to B
for some polynomial function P
then indeed B also makes P(n)
queries to its own challenger so
for every query that A makes to B,
B also makes one query
to its own challanger. remember
B's running time is the sum of these
so the time for P(n) oracle queries
+ A's running time
+ the red parts that make up B's code.
now
each oracle query takes O(1) time that's
the
assumption so this is P(n) times
O(1) this is some polynomial
A's running time is some
Q(n) which we know is also polynomial
remember A is a PPT algorithm
and the red code here
it is just some equality so
for every query that A makes we do
x'= x and y=y'
so actually 2P(n).
+2. one for passing the
the security parameter, the other for
passing the output
so since adversary makes polynomially many queries
this all thing is also another polynomial
which means the whole sum here
the B's running time is a polynomial
of the security parameter
now we are done we show that B's running
time is
PPT. The sixth
thing we need to do is to show that
B is indistinguishable from a real
challenger
so A's interaction with B should be similar to
A's
interaction with a real challanger now realize the
following
for all queries A makes for all
Xs that are not equal to the key
B indeed computes Zk(x)
exactly as a real challanger would have computed.
the only difference between B and a real challenger
is if the adversary queries
x if the adversary queries x
remember
a real challanger would have returned
0 as output whereas
B returns Fk(x)
Fk(k) actually
as its output so here
the adversary may distinguish
but remember this only happens this
difference
only happens if the adversary
manages to send a query
X that is equal to the key K. now remember
this key k is a randomly picked value so
the probably that A without knowing this key k
queries for some x that is the same as this key is
indeed the number of queries A
makes
over the key space. The key space
let's say if the keys are N bits
the key space will be 2^n
this is some polynomial. Polynomial^exp
we know its negligible
so except with negligible probability A
cannot distinguish B
from a real challanger. So sixth part is also done.
now seventh part success
probabilty, probability remember. 
Realise that
the probability B distinguishes
Fk from
some random F' is indeed the same
as the probability that
A distinguishes Zk from some random Z'
so probabilty that
B distinguishes Fk from
F' is indeed here the same as
A, the probability that A distinguishes
Zk
from some random
Z'. Remember by definition this is some
non negligible Epsilon. This is the
assumption that such A
exists that breaks Z.
breaking Z means distinguishing
these
with some non-negligible advantage.
now that we showed that B distinguishes
with non-negligible
advantage if A does so, we are done so
as the 8th item we can conclude
our theorem. Remember
if F is a secure PRF family
then this Epsilon, B's distinguishing
advantage
must be some negligible function
remember
Epsilon is also A's distinguishing
advantage so A's distinguishing advantage
must also be negligible
overall we can conclude our proof by saying that
this means Z must also be a secure
PRF family. So if F is a secure PRF
family, Z must also be a secure
PRF family
