-
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.