0:10

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.

Â 13:24

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.

Â