In the last few lectures we've explored the one-time pad encryption scheme. And shown that it achieves our definition of perfect secrecy. And indeed, the one-time pad has been used in the real world. A famous example is the red phone that connected Washington DC and Moscow in the 1980s, where the keying material was shared by trusted couriers, who would take suitcases full of printouts of bits, as it were and carry them between the two parties. Nevertheless the one-time pad encryption scheme is not used very often nowadays. Why is that? Well in fact there are several limitations that prevent more widespread use of the one time pad. One of these which you may have noticed as we've described the scheme. Is that the key is as long as the message. Remember that in the description of the one-time pad encryption scheme. We had a parameter n that determined both the length of the messages that could be encrypted. As well as the length of the key. Moreover the one-time pad encryption scheme is only secure if each key is used to encrypt a single message. Certainly the proof of perfect secrecy that we gave for the one-time pad relied on the assumption that the key was being used to encrypt only a single message, and we'll see in a few moments that in fact there are some simple attacks on the scheme in case a key is used to encrypt more than one message. What this means is that if you want to use the one-time pad encryption scheme to secure your communication, then parties need to share keys whose total length is equal to the total length of all messages they might ever want to send. That's because each portion of the shared key can be used only once, and must be used to encrypt a message whose length is equal to the length of that portion of the key. It's even worse if the parties don't know in advance how much they're going to want to communicate. In that case they would need to share a total key. Or a key rather, whose total length is at least an upper bound on the total length of all messages they want to send. I want to look in more detail at the problems that might arise in case the one-time pad encryption scheme is used to encrypt two messages using the same key. So let's say we have two parties who share a key k. And use this key to encrypt two messages, m1 and m2. An attacker who observes the two ciphertexts, phi 1 and phi 2, can compute the XOR of those two ciphertexts, and we see by performing the substitution, that that XOR is equal to the XOR of m1 and m2. Right c1 is equal to kx or m1. C2 is equal to KX or M2. And if we if the attacker XOR is C1 and C2 together the key K cancels from the resulting expression and the attacker learns m1 XOR m2. This is information about m1 and m2 jointly, right? It might not be information about m1 or m2 individually, but it does represent information about m1 and m2 jointly. And that's something that should, that would be ruled out by any definition of perfect secrecy for encrypting two messages using the same key. Now, m1 and m1 XOR m2 is indeed some information about m1 and m2. But I want to stress that this is not just a technical point that we've leaked some information but in fact, it can represent some significant information to an attacker. Let me give a couple of examples. So first of all the excor of m1 and m2 reveals exactly where the messages m1 and m2 differ, right? On any positions where m1 and m2 are the same their XOR will be 0. And on any positions where m1 and m2 differ, their XOR will be 1. So the XOR of the ciphertext c1 and c2 which is equal to the XOR of m1 and m2 reveals to the attacker precisely those positions where m1 and m2 differ and that can be a significant piece of information. In addition, it turns out that some former frequency analysis can be applied, even to the XOR of two English language messages. All right. We saw in an earlier lecture that we can take standard letter frequencies of, of standard English text and use that to help cryptanalyze. Encryptions using the vigenere cipher, or the shift cipher, and the same underlying principle can be used when all you have is the XOR of, two messages. It's a little bit more difficult. A lot more difficult, actually, because XORing two plain, two English language messages tends to smooth out the distribution on the possible values of the XOR. Nevertheless, if the plain texts are long enough, it turns out this information can be used to derive lots of information about the underlying plain text m1 and m2. Finally. It turns out that, by exploiting some particular characteristics of the ASCII representation. The XOR of m1 and m2 can reveal lots more information. I want to go through that in more detail next. So here's the ASCII table that we've seen in a previous lecture, and I've highlighted that portion of the table that illustrates the correspondence between the letters of the English alphabet, both upper and lower case, and their askew equivalent. If you look at this table, what you can notice is that all letters begin with 01, or rather the ASCII representation of all letters, whether they're upper or lower case begin with the two bits 01, right? Every letter corresponds to a single bit, to a single byte, rather, or eight bits. And if you look at the eight bits that correspond to every letter, you'll see that they all share the prefix 01. In contrast to that, the space character begins with the prefix 00. What this means is that if we have the XOR of any two letters, we get some byte. With prefix 00. But, if we have the XOR of a letter, and a space character, then we get the prefix 01. And, this allows an attacker to identify the XOR of a letter and a space. Right, if the attacker has the XOR of two messages it can look byte by byte. And it can guess that any byte with a prefix of 01 corresponds to the XOR of a letter and a space. Now this is not perfect, right it's possible to have two space characters that XOR to a byte with prefix 00. It's possible to have punctuation characters as well that might mess this up. Nevertheless, punctuation characters and pairs of spaces are expected to be much less frequent than pairs of two letters and pairs of a letter and a space. Just to go through this in pictures to illustrate the point more clearly. So here we have, for example, two ciphertexts. That were both encrypted using the one time pad and the same key. And I just highlighted here the initial two bit prefix of every byte. So the rectangles they represent bites, and the bits that are displayed there are the two bit prefix of each bite. If the attacker XOR's these two cypher text together. Then it obtains what, what I've displayed on the bottom here. And what you can see, right, is that the two bit prefix of the first three bytes is 00. And the two bit prefix of the fourth byte is 01. So the attacker can guess here that the first three bytes of each of these, the underlying plain text corresponding to these two initial ciphertexts. Are letters. But in the fourth position we have a pairing of a space character, and a letter. Right, the, again, the attacker doesn't know whether the first plain-text has the letter and the second plain-text has the space or vice versa. But it can guess, with high confidence, that one of those blue shaded bytes corresponds to a letter in the underlying plain-text. And the other one corresponds to a space. Now given that, the attacker can look at the full byte, the full value of the fourth byte in the XOR of the two cipher texts, and it then knows that that byte is equal to the XOR of a space character with some other. Plain text character with, with the ASCII representation of some letter. You can easily solve this in this particular example to see that the letter is the letter p, the lower case letter p. So again, that means that the attacker has now learned that one of the blue-shaded regions corresponds to a space character in the underlying plain text. And the other blue shaded region corresponds to a lower case letter p in the underlying plain text. And if you extend this, where you can imagine that the attacker can learn lots of information about each of the underlying plain text. Things get even worse if multiple plain texts are all encrypted using the same key because then the attacker can apply the same analysis. To each possible pair, of cipher-texts. Now what we've said is that the one time pad has these two key drawbacks first of all that the key is long as the message, and secondly that the one time pad encryption scheme is only secure, if a particular key is used to encrypt only a single plain text. Now it turns out that these limitations or these drawbacks are not something specific to the one time pad encryption scheme, but they're in fact inherent limitations for any encryption scheme achieving perfect secrecy. Right, we might have thought that the one time pad encryption scheme has these drawbacks, but we can hope to do better by designing some other perfectly secret encryption scheme that doesn't suffer from these drawbacks. But that's not the case. All right. These two drawbacks are inherent for any scheme achieving perfect secrecy. I want to prove this for the particular case of the key links. That is, I want to show that the one-time pad is, in fact, optimal as far as perfectly secret schemes go, when it comes to the length of the key. And the theorem I want to prove is the following. If we have an encryption scheme defined by the algorithm Gen, Enc, and Dec, and with message space M. And if that encryption scheme is perfectly secret, then it must be the case that the size of the key space is at least the size of the message space. And that means that if we represent keys and messages. Using some fixed length bit strings. That the length of the key. Must be at least the length of the messages that can be encrypted. It turns out that the intuition for the theorem is actually very simple. The basic idea is that given any ciphertext,. An attacker can simply try decrypting that ciphertext using every possible key in the key space. We've seen this before for the example of the shift cipher, where we mentioned that given a ciphertext, an attacker can just decrypt using all 26 possible keys. If the attacker does this, then it obtains a list. Of possible messages that can correspond to that cypher text. All right, the only messages that can possibly correspond to that cypher text, are the ones that can be obtained by decrypting that cypher text, under every possible key. Now the point is that that list can contain at most, the size of the key space number of messages. Each time I decrypt with some key. I get one message. It's possible that two different keys map onto the same message, that's fine. But the point is that the list of possible messages can have a size at most the size of the key space. Now if the size of the key space is smaller than the size of the message space. Then that means that there's some message not on that list. If a message is not on the list, it means that that message could not possibly have been the one that the parties encrypted and commu, and wanted to communicate with each other. And that's already a leakage of information to the attacker. Let's turn now to the formal proof. We're given some private key encryption scheme defined by algorithms Gen, Enc and Dec, and with message space M. Let's assume that the key space is smaller than the message space. We'll argue that this implies that the scheme can not be perfectly secret. So what we need to do to show that the scheme is not perfectly secret is to show some distribution over the message base, some message m, and some ciphertext c such that the probability that the message is m, conditioned on observing the ciphertext c. Is not equal to the a priori probability with which the message was equal to M. So let's take the uniform distribution on the message space. In fact the exact distribution is not really important for this proof. What's important is just that every message in the message space can occur with some non zero probability. In any event, we'll take the uniform distribution for completeness. Take any ciphertext c in the ciphertext space. Now, consider the set M(c) which is just the decryption of that ciphertext c using all possible keys in the key space. That is we take the cypher text and we decrypt using every possible key. And each of those goes into our set M(c). The key observation that we had before was that these are the only possible messages that could've yielded the ciphertext c. Now the size of this set. Which corresponds to the list we talked about on the when we discussed the intuition for the proof. The size of the set is at most equal to the size of the key space which by assumption was strictly smaller than the message base. Now, that means that there's some message in the message base. Which is not in this set. And therefore could not have been the message that the parties were communicating. So that means that the probability that the message was equal to that message M which is not on not in that set. Conditioned on observing the ciphertext c is 0. It's simply not, possible. For the parties to have been encrypting that message M and then obtain, to obtain the ciphertext c. Simply because there's no key, for which the encryption of m using that key, would result in ciphertext c. So again, the probability that the message was equal to M, conditioned on observing the ciphertext c, is 0. And that's different from the priority probability that the message was equal to M which we said was non-0. So this concludes the proof that the encryption scheme, having a key space smaller than a message space, could not possibly be perfectly secret. So where do things stand? Well we've defined perfect secrecy, we've also shown that the one-time pad achieves it. And we've just now shown that the one-time pad is optimal, at least as far as its key length is concerned. Does this mean we're done? Well, I hope not because we've got several weeks left in the class. In fact, we're not done at all and things are just starting to get interesting. What we'd like to do is to now relax the definition of perfect secrecy. And obtain a definition which is still meaningful and useful in practice, but allows us to circumvent these inherit draw backs of perfect secrecy that we've discussed in this lecture. And this is what will occupy us for the next few lectures.
