Now that we've seen a few examples of historic ciphers, all of which are badly broken, we're going to switch gears and talk about ciphers that are much better designed. But before we do that, I want to, first of all, define more precisely what a cipher is. So first of all, a cipher is actually, remember a cipher is made up of two algorithms. There's an encryption algorithm and a decryption algorithm. But in fact, a cipher is defined over a triple. So the set of all possible keys, which I'm going to denote by script K, and sometimes I'll call this the key space, it's the set of all possible keys. There's this set of all possible messages and this set of all possible ciphertexts. Okay, so this triple in some sense defines the environment over which the cipher is defined. And then the cipher itself is a pair of efficient algorithms E and D. E is the encryption algorithm; D is the decryption algorithm. Of course, E takes keys and messages. And outputs ciphertexts. And the decryption algorithm takes keys and ciphertexts. Then outputs messages. And the only requirements is that these algorithms are consistent. They satisfy what's called the correctness property. So for every message in the message space. And every key. In the key space, it had better be the case that if I encrypt the message with the key K and then I decrypt using the same key K I had better get back the original message that I started with. So this equation here is what's called the consistency equation and every cipher has to satisfy it in order to be a cipher otherwise it's not possible to decrypt. One thing I wanted to point out is that I put the word efficient here in quotes. And the reason I do that is because efficient means different things to different people. If you're more inclined towards theory, efficient means runs in polynomial time. So algorithms E and D have to run in polynomial time in the size of their inputs. If you're more practically inclined, efficient means runs within a certain time period. So for example, algorithm E might be required to take under a minute to encrypt a gigabyte of data. Now either way, the word efficient kind of captures both notions and you can interpret it in your head whichever way you'd like. I'm just going to keep referring to it as efficient and put quotes in it as I said if you're theory inclined think of it as polynomial time, otherwise think of it as concrete time constraints. Another comment I want to make is in fact algorithm E. It's often a randomized algorithm. What that means is that as your encrypting messages, algorithm E is gonna generate random bits for itself, and it's going to use those random bits to actually encrypt the messages that are given to it. On the other hand the decrypting algorithm is always deterministic. In other words given the key and the ciphertext output is always the same. Doesn't depend on any randomness that's used by the algorithm. Okay, so now that we understand what a cipher is better, I want to kind of show you the first example of a secure cipher. It's called a one time pad It was designed by Vernam back at the beginning of the twentieth century. Before I actually explain what the cipher is, let's just state it in the terminology that we've just seen. So the message space for the Vernam cipher for the one-time pad is the same as the ciphertext space which is just the set of all ended binary strings. This, this just means all sequences of bits, of zero one characters. The key space is basically the same as the message space which is again simply the embed of all binary strings. So a key in the one time pad is simply a random big string, it's a random sequence of bits. That's as long as the message to be encrypted, as long as the message. Okay, now that we've specified kind of what's the cipher's defined over we can actually specify how the cipher works and it's actually really simple. So essentially the ciphertexts. Which is the result of encrypting a message with a particular key, is simply the XOR of the two. Simply K XOR M. [inaudible] see a quick example of this. Remember that XOR, this plus with a circle. XOR means addition modulo two. So if I take a particular message, say, 0110111. And it take a particular key, say 1011001. When I compute the encryption of the message using this key, all I do is I compute the XOR of these two strings. In other words, I do addition module or two bit by bit. So I get one, one, zero, one, one, one, zero. That's a ciphertext. And then how do I decrypt? I guess they could do kind of the same thing. So they decrypt a cipher text using a particular key. What I do is I XOR the key and the ciphertext again. And so all we have to verify is that it satisfies the consistency requirements. And I'm going to do this slowly once and then from now on I'm going to assume this is all, simple to you. So we're gonna make, we're gonna have to make sure that if I decrypt a cipher text, that was encrypted using a particular key, I had better get. Back the message M. So what happens here? Well, let's see. So if I look at the encryption of k and m, this is just k XOR m by definition. What's the decryption of k XOR m using k? That's just k XOR (k XOR m). And so since I said that XOR is addition modulo two, addition is associative, so this is the same as (k XOR k) XOR m, which is simply as you know k XOR k is a zero, and zero XOR anything is simply m. Okay, so this actually shows that the one-time pad is in fact a cipher, but it doesn't say anything about the security of the cipher. And we'll talk about security of the cipher in just a minute. First of all, let me quickly ask you a question, just to make sure we're all in sync. Suppose you are given a message m and the encryption of that message using the one time pad. So all you're given is the message and the cipher text. My question to you is, given this pair m and c, can you actually figure out the one-time pad key that was used in the creation of c from m? So I hope all of you realize that in fact, given the message in the cipher text it's very easy to recover what the key is. In particular the key is simply M XOR C. Then we'll see that if it's not immediately obvious to you we'll see why that's, the case, a little later in the talk, in the lecture. Okay alright so the 1-time pad is a really cool from a performance point of view all you're doing is you exo-ring the key in the message so it's a super, super fast. Cypher for encrypting and decrypting very long messages. Unfortunately it's very difficult to use in practice. The reason it's difficult to use is the keys are essentially as long as the message. So if Alice and Bob want to communicate securely, so you know Alice wants to send a message end to Bob, before she begins even sending the first bit of the message, she has to transmit a key to Bob that's as long as that message. Well, if she has a way to transmit a secure key to Bob that's as long as the message, she might as well use that same mechanism to also transmit the message itself. So the fact that the key is as long as the message is quite problematic and makes the one-time pad very difficult to use in practice. Although we'll see that the idea behind the one-time pad is actually quite useful and we'll see that a little bit later. But for now I want to focus a little bit on security. So the obvious questions are, you know, why is the one-time pad secure? Why is it a good cypher? Then to answer that question, the first thing we have to answer is, what is a secure cipher to begin with? What is a, what makes cipher secure? Okay, so the study, security of ciphers, we have to talk a little bit about information theory. And in fact the first person, to study security of ciphers rigorously. Is very famous, you know, the father of information theory, Claude Shannon, and he published a famous paper back in 1949 where he analyzes the security of the one-time pad. So the idea behind Shannon's definition of security is the following. Basically, if all you get to see is the cypher text, then you should learn absolutely nothing about the plain text. In other words, the cypher text should reveal no information about the plain text. And you see why it took someone who invented information theory to come up with this notion because you have to formulize, formally explain what does information about the plain text actually mean. Okay so that's what Shannon did and so lemme show you Shannon's definition, I'll, I'll write it out slowly first. So what Shannon said is you know suppose we have a cypher E D that's defined over triple K M and C just as before. So KM and C define the key space, the message space and the cypher text space. And when we say that the cypher text sorry we say that the cypher has perfect secrecy if the following condition holds. It so happens for every two messages M zero and M1 in the message space. For every two messages the only requirement I'm gonna put on these messages is they have the same length. Yeah so we're only, we'll see why this requirement is necessary in just a minute. And for every cyphertext, in the cyphertext space. Okay? So for every pair of method messages and for every cipher text, it had better be the case that, if I ask, what is the probability that, encrypting N zero with K, woops. Encrypting N zero with K gives C, okay? So how likely is it, if we pick a random key? How likely is it that when we encrypt N zero, we get C. That probability should be the same as when we encrypt N1. Okay, so the probability of encrypting n one and getting c is exactly the same as the probability of encrypting n zero and getting c. And just as I said where the key, the distribution, is over the distribution on the key. So, the key is uniform in the key space. So k is uniform in k. And I'm often going to write k arrow with a little r above it to denote the fact that k is a random variable that's uniformly sampled in the key space k. Okay, this is the main part of Shannon's definition. And let's think a little bit about what this definition actually says. So what does it mean that these two probabilities are the same? Well, what it says is that if I'm an attacker and I intercept a particular cypher text c, then in reality, the probability that the cypher text is the encryption of n zero is exactly the same as the probability that it's the incryption of n one. Because those probabilities are equal. So if I have, all I have the cypher text C that's all I have intercepted I have no idea whether the cypher text came from M zero or the cypher text came from M one because again the probability of getting C is equally likely whether M zero is being encrypted or M one is being encrypted. So here, we have the definition stated again. And I just wanna write these properties again more precisely. So let's write this again. So what [inaudible] definition means is that if I am given a particular cipher text, I can't tell where it came from. I can't tell if it's, if the message that was encrypted. Is either N zero or N one and in fact, this property is true for all messages. For all these N zero, for all N zero and N ones. So not only can I not tell if'c' came from N zero or N one, I can't tell if it came from N two or N three or N four or N five because all of them are equally likely to produce the cypher text'c'. So what this means really is that if you're encrypting messages with a one time pad then in fact the most powerful adversary, I don't really care how smart you are, the most powerful adversary. Can learn nothing about the plain text, learns nothing about the plain text. From the cypher text. So to say it in one more way, basically what this proves is that there's no, there's no cypher text-only attack on a cypher that has perfect secrecy. Now, cypher attacks actually aren't the only attacks possible. And in fact, other attacks may be possible, other attacks may be possible. Okay. Now that we understand what perfect secrecy, means, the question is, can we build ciphers that actually have perfect secrecy? And it turns out that we don't have to look very far, the one time pattern fact has perfect secrecy. So I want to prove to you this is Shannon's first results and I wanna prove this fact to you, it's very simple proof so let's go ahead and look at it and just do it. So we need to kind of interpret what does that mean, what is this probability that E K M Z is equal to C. So it's actually not that hard to see that for every message and every cyphertext the probability that the encryption of N under a key K the probability that, that's equal to C, the probability that our random choice of key by definition. All that is, is basically the number of keys. Kay, instruct Kay. Such that, well. If I encrypt. And with k I get c. So I literally count the number of keys and I divide by the total number of keys. Right? That's what it means, that if I choose a random key, that key maps m to c. Right. So it's basically the number of key that map n to c divided by the total number of keys. This is its probability. So now suppose that we had a cypher such that for all messages and all cypher texts, it so happens that if I look at this number, the number of k, k, and k, such that e, k, m is equal to c. In other words, I'm looking at the number of keys that map m to c. Suppose this number happens to be a constant. So say it happens to be two, three, or ten or fifteen. It just hap, happens to be an absolute constance. If that's the case, then by definition, for all n0 and n1 and for all c, this probability has to be the same because the denominator is the same, the numerator is the same, it's just as constant, and therefore the probability is always the same for all n and c. And so if this property is true, then the cypher has to have, the cypher has perfect secrecy. Okay, so lets see what can we say about this quantity for the one time pad. So the sec-, so, the question to you is, if I have a message in a cipher-text, how many one time pad keys are there [inaudible] map, this message ends, so the [inaudible] C? So, in other words, how many keys are there, such that M XOR K is equal to C? So I hope you've all answered one. And let's see why that's the case. For the one time pad, if we have that, the encryption of K of M under K is equal to C. But basically, well, by definition, that implies that K XOR M is equal to C. But that also simply says that K has to equal to M XOR C. Yes, I just X over both sides by M and I get that K must equal the M XOR C. Okay? So what that says is that, for the one time pad, in fact, the number of keys, in K, shows the EKM, is equal to C. That simply is one, and this holds for all messages in cipher text. And so, again, by what we said before, it just says that the one time pad has, perfect secrecy. Perfect secrecy and that completes the proof of this [inaudible] very, very simple. Very, very simple lemma. Now the funny thing is that even though this lemma is so simple to prove in fact it proves a pretty powerful statement again. This basically says for the one time [inaudible] there is no cypher text only attack. So, unlike the substitution cipher, or the vigenere cipher, or the roller machines, all those could be broken by ciphertext-only attack. We've just proved that for the one-time pad, that's simply impossible. Given the cyphertext, you simply learn nothing about the plaintext. However, as we can see, this is simply not the end of the story. I mean, are we done? I mean, basically, we're done with the course now, cuz we have a way. To encrypt, so that an attacker can't recover anything about our method. So maybe we're done with the course. But in fact, as we'll see, there are other attacks. And, in fact, the one time pad is actually not such a secure cipher. And in fact, there are other attacks that are possible, and we'll see that shortly. Okay? I emphasize again the fact that it has perfect secrecy does not mean that the one time pad is the secure cypher to use. Okay. But as we said the problem with the one time pad is that the secret key is really long. If you had a way of. Communicating the secret key over to the other side. You might as well use that exact same method to also communicate the message to the other side, in which case you wouldn't need a cypher to begin with. Okay? So the problem again is the one time pad had really long keys and so the obvious question is are there other cyphers that has perfect secrecy and possibly have much, much shorter keys? Well, so the bad news is the Shannon, after proving that the one-time pad has perfect secrecy, proved another theorem that says that in fact if a cypher has perfect secrecy, the number of keys in the cypher must be at least the number of messages that the cypher can handle. Okay, so in particular, what this means is if I have perfect secrecy. Then necessarily the number of keys, or rather the length of my key, must be greater than the length of the message. So, in fact, since the one time pad satisfies us with equality, the one time pad is an optimal, cipher that has perfect secrecy, okay? So basically, what this shows is that this is an interesting notion. The one time pad is an interesting cipher. But, in fact, in reality, it's actually quite hard to use. It's hard to use in practice, again, because of these long keys. And so this notion of perfect secrecy, even though it's quite interesting, basically says that it doesn't really tell us the practical cyphers are going to be secure. And we're gonna see, but, as we said, the idea behind the one time pad is quite good. And we're gonna see, in the next lecture, how to make that into a practical system.