So now that we understand what a secure PRG is, and we understand what semantic
security means, we can actually argue that a stream cipher with a secure PRG is, in
fact, a semantically secure. So that's our goal for this, segment. It's a fairly
straightforward proof, and we'll see how it goes. So the theory we wanna prove is
that, basically, given a generator G that happens to be a secured, psedo-random
generator. In fact, the stream cipher that's derived from this generator is
going to be semantically secure. Okay and I want to emphasize. That there was no
hope of proving a theorem like this for perfect secrecy. For Shannons concept of
perfect secrecy. Because we know that a stream cipher can not be perfectly
secure because it has short keys. And perfect secrecy requires the keys to be as
long as the message. So this is really kind of the first example the we see where
we're able to prove that a cipher with short keys has security. The concept of
security is semantic security. And this actually validates that, really, this is a
very useful concept. And in fact, you know, we'll be using semantic security
many, many times throughout the course. Okay, so how do we prove a theory like
this? What we're actually gonna be doing, is we're gonna be proving the
contrapositive. What we're gonna show is the following. So we're gonna prove this
statement down here, but let me parse it for you. Suppose. You give me a semantic
security adversary A. What we'll do is we'll build PRG adversary B to satisfy
this inequality here. Now why is this inequality useful? Basically what do we
know? We know that if B is an efficient adversary. Then we know that since G is a
secure generator, we know that this advantage is negligible, right? A secure
generator has a negligible advantage against any efficient statistical test. So
the right hand side, basically, is gonna be negligible. But because the right hand
side is negligible, we can deduce that the left hand side is negligible.
And therefore, the adversary that you looked at actually has negligible advantage in
attacking the stream cipher E. Okay. So this is how this, this will work.
Basically all we have to do is given an adversary A we're going to build an
adversary B. We know that B has negligible advantage against generator but that
implies that A has negligible advantage against the stream cipher.
So let's do that. So all we have to do again is given A, we have to build B.
So let A be a semantic security adversary against the stream cipher. So let me remind you
what that means. Basically, there's a challenger. The challenger starts off by
choosing the key K. And then the adversary is gonna output two messages, two equal
length messages. And he's gonna receive the encryption of M0 or M1
and outputs B1. Okay, that's what a semantic security adversary is
going to do. So now we're going to start playing games with this adversary. And
that's how we're going to prove our lemma. Alright, so the first thing
we're going to do is we're going to make the challenger. Also choose a random R.
Okay, a random string R. So, well you know the adversary doesn't really care what the
challenger does internally. The challenger never uses R, so this doesn't affect the
adversary's advantage at all. The adversary just doesn't care that the
challenger also picks R. But now comes the trick. What we're going to do is we're
going to, instead of encrypting using GK. We're going to encrypt using R. You can
see basically what we're doing here. Essentially we're changing the
challenger so now the challenge cipher text is encrypted using a
truly random pad. As opposed to just pseudo random pad GK. Okay. Now, the property of
the pseudo-random generator is that its output is indistinguishable from truly
random. So, because the PRG is secure, the adversary can't tell that we made this
change. The adversary can't tell that we switched from a pseudo-random string to a
truly random string. Again, because the generator is secure. Well, but now look at
the game that we ended up with. So the adversary's advantage couldn't have
changed by much, because he can't tell the difference. But now look at the game that
we ended up with. Now this game is truly a one time pad game. This a semantic
security game against the one time pad. Because now the adversary is getting a one
time pad encryption of M0 or M1 But in the one time pad we know that the adversaries
advantage is zero, because you can't beat the one time pad. The one time pad is
secure Unconditionally secure. And as a result, because of this. Essentially
because the adversary couldn't have told the difference when
we moved from pseudo random to random. But he couldn't win the random game. That also means that he
couldn't win the sudo random game. And as a result, the stream cipher, the original
stream cipher must be secure. So that's the intuition for how the proof is gonna go.
But I wanna do it rigorously once. From now on, we're just gonna argue by
playing games with our challenger. And, we won't be doing things as formal as I'm
gonna do next. But I wanna do formally and precisely once, just so that you see how
these proofs actually work. Okay, so I'm gonna have to introduce some notation. And
I'll do the usual notation, basically. If the original semantics are here at the
beginning, when we're actually using a pseudo-random pad, I'm gonna use W0 and W1
to denote the event that the adversary outputs one, when it gets the encryption
of M0, or gets the encryption of M1, respectively. Okay? So W0 corresponds to
outputting 1 when receiving the encryption of M0. And W1 corresponds
to outputting 1 when receiving the encryption of M1. So that's the standard
definition of semantic security. Now once we flip to the random pad. I'm gonna use
R0 and R1 to denote the event that the adversary outputs 1 when receiving the
one-type pad encryption of M0 or the one-time pad encryption of M1. So we have
four events, W0, W1 from the original semmantics security game, and R0 and R1
from the semmantics security game once we switch over to the one-time pad. So now
let's look at relations between these variables. So first of all, R0 and R1 are
basically events from a semmantics security game against a one-time pad. So
the difference between these probabilities is that, as we said, basically the
advantage of algorithm A, of adversary A, against the one-time pad. Which we know is
zero. Okay, so that's great. So that basically means that probability of, of R0
is equal to the probability of R1. So now, let's put these events on a line, on a
line segment between zero and one. So here are the events. W0 and W1 are the events
we're interested in. We wanna show that these two are close. Okay. And the way
we're going to do it is basically by showing, oh and I should say, here is
probability R0 and R1, it says they're both same, I just put them in the
same place. What we're gonna do is we're gonna show that both W0 and W1 are
actually close to the probability of RB and as a result they must be close to one
another. Okay, so the way we do that is using a second claim, so now we're
interested in the distance between probability of Wb and the probability of
Rb. Okay so we'll prove the claim in a second. Let me just state the claim. The
claim says that there exists in adversary B. Such that the difference of these two
probabilities is basically the advantage of B against the generator G and this is
for both b's. Okay? So given these two claims, like the theorem is done because
basically what do we know. We know this distance is less than the advantage of B
against G. That's from claim two and similarly, this distance actually is even
equal to, I'm not gonna say less but is equal to the advantage. Of B
against G, and as a result you can see that the distance between W0 and W1
is basically almost twice the advantage of B against G. That's basically
the thing that we are trying to prove. Okay the only thing that remains is just
proving this claim two and if you think about what claim two says, it basically
captures the question of what happens in experiment zero what happens when we
replace the pseudo random pad GK, by truly random pad R. Here in
experiment zero say we're using the pseudo random pad and here in experiment zero we
are using a Truly random pad and we are asking can the adversary tell the
difference between these two and we wanna argue that he cannot because the generator
is secure. Okay so here's what we are gonna do. So let's prove claim two. So we
are gonna argue that in fact there is a PRG adversary B that has exactly the
difference of the two probabilities as it's advantage. Okay and since the point
is since this is negligible this is negligible. And that's basically what we
wanted to prove. Okay, so let's look at the statistical test b. So, what, our
statistical test b is gonna use adversary A in his belly, so we get to build
statistical test b however we want. As we said, it's gonna use adversary A inside of
it, for its operation, and it's a regular statistical test, so it takes an n-bit
string as inputs, and it's supposed to output, you know, random or non-random,
zero or one. Okay, so let's see. So it's, first thing it's gonna do, is it's gonna
run adversary A, and adversary A is gonna output two messages, M0 and M1. And then,
what adversary b's gonna do, is basically gonna respond. With M0 XOR or the string that
it was given as inputs. Alright? That's the statistical lesson, then. Whenever A
outputs, it's gonna output, its output. And now let's look at its advantage. So
what can we say about the advantage of this statistical test against the
generator? Well, so by definition, it's the probability that, if you choose a
truly random string. So here are 01 to the N, so probability
that R, that B outputs 1 minus the probability, is that when we choose a
pseudo random string, B outputs 1, okay? Okay, but let's think about what this is.
What can you tell me about the first expressions? What can you tell me about
this expression over here? Well, by the definition that's exactly if you think
about what's going on here, that's this is exactly the probability R0 right?
Because this game that we are playing with the adversary here is basically he helped
us M0 and M1 right here he helped add M0 and m1 and he got the encryption
of M0 under truly one time pad. Okay, so this is basically a [inaudible]. Here
let me write this a little better. That's the basic level probability of R0.
Now, what can we say about the next expression, well what can we say about
when B is given a pseudo random string Y as input.
Well in that case, this is exactly experiment zero and true stream cipher game
because now we're computing M XOR M0, XOR GK. This is exactly W0.
Okay, that's exactly what we have to prove. So it's kind of a trivial proof.
Okay, so that completes the proof of claim two. And again, just to make sure this is all clear, once we have
claim two, we know that W0 must be close to W1, and that's the theorem.
That's what we have to prove. Okay, so now we've established that a stream cypher is in
fact symmantically secure, assuming that the PRG is secure.
