Stream ciphers are semantically secure (11 min)

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.