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

## 4 comments

## Obinna Omego

nice lecture

## Obinna Omego

Please can you explain the advantage of an adversary, insecurity and security of an encryption-system or stego-system. An article named "provably secure steganography" discuss this google scholar. I really need this urgently for my phd

## Junwei Wang

I think there is a mistake in this lecture. Pr[b' neq b | r is PR] Pr[r is PR] + Pr[b' neq b | r is R] Pr[r is R] = Pr[b neq b] = 1/2 – non-negl(n). Pr[r is R] = Pr[r is PR] = 1/2 (otherwise, B can just always make the same guess). Hence Pr[b' neq b | r is PR] = 1/2 – 2* non-negl(n). All in all, Pr[b->R | r is R] – Pr[b->R | r is PR] = 2*non-negl(n).

## gingerAV

bless your soul