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.
