Now that we know that block cyphers are we know how to construct them, let's see how to use them for secure encryption? But before that, I wanna briefly remind you of an important abstraction called a pseudo-random function, and a pseudo-random permutation. So as we said in the last module, a block cipher's map, N bits of inputs to N bits of outputs. And we saw two examples of block ciphers, triple DES and AES. Now, an important abstraction of the concept of a block cipher, is captured by this idea of a PRP and a PRF. And remember that a pseudo-random function, a PRF, basically is a function that takes two inputs. It takes a key and an element in some set X. And in outputs an element in some set Y and for now the only requirement is that there's an efficient algorithm to evaluate this function. We're going to talk about security for PRFs in just a minute. And then similarly, there's a related concept called a pseudo-random permutation, which is similar to a PRF. In fact, there's also an efficient algorithm to evaluate, the pseudo-random permutation. However, there's an additional requirement, that there's also an algorithm D that will invert this function E. So a PRP, is basically a PRF, but where the function is required to be one to one for all keys. And there is an efficient inversion algorithm. So now lets talk about how to define secure PRF's. So we already said that essentially the goal of a PRF is to look like a random function from the set X to Y. So to capture that more precisely we define this notation, funs XY to be the set of all functions from the set X, to the set Y. Similarly, we defined the set S sub F to be the set of all functions from the set X to Y that are defined by the PRF. In other words. Once you fix the key K, you obtain a function from the set X to the set Y. And the set of all such functions, given a particular PRF, would be the set S sub F. So as we said last time, funs XY is generally a gigantic set of all functions from S to Y. I think I mentioned that, in fact, for AES, where X and Y are two to the 128, the size of the set is two to the 128 times two to the 128. It's a double exponential, which is an absolutely enormous number. On the other hand, the number of functions defined by the AES block cipher is just two to the hundred and twenty-eight. Namely, one function from each key. And what we would like to say is that a random choice from this huge set is indistinguishable from a random choice from the small set. And what do we mean by indistinguishable, we mean that an adversary who can interact with a random function in here, can't distinguish that interaction from an interaction with a random function in here. Now let's find out more precisely. So we're gonna, as usual, define two experiments. Experiment zero and experiment one. And our goal is to say that the adversary can't distinguish these two experiments. So in experiment zero, the challenger, basically, is gonna choose a random, pseudo-random function. Okay? So he's gonna fix the key K at random, and that's gonna define this function, little f over here, to be one of the functions implemented by the PRF. And experiment one, on the other hand, the challenger is gonna choose a truly random function from the set X to the set Y. And again, we're gonna call this truly random function little f, either way, either experiment zero or experiment one, the challenger ends up with this little function f that's either chosen from the PRF, or chosen as a truly random function from X to Y. Now the adversary basically gets to query this function, little f. So he gets to submit a query X1 and he obtains the value of f at the point X1, then he gets to submit at X2, and he obtains the value of f at the point X2. So on and so fourth, he makes Q queries. And so he learns the value of the function little f at those Q points. Now his goal is to say whether the function little f is chosen truly at random from funs XY, or chosen just from the set of functions implemented by the PRF. So he outputs a certain bit b prime and we'll refer to that output as the output of experiments, either as experiment zero or experiment one. As usual we say that the PRF is secure. If, in fact, the adversary can't distinguish these two experiments. In other words, the probability that he outputs one, experiments zero is the same, pretty much the same as the probability that he outputs one in experiment one. In other words, the difference of these two probabilities is negligible. So this captures nicely, the fact that the adversary couldn't distinguish a pseudo-random function from a truly random function from the set X to Y. Now, the definition for a secure pseudo-random permutation, a secure PRP, which is basically a secure block cipher, is pretty much the same. In experiment zero, the adversary's gonna change a random instance of the PRP. So he's gonna choose a random K, and define little f to be the function that corresponds to little k within the pseudo-random permutation. In experiment one: the adversary is gonna choose not a truly random function from X to Y, but a truly random one to one function from X to X. Okay? So the goal of our PRP is to look like a random permutation from X to X. Namely, a random one to one function from the set X to itself. So the little functional little f here is again gonna be a random function. From the set X to itself. And again, the challenger ends up with this function, little f. As before, the adversary gets to submit queries and it gets to see the results of those queries. And then he shouldn't be able to distinguish, again, experiment zero from experiment one. So again, given the value of the function f at cue points chosen by the adversary, he can't tell whether the function f came from a PRP, or whether it's a truly random permutation from X to X. So let's look at a simple example. Suppose the set X contains only two points, zero and one. In this case, Perms[X] is really easy to define. Essentially, there are two points, and we're looking at, you know, 01. And we're asking, what is the set of all invertible functions on the set 01. Well, there are only two such functions. One function is the identity function. And the other function is basically the function that does crossovers, namely this function here. These are the only two invertible functions in the set 01. So really, Perms[X] only contains two functions, in this case. Now, let's look at the following PRP. The key space is gonna be 01, and of course, X is gonna be 01. And let's define the PRP as basically X XOR K. Okay so that's our PRP and my question to you is, is this a secure PRP. In other words, is this PRP indistinguishable from a random function on Perms[X]? I hope everybody said, yes, because essentially, the sets of functions implemented in this PRP, is identical to the set of functions in Perms[X]. So a random choice of key here is identical to a random choice of function over here. And as a result, the two distributions, either pseudo-random or random, are identical. So clearly, an adversary can't distinguish the two distributions. Now, we already said that we have a couple of examples of secure PRPs triple DES and AES. And I just wanted to mention that, if you want to make things very concrete, here's a concrete security assumptions about AES. Just to give an example, say that all algorithms had run in time 2^80 have advantage against AES of utmost 2^-40. This is, a reasonable assumption about AES, and I just wanted to state it for concreteness. So let's look at another example. Consider again the PRP from the previous question. Namely XX or K. Remember the set X was just one bit, namely the value zero and one. And this time, we're asking, is this PRP a secure PRF? In other words, is this PRP indistinguishable from a random function from X to X? Now, the set of random functions from X to X, Funs[XX] in this case, contains only four elements. There are the two invertible functions, which we already saw in... I believe the identity function, and the negation function, the function that sends zero to one, and one to zero. But there are two other functions. Namely, the function that sends everything to zero. And the function that sends everything to one. Okay, these are four functions inside Funs[XX], and the question is: Is this PRP that we just looked at, is it also indistinguishable from a random choice from Funs[XX]? So I hope everybody said no and the reason it's not a secure prf is because there's a simple attack, namely the attacker supposed to distinguish whether he's interacting with this PRP or is he interacting with a random function from Funs[XX]. And the distinguisher is very simple. Basically we're gonna query the function at both x equals zero and x equals one, and then if we get a collision, in other words, if f of zero is equal to f of one, then for sure we're not interacting with a PRP. In which case we can just output one. In other words we're interacting with a random function. In other words we say zero. So let's look at the advantage of this distinguisher. Well when it's interacting with a PRP, it'll never output a one, because f of zero can never be equal to f of one. In other words, the probability of outputting one is zero. However, when we interact with a truly random function in Funs[XX], the probability that f of zero is equal to f of one is exactly one-half. Cause half the functions satisfy F of zero's equal to F of one, and half the functions don't. So then, we'll output one with probability one-half. So the advantage of this distinguisher is one-half, which is non-negligible. And as a result, this PRP here is not a secure PRF. Now it turns out this only true because if set X is very small. And in fact there is an important lemma, called the PRF Switching Lemma, that says that a secure PRP, is in fact a secure PRF, whenever the set X is sufficiently large. And by sufficiently large, I mean say the output space of AES which is two to the 128th. So by this lemma which will state more precisely in a second, AES if it's a secure PRP, it is also a secure PRF. So this lemma basically says the following, if you give me a PRP over the set X Then for any adversary that queries the PRP, at at most Q points, so it makes at most Q queries into the challenge function. Then, the difference between its advantage in attacking the PRP when compared to a random function, is very close to its advantage in distinguishing the PRP from a random permutation. In fact the difference, is bounded by this quantity here, and since we said that X is very large, this quantity Q squared over 2X is negligible. Okay. That's gonna be our goal. So essentially, again, when X is large, say two to the 128, Q say is going to be two to the 32. That's a billion queries that the adversary makes. Then, still the ratio is going to be negligible. In which case, we say that the adversary's advantage is distinguishing the PRP from a random function. It's pretty much the same as its advantage of distinguishing a PRP from a random permutation. So, again, it's basically, if E is already a secure PRP, then it's already a secure PRF. So for AES, AES, we believe, is a secure PRP. And therefore, AES, we can also use it as a secure PRF. And so, as a final note, I just want to mention that, really, from now on, you can kinda forget about the inner workings of AES and triple DES. We're simply gonna assume that both are secure PRPs, and then we're gonna see how to use them. But whenever I say PRP, or PRF, you should be thinking in your mind, basically, AES or triple DES.
