[SOUND]. Recall from our discussion of perfect secrecy, that the notion of perfect secrecy has two inherent limitations. First of all, the key in any perfectly secret encryption scheme, must be as long as the message being encrypted. Second, the key in any perfectly secret encryption scheme, can only be used to encrypt a single message securely. Both of these are really very significant drawbacks for encryption schemes that we'd like to use in practice, where what we'd like to do is share a single key, a short key, that we can use to encrypt as many messages of as whatever length that we want. Now we've seen how we can circumvent the first limitation by relaxing the notion of perfect secrecy, and moving to a definition of computational secrecy. And in particular the pseudo one time pad allows parties to securely encrypt a very long message using a short key. But if you think about it, the pseudo one time pad, still has the second limitation. That is, the key in the pseudo one time pad encryption scheme, can only be used securely to encrypt a single message. And the reason for this is the same as for the case of the one time pad. And if you go back to our earlier discussion, where we showed attacks on the one time pad encryption scheme, when the same key is used to encrypt multiple messages, the same attacks apply to the pseudo one time pad encryption scheme as well. So how can we circumvent the second limitation? Well the first thing we need to do, is to develop an appropriate security definition for the setting where multiple messages can be encrypted using the same key. Remember that in general, cryptographic security definitions have two parts. There's the security goal, describing what it is the parties are trying to achieve, or equivalently, what they're trying to prevent the attacker from doing. And the threat model, describing the abilities that the attacker is assumed to have. Our general, our general approach here is that we're going to keep the security goal essentially the same as what we've seen before for the notion of indistinguishable encryption. But we're going to now strengthen the threat model. So if we go back to a pictorial depiction of the single-message secrecy which encompasses both perfect secrecy, as well as the notion of indistinguishability that we've talked about. What we have are two parties who share the key k in advance, and an attacker represented here by the magnifying glass, who's listening to all the communication between them. And, for single-message secrecy at a high level, what we have is one of the parties encrypting an unknown message m, generating a cipher text c, and transmitting that ciphertext across the channel. The attacker observes that ciphertext. And, roughly speaking, the scheme is secure if, given the ciphertext, the attacker can't figure out any information about the underlying message m. In the case of multiple message secrecy, where again we have multiple messages being encrypted by the same key. We have again the two parties who've shared their key in advance, but now we can think of having multiple unknown messages and one through mt. Each of which is encrypted, using the same key, giving a ciphertext that's transmitted across the channel. Now in this picture I've drawn it with all the ciphertexts going across the channel at once. But there's really no reason that has to be the case. It could be that these are being sent sequentially over time. But the point is that the attacker is observing all of them. The attacker's observing, in this case, t different ciphertexts corresponding to t different messages. Intuitively, what we'd like, is for an encryption scheme to ensure that the attacker gets no information at all about any of the messages collectively. And this notion is not going to be satisfied by the pseudo one time pad encryption scheme, even at an intuitive level. Now in fact, we could define, formally, a notion of multiple-messa, -message secrecy and then try to work with that definition. Because of our time constraints we're not going to do that. Instead, what we're going to do is jump directly to defining something stronger. Namely, security against chosen-plaintext attacks. Or what's called CPA-security. Now it's not immediate that this notion of secrecy is stronger than multiple message secrecy. But in fact if you define things appropriately you can prove that that's the case. You'll just have to take my word for it. One thing I want to point out is that CPA-security is nowadays, the minimal notion of security that an encryption scheme used in practice should satisfy. We defined the notion of indistinguishability, which translates to security for encryption of a single message. But that was really for, only for pedagogical purposes. That notion is really too weak for schemes used in practice today. So let's look intuitively, or informally, at the notion of CPA-security. What exactly do we mean by security against chosen-plaintext attacks? Well here we imagine again our two parties who have shared a key, k, in advance. And an attacker listening in to all the communication between them. Now however, we're going to allow the attacker to, as it were, specify a message, m1. And thereby request that one of those parties encrypt that message, using their shared key to generate a ciphertext c1, that's then sent across the channel and obtained by the attacker. The attacker can do this repeatedly. So it can request encryption of a second message, m2. Again, causing the sender to encrypt that message using the key, generate a ciphertext, and send that ciphertext across the channel. The attacker can repeatedly do this, and we're going to allow the attacker to do this as often as it likes, with whatever messages it likes. At some later point in time, we imagine that there's then an unknown message m, that one of the parties encrypts. And again, sends the resulting ciphertext across the channel, which is observed by the attacker. And what we'd like, again, is that this encryption scheme will guarantee that the attacker doesn't learn anything about this unknown message m, from the additional ciphertext c that is observed. You can ask whether this kind of a threat model is really too strong. In the picture we're giving the attacker the ability to request encryptions of any messages of his choice as may times as it likes. I would argue that this threat model is not to strong. And it's, and it represents a realistic threat that we need to be concerned about. In practice there can be many ways that an attacker can influence what the honest parties encrypt. It's not clear how best to model this, but by defining a strong notion of security against chosen-plaintext attacks, we automatically encompass any such influence on the part of the attacker. Moreover there can be cases where an attacker has significant control over what is encrypted. Really approximating or, or approaching with the power that we give it in the notion of CPA -security. And so again, this threat model is not unrealistic, and it does represent concerns that do arise in practice. I actually want to give a specific example of this, which is also a nice story and a good motivator for the notion of CPA-security. This is a classical example going back to World War II, involving the Americans and the Japanese. In one particular setting, we have here the US forces at Midway island, as well as the American flag representing a US base. And we have a ship supposed to represent the Japanese Pacific fleet, that's communicating back with Japanese forces back in Japan. At one point in time, the Americans intercepted a communication between the Japanese, sig, signifying that there was going to be an impending attack on a place referred to by the code name AF. You can view AF here as a ciphertext corresponding to the encryption of some unknown location that the Japanese were about to attack. Now for various reasons the Americans had reason to believe that AF corresponded to Midway Island, but they weren't sure. So they came up with a very clever mechanism for determining whether their guess was correct. What they did was they had the forces at Midway Island broadcast a message asking for help and requesting fresh water. They then listened in to the Japanese communication, and shortly afterward observed the message going back to the Japanese indicating that AF is now short of water. This corresponds exactly to a chosen-plaintext attack. Right? The Americans were able to influence the Japanese to encrypt something related to Midway Island. They were then able to observe the ciphertext AF. And from that, conclude that AF very likely corresponded, indeed, to Midway Island. It turned out that the American guess was correct. They were able to deploy forces to Midway Island and defeat the Japanese in that battle. This really did represent a turning point in the war. And interestingly, if the Japanese had been using a CPA-secure encryption scheme, perhaps history might have been different. Let's now define formally the notion of CPA-security. As usual, we're going to fix an encryption scheme pi. Fix a particular adversary A. And then define a randomized experiment based on pi and A. The experiment that I'm calling here PrivCPA is parameterized by our security parameter n, and proceeds in the following way. In the first step, we run the key generation algorithm of the encryption scheme to obtain a key k. We then allow the attacker to interact with what we're going to call an encryption oracle. This encryption oracle allows the attacker to submit messages of his choice. And to get back encryptions of those messages, using the key k chosen in the first step. The attacker can interact with the oracle as many times as it likes. And then at some point it outputs a pair of messages, m0 and m1, of the same length. In the next step of the experiment we choose a uniform bit b. And we encrypt the message mb, using again the same key that we chose in the first step. This generates a ciphertext c, which is given to the attacker. We allow the attacker to then continue to interact with the encryption oracle as many times as it likes. Finally A outputs a bit b prime which can be viewed as representing its guess as to which of the two messages was the one that was encrypted. We'll say that A succeeds if its guess is correct, and the experiment evaluates to 1 in that case. We can now define what it means for an encryption scheme, pi, to be CPA-secure. We'll say that pi is CPA-secure if for all efficient, i.e probablistic polynomial time attackers A, there's some negligible function epsilon, such that the probability with which A succeeds in the previous experiment, is at most one-half plus epsilon. As before, the attacker can trivially succeed with probability half just by guessing. But we require that the attacker cannot do any better than this. Or at least, not substantially better. The definition is all well and good, but you might be worried that the definition is impossible to achieve. And in fact, we can give a sort of impossibility proof for that statement. Consider the following attacker A. This attacker will choose two messages, m0 and 1. And then request encryption of m0, and requist, and request encryption of m1 via its encryption oracle. In doing so, it obtains a ciphertext c0 responding to encryption of m0. And a ciphertext c1 corresponding to encryption of m1. It then outputs m0 and m1 as its two challenge messages, and gets back a challenge ciphertext c. It then simply compares whether c is equal to c0 or c1. If c is equal to c0, then A guesses is that m0 was encrypted, and outputs 0. And if c is equal to c1, then A guesses that m1 was encrypted in outputs 1. And it look like, this allows A to succeed with probability 1. This seems to show that for any encryption scheme, there's an attack in the sense of a chosen-plaintext attack, that violates our definition, because it succeeds with probability the attacker here succeeds with probability more than one half. So is the definition impossible to achieve? Well in fact, if you look carefully, at this attacker you'll see that this attack only works if encryption is deterministic. That is, if we assume that the encryption of m0 using a key k always gives the same result c0. And encryption of m1 using k always gives the same result c1. But in fact, if encryption is randomized, then it can be the case that when I encrypt m0 multiple times, even using the same key, I get different ciphertext each time. So in fact the impossibility result, or this attacker, only shows that CPA-security is impossible to achieve for deterministic encryption schemes. The moral here is that if we want to ho, a hope to achieve CPA-security, we need to use randomized encryption. This is actually a very important point, and I stress that the issue is not an artifact of the definition, or an indication that the definition is too strong. In reality, it really is a problem, if an attacker can tell when the same message is encrypted twice. So is we want to define a meaningful notion of security, even in the case where multiple messages can be encrypted, then we really do need a randomized encryption scheme which also hides information about whether the same thing is being encrypted multiple times. In the next lecture, we'll study pseudorandom functions, a primitive that we're going to rely on for constructing CPA-secure encryption.
