Remember the theorem we are trying to prove so theorem was that if G is a secure pseudorandom generator PRG then our scheme X that we defined previously was a secure encryption scheme under the single message eavesdropper
game that we have defined so when you think about our proof strategy remember we do the proof using contrapositive so if there exists some PPT adversary A who breaks the scheme X so remember breaking scheme X would mean
winning this game with 1/2+non-neg(n) probabilty then we are going to construct Remember this is a constructive proof then
we are going to construct another PPT adversary B now what is that B going to break B is going to break G now what does breaking G mean it will distinguish between random and pseudorandom so the output of G versus some randomly picked value of the same length with non-negligible advantage so the difference between the probabilities will be non-negligible as usual we are going to draw our boxes remember the outside box will be B and B’s going to play the PRG game what was the PRG game remember B is given the security
parameter and some value R such that either R is picked randomly from n’ prime bits length values or so this is one option or a random seed was picked for our PRG and then this R was computed as G(s) so this corresponds to the random case this corresponds to the pseudorandom case so R is either random or pseudorandom which
means eventually we need to guess that we need to say random or that’s a
pseudorandom now inside there is this adversary A that we can make use of A is going to play encryption game the eavesdropper so what’s the interaction here A needs to
be given the security parameter and then A will give us m0 and m1 then we are going to return some value c that should be encryption of one these two A and finally he’s going to output his guess some B’ remember B needs to behave similar to the challenger of
the encryption game here and it needs to behave as a adversary in the PRG game here so now our job is to fill in the code for the security parameter we will just
pass on the same values so this green security parameter
will be the same as the blue one there’s nothing interesting here for this encryption what B will do is B it will pick a bit b and then it is going to encrypt mb but it does not it needs to tie it to this random or pseudorandom somehow so it will compute c as r xored with Mb and then send it now it recieves back some b’ prime from the adversary we have two options if this b’ prime is indeed equal to b so the adversary
guessed correctly then we will return as output we will say pseudorandom else B will return random intuitively the reason here is that if r is pseudorandomly generated value this way then what we did here is exactly what A is expecting we give him an encrypted message and then by our assumption that A
the breaks X he should have 1/2+non-neg(n) probability on the other hand if r was random this is exactly one-time-pad
which we know it is perfectly secure remember there are three things we need
to analyse 1)we need to show that B we constructed is PPT. this is the
code for B indeed you can even argue this is taken constant time, done. so we proved that B takes PPT. the other thing we need to have argue is our simulation remember here A is expecting the security parameter we are giving him one. here A is expecting one of the
messages xor’ed with some value which is what we are giving so our simulation of the challengers is done we are indistinguishable from a real
challenger of the encryption game as far A is concerned the third part remember is the
probability argument we need to argue probability we need to argue that if A manages to guess this bit with non-neg(n) advantage meaning A guesses this bit so b’ is indeed equal to b with probability 1/2 + … non-negligible lets say some negligible function if this is the case we need to argue that our distinguishing probabilities so B outputting random so B outputting random given that R was indeed random so this probability and this probability B again outputs random but now it is given a pseudorandom value you won’t remember that this probability
to be equal to this plus minus some negligible in the usual case breaking would mean some non-negligible here. so if this is the case this should be the
case this is what we want to show now when you think about it. when would B output random. so take this probability B outputs random if this bit here b’ is not equal to b so this whole thing is the same as saying that b’ is not equal to b given that r is a random value so this is the same as this probability here now when r is a random value remember what we are doing is exactly a
one-time-pad therefore by the perfect security of one-time-pad b’ being equal to b has probably 1/2 b’ not being equal to b again we’ll have probability 1/2 so 1 – 1/2 will give us 1/2 what about this one this is analogous here that probability will be the probability that b’ is not equal to b now given that r is a pseudorandom value now when r is pseudorandom what we do here is exactly simulating the challenger for the adversary when we
give it the encryption construction X we know that the adversary wins with 1/2+ some non-neg probability. now this is the probability that the
adversary loses if it wins with 1/2 + non negligible it will lose with one minus this and one minus this will be 1/2 – non negligible so when r is a pseudorandom the adversary loses with 1/2 – non negligible probabilty and whenever the adversary loses B says r was random now we need to look at the difference between these probabilities and the difference needs to be non negligible so
here we have 1/2 and then here we have 1/2 – non negligible and when we subtract these what we realize is that this difference is non-negligible there is a very similar way of arguing about this so instead of directly saying non-neg here some sources says this is let’s say 1/2 + some Epsilon if that’s the case 1 – 1/2 + epsilon will be 1/2-epsilon(n) and then the difference here remember this is now epsilon(n) will be equal to epsilon(n) so if epsilon is non-negligible if the adversary has
non-negligible advantage in guessing this bit then our adversary B will have non-negligible distinguishing probability going backwards since we are assuming G is a secure pseudorandom generator this value must be
negligible so Epsilon must be negligible which means the adversary’s probability of guessing
correctly would be 1/2 + negligible so if G is a secure pseduorandom generator then X must be a secure encryption scheme