[SOUND] In the last two lectures, we have discussed the notion of security against chosen plain text attacks, as well as the important primitive of pseudo-random functions or block ciphers. In this lecture I want to show a construction of CPA ins, secure encryption from pseudorandom functions and give a proof that the construction is indeed secure. Before I do that I just want to give one clarification, regarding something from the previous lecture. We talked there, about how block ciphers, provide a secure instantiation of pseudorandom permutations. And that's still true. What I want to point out here is that for large enough n, a random permutation is indistinguishable from a random function. And so, a pseudorandom permutation is similarly indistinguishable from a pseudorandom function. There's still a difference between the two, because a pseudorandom permutation requires, also, efficient invertibility of f sub k but nevertheless, what this means is that, any pseudorandom permutation is also a pseudorandom function, if n is large enough. Now in practice, what that means is that block ciphers are good pseudorandom functions also. And so we can use them, both whenever we need pseudorandom permutations, as well as when we need pseudorandom functions. So let me now describe for you a, an encryption scheme that we'll prove is CPA secure. Let F be a keyed function. Here we actually don't require for it to be a permutation. We'll define the encryption scheme as follows. The key generation algorithm, will choose a uniform key of length n, where n is our security parameter. To encrypt a message, m, whose length we'll assume is the same as that of the key, we do the following. We choose a uniform n-bit string R, and then we output the cypher text that contains 2 components. The first component is R itself. And the second component contains fk of r, XOR with m, so we apply our pseudorandom function F using key k to the random value r, that we've just chosen, and take the result and XOR it with m. And that gives us the second component of a cipher text. And I want to highlight here, that encryption is randomized. If we encrypt the same m bit string m, twice using the same key, we're going to get in general different results. We're going to get different cipher texts, as long as we choose different values of r each time. To decrypt a cipher text containing two components, C1 and C2, what we do is we simply apply F k to the first component C1 and XOR that with C2, in order to obtain the original message. And you can verify for yourself that correctness here holds with probability one. In pictures what we have is the following. We take our message m and our key K. And to encrypt that message under that key, we choose a uniform string r, and then evaluate our pseudo-random function F on the value r, using our key K, of course. This gives us a pseudorandom value, F K of R. It's a pseudorandom value because F is going to be assumed to be a pseudorandom function. We then exhort that pseudorandom value with our message to obtain the second component of the ciphertext. We send r as the first component of a ciphertext to allow the receiver to decrypt. Now, if you look at part of this this should look exactly, like the pseudo one time pad and it should remind you very much of that scheme. What we have is the exor of a message with a pseudo random value. The key difference here is that rather than having just a single pseudo random value defined by, applying a pseudorandom generator to the key, as in the case of the pseudo-one-time pad, what we have here is the ability to produce multiple independent looking pseudorandom values based on the single key r. And we do that by selecting a uniform value r that identifies, some pseudo random value in the function table for Fk. Maybe we can imagine the value r as specifying which entry in this huge array we're going to select out and use next as the value we're going to XOR with our message to encrypt it. This gives us the ability then, to have access to, as it were, 2 to the n different pseudorandom values that we can use for encryption. And this is precisely why we can use the scheme just described to safely encrypt more than one message. Now one thing I do want to stress here, is that the key is as long as the message, right? We were assuming that the message and the key were both of length n. And you might wonder whether we're really doing anything better than the one-time pad itself. The point here is that the scheme can be used with the same key to safely encrypt multiple messages. So this really is much better than the one-time pad. And further more if we wanted to, we could use it to encrypt longer messages, we'll get into more of a discussion of that in the following lecture What I want to do next is, explore the security of the construction we've just given. And what I really want to do is to prove the following theorem. If our keyed function, F, is indeed a pseudorandom function, then the scheme we've just presented, that I'll refer to as pi, is CPA-secure. And as previously, we're going to prove this theorem by reduction [BLEEP]. What that means is, we'll assume we have some attacker, depicted here as a devil, attacking our encryption scheme, our encryption scheme pi. And what we're going to then do is use that attacker as a subroutine, to construct a distinguisher D that's going to distinguish or try to distinguish between two cases. When it's given access to a random function, or when it's given access to F sub k for a uniform key k. Right this is the definition of security for F, the definition of it means for F to be a pseudorandom function, is that no efficient d should be able to tell these apart. So our distiguishier d has to be able to stimulate for our attacker, the effects of interacting in the CPA security experiment. So this means, first of all, that we need a way to, emulate, the encryption oracle for this attacker. That is, the attacker might request encryption of some message m, and we have to provide that attacker in return, with a simulated encryption of m, with respect to some key. The way we do that is as follows [BLEEP]. What D will do, is choose a random uniform value, r, query that value r, to its function oracle, and get back, some value that I'll call here f(r). It takes that value f(r). And x soars it with m and then provides to the attacker the simulated ciphertext containing two components, r and f of r x soar with m. And it continues to do this, for each encryption Oracle query that this attacker makes [BLEEP]. At some point later the attacker outputs two messages, m0 and m1. And what's supposed to happen in the CPA security experiment, is that one of the those is chosen and encrypted. And our distinguisher D is going to have to simulate that as well. To do that, it does what really should look like the obvious thing. It's going to sample a uniform value that I'll call r* here. And it's going to submit r star to its function oracle and get back a value f of r star. it's then going to also sample a uniform bit b, that it's going to use to select between, those two messages m0 and m1. It then takes Mb, and x or is that with the value F of r start that it received from its function oracle. And it gives the to the attacker the challenge cypher text containing the two components r star and F of r star x ored with m sub b. The attacker can continue to query the encryption oracle, but those queries will be simulated just like on the previous slide. Eventually, A, or this attacker, outputs a guess, b prime, as to the message that was actually encrypted. What we do then, is simply look, whether the attacker's guess was correct. If the attacker's guess was correct, that is, b is equal to b prime, then we output one, and otherwise, D will output zero. What we need to do now is to analyze the probability with which D outputs one when it's interacting with, a random function and the probability that D outputs one when it's interacting with F Sub k for uniform key k. Let's just define for convenience. Mu of n to be the probability that our attacker, the devil in the previous slide, that the attacker succeeds in the CPA experiment, right? So mu of n, we'll just define as the probability that A succeeds in the CPA experiment when interacting with the encryption scheme pi. We'll also let q of n. Denote a bound on the total number of encryption queries that the attacker ever makes. Now with that in place we can first look at the case of or look at the behavior of D in case it's function oracle is F sub k for uniformly chosen key k. Well, if the function that D is interacting with is S sub K for uniform K, then you can go back and check that the view of the attacker is identical to its view in the CPA, experiment. Right? The encryption inquiries of the attacker are answered exactly as they would be in that experiment. And the challenge cypher is constructed exactly as it would be in that experiment. What that means, is, that if the function article with which D is interacting contains F sub K for a uniform choice of K, then the probability that D outputs 1 is exactly the probability with which the attacker succeeds. In this CPA experiment involving pi, because D only outputs one exactly when the attacker succeeds. That just means that the probability that D outputs one in that case is precisely mu of n. On the other hand, what happens when the function oracle with, with which D is interacting, is chosen by picking a uniform function F and placing that inside the function oracle. Well in that case there are two interesting subcases we can analyze. The first thing we can look at, or the first event, is that the random value, r* that was used by D, to generate the challenge cipher text is. Was queried at some other time. Particularly to answer some other encryption oracle query. And we'll call this event repeat, so we'll say that repeat occurs, if the value r* used to answer the, to construct the challenge cipher text is ever used in answering some encryption oracle query. The other event, or the other sub case is that r* was not quarried, at any other time. And this will just be the complimentary event to event repeat [BLEEP]. And we can then express the probability that D outputs 1 when it's interacting with a uniform function f have been bounded by the probability that D outputs 1, conditioned on Repeat not happening, plus the probability that Repeat happens. I've done some simple algebraic simplifications here nothing very complicated, just straightforward probability. We can bound the probability of Repeat by q of n over 2 to the n. But why is that? Well, we can imagine, conceptually, that the value r* is chosen at the beginning of the experiment, which doesn't, doesn't change the probability space at all. Doesn't matter when we choose it. Then, we can look at, the probability with which the event repeat happens, in any particular encryption oracle query. Well, for any particular encryption Oracle query, we choose a value r uniformly at random from the set of n-bit strings. So the probability in that particular query that that r happens to be equal to r* is exactly 1 over 2 to the n. And so the probability that in any of the at most q of n encryption Oracle queries that any of those values r, is equal to our value r* is at most q of n over two to the n [BLEEP]. What about the probability that D outputs one, conditioned on no repeat occurring? So here's where things get interesting. Well, if repeat did not occur, then what we know is that the value r*, was never queried to the encryption oracle, in answering any of the encryption oracle queries. That is, a value r* was only submitted, to the function oracle of D exactly one. Now because the function in this case is a uniform function, the value f of r star is a uniform ended value. Moreover because repeat did not occur, that value, F of r* is uniform and independent of the entire rest of the experiment. Right? The whole point of saying that F is a uniform function is that the value of F of r* is independent of the value of F on any other input. So what were doing in that case, is were XOR the uniform value F of R star, with M sub B. But because F of R star, is uniform and independent of the rest of the experiment, that is equivalent to XORing M sub B, with a uniform and independent, string which is exactly like what we do, in one time pat encryption. And so there's no way whatsoever, for the attacker to determine, with probability better then one half, whether m0 was encrypted or whether m1 was encrypted. And so the probability with which D outputs one in that case, conditioned on repeat not happening, is equal to the probability with which the attacker, guesses correctly, namely guesses the value, of the bid B correctly, which is exactly one half [BLEEP]. So, now just going through the rest of the math, because we know that F is a pseudorandom function, this was the assumption of the theorem, we know that the difference in the probabilities, with which D outputs one in both of those cases, i.e, when given access to a completely random function or when given access to F sub k for uniform k, that difference must be negligible. So we know, therefore, that mu of n minus the probability, that D outputs 1 when interacting with a random function, must be negligible. And this tells us that the probability, sorry that mu of n is bounded by the probability with which D outputs 1, when accessing a random function, plus a negligible value. On the previous slide we showed that his is in turn, bounded by one half plus q of n over 2 to the n plus epsilon n. Now the key point here, is that for any polynomial Q that is regardless of the running time of the attacker, all right we know that Q of n must be polynomial because we're concerned only with polynomial time attackers. For any polynomial Q, the additive term Q of N divided by 2 to the N is negligible. Right this is a polynomial divided by 2 to the n. A polynomial divided by an exponential. And that is an example of a negligible function. Furthermore the sum of two negligible functions is again a negligible function. So we can just represent the terms q of n divided by 2 to the n plus epsilon n, by the single negligible function epsilon prime of n. And then we have that the probability with which the attacker succeeds, in the CPA experiment when interacting with pi. Is at most one half plus epslon prime of n. And that completes the proof because what we wanted to show, remember, is that, pi is secure, that pi is CPA secure and what that would mean is that for every polynomial time attacker A, the probability with which that attacker succeeds is bounded by one half plus a negligible function. And that's exactly what we've shown here.