My goal for the next few segments is to show you that if we use a secure PRG We'll get a secure stream safer. The first thing we have to do is define is, what does it mean for a stream safer to be secure? So whenever we define security we always define it in terms of what can the attacker do? And what is the attacker trying to do? In the context of stream ciphers remember these are only used with a onetime key, and as a result the most the attacker is ever going to see is just one cypher text encrypted using the key that we're using. And so we're gonna limit the attackers? ability to basically obtain just one cypher text. And in fact later on we're going to allow the attacker to do much, much, much more, but for now we're just gonna give him one cypher text. And we wanted to find, what does it mean for the cypher to be secure? So the first definition that comes to mind is basically to say, well maybe we wanna require that the attacker can't actually recover the secret key. Okay so given ciphertext you shouldn't be able to recover the secret key. But that's a terrible definition because think about the falling brilliant cipher but the way we encrypt the message using a key K is basically we just output the message. Okay this is a brilliant cipher yeah of course it doesn't do anything given a message just output a message as the cipher text. This is not a particularly good encryption scheme; however, given the cipher text, mainly the message the poor attacker cannot recover the key because he doesn't know what the key is. And so as a result this cipher which clearly is insecure, would be considered secure under this requirement for security. So this definition will be no good. Okay so it's recovering the secret key is the wrong way to define security. So the next thing we can kinda attempt is basically just say, well maybe the attacker doesn't care about the secret key, what he really cares about are the plain text. So maybe it should be hard for the attacker to recover the entire plain text. But even that doesn't work because let's think about the following encryption scheme. So suppose what this encryption scheme does is it takes two messages, so I'm gonna use two lines to denote concatenation of two messages M0 line, line M1 means concatenate M0 and M1. And imagine what the scheme does is really it outputs M0 in the clear and concatenate to that the encryption of M1. Perhaps even using the One Time Pad okay? And so here the attacker is gonna be given one cipher text. And his goal would be to recover the entire plain texts. But the poor attacker can't do that because here maybe we've encrypted M1 using the One Time Pad so the attacker can't actually recover M1 because we know the One Time Pad is secure given just one cipher text. So this construction would satisfy the definition but unfortunately clearly this is not a secure encryption scheme because we just leaked half of the plain text. M0 is completely available to the attacker so even though he can't recover all of the plain text he might be able to recover most of the plain text, and that's clearly unsecured. So of course we already know the solution to this and we talked about Shanon definition of security perfect secrecy where Shannon's idea was that in fact when the attacker intercepts a cipher text he should learn absolutely no information about the plain texts. He shouldn't even learn one bit about the plain text or even he shouldn't learn, he shouldn't even be able to predict a little bit about a bid of the plain text. Absolutely no information about the plain text. So let's recall very briefly Shannon's concept of perfect secrecy basically we said that you know given a cipher We said the cipher has perfect secrecy if given two messages of the same length it so happens that the distribution of cipher texts. Yet if we pick a random key and we look into distribution of cipher texts we encrypt M0 we get exactly the same distribution as when we encrypt M1. The intuition here was that if the advisory observes the cipher texts then he doesn't know whether it came from the distribution the result of encrypting M0 or it came from the distribution as the result of encrypting M1. And as a result he can't tell whether we encrypted M0 or M1. And that's true for all messages of the same length and as a result a poor attacker doesn't really know what message was encrypted. Of course we already said that this definition is too strong in the sense that it requires really long keys if cipher has short keys can't possibly satisfy this definition in a particular stream ciphers can satisfy this definition. Okay so let's try to weaken the definition a little bit and let's think to the previous segment, and we can say that instead of requiring the two distributions to be absolutely identical what we can require is, is that two distributions just be computationally indistinguishable. In other words a poor, efficient attacker cannot distinguish the two distributions even though the distributions might be very, very, very different. That just given a sample for one distribution and a sample for another distribution the attacker can't tell which distribution he was given a sample from. It turns out this definition is actually almost right, but it's still a little too strong, that still cannot be satisfied, so we have to add one more constraint, and that is that instead of saying that this definition should have hold for all M0 and M1. It is to hold for only pairs M0 M1 that the attackers could actually exhibit. Okay so this actually leads us to the definition of semantics security. And so, again this is semantics security for one time key in other words when the attacker is only given one cipher text. And so the way we define semantic security is by defining two experiments, okay we'll define experiment 0 and experiment 1. And more generally we will think of these as experiments parentheses B, where B can be zero or one. Okay so the way the experiment is defined is as follows, we have an adversary that's trying to break the system. An adversary A, that's kinda the analog of statistical tests in the world of pseudo random generators. And then the challenger does the following, so really we have two challengers, but the challengers are so similar that we can just describe them as a single challenger that in one case takes his inputs bits set to zero, and the other case takes his inputs bits set to one. And let me show you what these challengers do. The first thing the challenger is gonna do is it's gonna pick a random key and then the adversary basically is going to output two messages M0 and M1. Okay so this is an explicit pair of messages that the attacker wants to be challenged on and as usual we're not trying to hide the length of the messages, we require that the messages be equal length. And then the challenger basically will output either the encryption of M0 or the encryption of M1, okay so in experiment 0 the challenger will output the encryption of M0. In experiment 1 the challenger will output the encryption of M1. Okay so that the difference between the two experiments. And then the adversary is trying to guess basically whether he was given the encryption of M0 or given the encryption of M1. Okay so here's a little bit of notation let's define the events Wb to be the events that an experiment B the adversary output one. Okay so that is just an event that basically in experiment zero W0 means that the adversary output one and in experiment one W1 means the adversary output one. And now we can define the advantage of this adversary, basically to say that this is called the semantics security advantage of the adversary A against the scheme E, to be the difference of the probability of these two events. In other words we are looking at whether the adversary behaves differently when he was given the encryption of M0 from when he was given the encryption of M1. And I wanna make sure this is clear so I'm gonna say it one more time. So in experiment zero he was given the encryption of M0 and in experiment one he was given the encryption of M1. Now we're just interested in whether the adversary output 1 or not. ... In these experiments. If in both experiments the adversary output 1 with the same probability that means the adversary wasn't able to distinguish the two experiments. Experiments zero basically looks to the adversary the same as experiment one because in both cases upload one with the same probability. However if the adversary is able to output 1 in one experiment with significantly different probability than in the other experiment, then the adversary was actually able to distinguish the two experiments. Okay so... To say this more formally, essentially the advantage again because it's the difference of two probabilities the advantage is a number between zero and one. If the advantage is close to zero that means that the adversary was not able to distinguish experiment zero from experiment one. However if the advantage is close to one, that means the adversary was very well able to distinguish experiment zero from experiment one and that really means that he was able to distinguish an encryption of M0 from an encryption of M1, okay?So that's out definition. Actually that is just the definition of the advantage and the definition is just what you would expect basically we'll say that a symmetric encryption scheme is semantically secure if for all efficient adversaries here I'll put these in quotes again, "For all efficient adversaries the advantage is negligible." In other words, no efficient adversary can distinguish the encryption of M0 from the encryption of M1 and basically this is what it says repeatedly that for these two messages that the adversary was able to exhibit he wasn't able to distinguish these two distributions. Now I want to show you this, this is actually a very elegant definition. It might not seem so right away, but I want to show you some implications of this definition and you'll see exactly why the definition is the way it is. Okay so let's look at some examples. So the first example is suppose we have a broken encryption scheme, in other words suppose we have an adversary A that somehow given the cipher text he is always able to deduce the least significant bit of the plain text. Okay so given the encryption of M0, this adversary is able to deduce the least significant bit of M0. So that is a terrible encryption scheme because it basically leaks the least significant bit of the plain text just given the cipher text. So I want to show you that this scheme is therefore semantically secure so that kind of shows that if a system is semantically secure than there is no attacker of this type. Okay so let's see why is the system not semantically secure well so what we are gonna do is we're gonna basically use our adversary who is able to learn our most insignificant bits, we're going to use him to break semantic security so we're going to use him to distinguish experiment zero from experiment one Okay so here is what we are going to do. We are algorithm B, we are going to be algorithm B and this algorithm B is going to use algorithm A in its belly. Okay so the first thing that is going to happen is of course the challenger is going to choose a random key. The first thing that is going to happen is that we need to output two messages. The messages that we are going to output basically are going to have differently significant bits. So one message is going to end with zero and one message is going to end with one. Now what is the challenger going to do? The challenger is going to give us the encryption of either M0 or M1, depending on whether in experiment 0 or in experiment 1. And then we just forward this cipher text to the adversary okay so the adversary A. Now what is the property of adversary A? Given the cipher text, adversary A can tell us what the least significant bits of the plain text is. In other words the adversary is going to output the least significant bits of M0 or M1 but low and behold that's basically the bit B. And then we're just going to output that as our guest so let?s call this thing B prime Okay so now this describes the semantic security adversary. And now you tell me what is the semantic security advantage of this adversary? Well so let's see. In experiment zero, what is the probability that adversary B outputs one? Well in experiment zero it is always given the encryption of M zero and therefore adversary A is always output the least significant bit of M zero which always happens to be zero. In experiment zero, B always outputs zero. So the probability that outputs one is zero. However in experiment one, we're given the encryption of M1. So how likely is adversary B to output one in experiment one well it always outputs one, again by the properties of algorithm A and therefore the advantage basically is one. So this is a huge advantage, it's as big as it's gonna get. Which means that this adversary completely broke the system. Okay so we consider, so under semantic security basically just deducing the least significant bits is enough to completely break the system under a semantic security definition. Okay, now the interesting thing here of course is that this is not just about the least significant bit, in fact of the message for example the most significant bit, you know bit number seven Maybe the XOR of all the bits in the message and so on and so forth any kind of information, any bit about the plain text they can be learned basically would mean that the system is not semantically secure. So basically all the adversary would have to do would be to come up with two messages M0 and M1 such that under one thing that they learned it's the value zero and then the other thing, the value, is one. So for example if A was able to learn the XOR bits of the message then M0 and M1 would just have different XOR for all the bits of their messages and then this adversary A would also be sufficient to break semantic security. Okay so, basically for cipher is semantically secure then no bit of information is revealed to an efficient adversary. Okay so this is exactly a concept of perfect secrecy only applied just efficient adversaries rather than all adversaries. So the next thing I wanna show you is that in fact the one time pad in fact is semantically secure, they better be semantically secure because it's in fact, it's more than that it's perfectly secure. So let's see why that's true. Well so again it's one of these experiments, so suppose we have an adversary that claims to break semantic security of the one time pad. The first the adversary is gonna do is he's gonna output two messages M0 and M1 of the same length. Now what does he get back as a challenge? As a challenge, he gets either the encryption of M0 or the encryption of M1 under the one time pad. And he's trying to distinguish between those two possible cipher texts that he gets, right? In experiment zero, he gets the encryption of M0 and in experiment one, he gets the encryption of M1. Well so let me ask you, so what is the advantage of adversary A against the one time patent? So I remember that the property of the ones I had is that, that K, XOR M0 is distributed identically to K, XOR M1. In other words, these distributions are absolutely identical distribution, distributions, identical. This is a property of XOR. If we XOR the random pad K with anything, either M0 or M1, we get uniform distribution. So in both cases, algorithm A is given as in input exactly the same distribution. Maybe the uniform distribution on cipher texts. And therefore it's gonna behave exactly the same in both cases because it was given the exact distribution as input. And as a result, its advantage is zero, which means that the onetime pad is semantically secure. Now the interesting thing here is not only is it semantically secure, it's semantically secure for all adversaries. We don't even have to restrict the adversaries to be efficient. No adversary, doesn't matter how smart you are, no adversary will be able to distinguish K XOR M0 from K XOR M1 because the two distributions are identical. Okay, so the one time pad is semantically secure. Okay, so that completes our definition of semantic security so the next thing we're going to do is prove to the secure PRG, in fact implies that the stream cipher is semantically secure.
