Music Music Music Music Music Music Music Music Music Music Music Music Music Music Hello everyone, welcome to lecture 13. The plan for this lecture is as follows. We will introduce a very important building block for the symmetric key cryptography namely pseudo random function and later we will see that how the pseudo random function acts as a fundamental building blocks for designing many beautiful symmetric key primitives. We will also discuss variants of pseudo random function namely pseudo random permutation and strong pseudo random permutation and we will see how to construct pseudo random generators from pseudo random function.
So let us start our discussion on pseudo random function. On a very high level a pseudo random function is a deterministic algorithm with two inputs and a single output. So, the first input for the function f is actually a key which is going to be uniformly random and we will assume that a key size is little n where little n is some security parameter. So, that is why we often call the function f as a keyed function because it is going to be operated by a key and a second input for the function f is actually the input x which we also call as the block and the size of this block is going to be little l bits.
and output of the function is f denoted as y which is basically the function f on the input k and input x and it is going to be a Bigel bits. So in practice the size of n, l and Bigel can all vary and later on we will see various instantiations of pseudo random function where indeed n, l and Bigel, little l and Bigel are different but asymptotically everything has to be some polynomial function of your security parameter. Now, how we are going to use this pseudo random function? So whenever we are designing any cryptographic primitive, the way we use this pseudo random function is as follows.
At the beginning of the instantiation of the cryptographic primitive, which uses this function f, either the sender or the receiver is going to use a generator uniformly random key and somehow it will be established with the receiving party as well and it would not be known to the attacker. And once the key has been fixed, we are not going to change the key throughout that session or throughout that instantiation, the key will remain the same. Now once we fix the key, right, you can imagine that the function f is now behaving as a single input function, namely taking little l bit blocks and producing big l bit output.
So we denote that single input function as the keyed function fk. Where K is going to be fixed and it would not be known to the attacker. That is the way we are going to use a pseudo random function.
Now what exactly is the security property we require from this pseudo random function and informally we require the following. If the K is unknown and uniformly randomly chosen from the domain of the key space, we Then we basically require that the behavior or the output of this keyed function fk should almost resemble the output of any truly random function mapping little l bit strings to big l bit strings. So, remember a truly random function is an unkeyed function.
So, what basically want is that this keyed function fk once the key has been randomly chosen its behavior should almost resemble the behavior of a pseudo random function. So, let us go little bit deeper into what exactly I mean by the formal statement. So, imagine you have a truly random function which is an unkeyed function, it does not have any key, it just takes an input of size little l bits and it produces an output of size big L bits. So, it is easy to imagine the behaviour of a truly random function as follows.
So, what this truly random function basically takes is an input of size x and it produces an output of size big L bits. And you can imagine that basically this truly random function maintains a table consisting of 2 to the power literal rows right. We are basically the first row stores the value of the function at all 0s, the second row stores the value of the function at input all 0s and 1 and the last row stores the value of the function at the input all 1s. So whenever this truly random function receives an input x what basically it does is it internally checks whether. there is already an entry for the value of this truly random function at the input x.
If it is not there, then fill that row namely f of x. x by a uniformly random bit string of length big L bits and denote it as y and for the future invocations of this truly random function set that y to be the output of the truly random function on the input x. On the other hand if the value x which has been passed you have already have an entry corresponding to that entry x in this table then just pass on the value which is stored in that corresponding row as the output y.
So that is the way you can imagine. the behavior of a truly random function. The important thing here is that since this function is a truly random function each row here is an independent string of length Big L bits. That means if you consider the entry or the value of the truly random function at input x and input x dash where x and x dash are different then the corresponding y outputs are independent of each other.
That means If there exist an algorithm which has not yet seen the value of the truly random function on some input x, it cannot predict what exactly the value of the function is going to be for that input x except for guessing the output and the guessing will be successful with probability 1 over 2 to the power L. Apart from that there is no way to predict the outcome of the truly random function on some input x. And this holds even if that algorithm which is actually trying to predict the outcome of this truly random function on the input x has already seen the output of this truly random function on several previous x values which might be related to this new x values.
This is because each row in the table of this truly random function is independent of each other. The security property that we require from a pseudo random function is that once we fix the key. by selecting the key uniformly randomly and once you fix the key then that keyed function should also have the similar properties except with a negligible probability.
So what exactly that means is that on your left hand side you have a keyed function f k where the description of the function f is publicly known I stress the description of the function is publicly known what is not known is basically the value of the key. And on the right hand side you have a truly random function this basically consists of 2 to the power little l rows each entry consisting of a uniformly random string of length bigger bits. And when I say that my function f is a pseudo random function what basically I mean is that there exist no polynomial time static statistical test or statistical algorithm right which can significantly distinguish apart an output of the algorithm fk. from the output of this truly random function right. That means if our distinguisher or the statistical test is basically given outputs of either the function fk or the output of the truly random function on several inputs of adversaries or distinguisher choice from the viewpoint of the distinguisher those output could be as likely to come from the function fk as it is likely to come from this truly random function.
Now before we go further this condition is similar to the way we have actually defined the notion of pseudo random generator. So, remember in the pseudo random generator that security is defined by saying that there exists no statistical test which when given a sample cannot distinguish apart whether that sample is generated by running a pseudo random generator or by running a truly random generator. So, in that experiment The distinguisher was given only one sample because our pseudo random generator is a single input function. So, for each invocation of the pseudo random generator the sample is going to be different because the key for the pseudo random generator is going to be different.
But in the context of pseudo random function the way we are going to use a pseudo random function in real world application is that the K will be fixed once for all at the beginning of the session and then the X inputs are going to be varied and each invocation of the keyed function will be with the same key. So, what we are now going to do is that in our formal definition basically the adversary is going to be given many samples and he has to distinguish apart whether those samples are generated by running a keyed function fk or by running a truly random function. So, let us see what exactly are the formal details.
So, you are given the description of a publicly known function and the experiment we call as indistinguishability experiment against the PRF with respect to a distinguisher algorithm against the function f and little n is the security parameter. The rules of the games are as follows, the distinguisher is allowed to ask for the function output at many x inputs of his choice. and it can ask its queries adaptively that means it can first ask for the function output input at input X1 and then based on the response it can decide what should be X2 and then based on the response it can decide what should be X3 and so on. So we put absolutely no restriction on what kind of queries the distinguisher is asking. Now once the distinguisher submits its queries the challenger here has to come up with the response namely the output of the functions at those inputs and the way the challenger would have prepared those response is as follows.
Basically, the challenger is going to toss a uniformly random coin which is either going to output 0 or 1 with probability 1 by 2. If the coin toss is 0, then all these responses y1 to yq are basically generated by running a truly random function on those X inputs. In a more detail, all these Y strings are basically independent of each other and each of them is basically a uniformly random bit string of length Bigel bits. On the other hand, if the coin toss of the challenger is 1, then this Y outputs are basically the output of a keyed function FK where the key is chosen uniformly randomly by the challenger. And now the challenge for the distinguisher is to find out how exactly this responses Y1 to YQ are generated, whether they are generated by mechanism 0 or whether they are generated by mechanism 1. That is the challenge for our distinguisher. So, distinguisher in this case outputs a B dash which is either which is going to be a bit which basically says whether it feels that the samples Y1 to Y2 are generated by mechanism 0 or by mechanism 1 and our security definition is we say that the function F is a pseudo random function if for every probabilistic polynomial time algorithm D participating in this experiment there exist a negligible function.
such that the probability the distinguisher correctly identifies the label or the nature of the samples Y1 to YQ is upper bounded by half plus negligible. Again the probability is taken here over the random choice of the challenger and the random queries of the distinguisher. Another equivalent formulation of the same definition is that we say that the function F is a PRF if the distinguishing advantage of our distinguisher is upper bounded by a negligible function.
That means it does not matter whether B is equal to 0 or whether B is equal to 1. That means it does not matter whether the Y samples are generated by a truly random functions or whether they are generated by a pseudo random function. In both the cases, the distinguisher should output the same output. say b dash equal to 1 except with negligible probability and again we can prove that if we have a pseudo random function which satisfies the first condition then it also satisfies the second condition and vice versa.
So depending upon our convenience we can use either of these two definitions. So that is the definition of our pseudo random function and basically the intuition in this experiment is that we are giving our distinguish, distinguishing an oracle access to the function Where the function is either a truly random function or a keyed function and basically distinguisher has to distinguish apart whether it is interacting with a truly random function oracle or whether it is interacting with a keyed function oracle and the security definition demands that except with negligible probability it should not be able to distinguish apart. Notice that here we are required to upper bound the success probability of the adversary by half plus negligible, we cannot put a definition saying that a success probability of the distinguisher should be 0 because there is always a guessing distinguisher who can just guess that it is interacting with say either TRF or PRF and with probability half.
It can actually correctly identify or the probability half is guess could be actually correct. So, we can never put a condition that a success probability of the distinguisher should be 0. The additional negligible advantage is basically due to the necessary evil associated with the fact that we are in the computational world. So, now let us see whether it is easy or whether it is how easy or how difficult it is to construct a pseudo random function. So, imagine I design a function f as follows and for simplicity I assume that the key length, the block length and output length are of same size namely say n bit strings and the way the output of the function is defined is basically take perform the XOR of the key and the block that is the way output is computed.
And our goal is to either prove or disprove whether this function is a pseudo random function. In fact, we want to disprove that this construction is not a PRF. And for that we basically want to argue whether indeed the outputs of this function f is a going to produce pseudo random outputs once we fix the key. And if you go little bit deeper into the algorithm you can clearly see the following fact.
If we have a truly random function mapping n bit strings to n bit strings then the output of the truly random function on two different inputs x1 and x2 will be completely independent of each other. On the other hand for the function f that we are considering it does not matter what key you use it could be any random key of size little n bit. Once you fix the key k then the behavior of the function fk is as follows for any input x1 and x2 which are different their outputs y1 and y2 will be related by the fact that XOR of the outputs y1 and y2 is exactly the same as XOR of x1 and x2.
That means you now have a test which will always pass. or which will always hold for the samples which are generated by the function fk and you have a test the same test may not always be applicable for the samples which we are generated by a truly random function. So, this basically gives us an intuition to design a distinguisher which can distinguish apart the outcome of this function f from the outcome of a truly random function.
So, here is the instance of the distinguisher it basically ask for the value of the function f. at input x1 comma x2 which are different and in response the challenger replies with outputs y1 and y2 and the way this y1 and y2 would have been generated as per the PRF indistinguishability game is as follows. The challenger would have basically tossed a coin if the coin toss is 0 then y1 and y2 are random in bit strings whereas if the coin toss is 1 then y1 and y2 are the outcomes of the keyed function fk for a uniformly random key known only to the challenger. And now distinguisher can act smart and can act smartly and basically distinguish apart whether Y1 and Y2 are generated by a truly random function or a pseudo random function by just performing this test. It checks whether X1 and X2 their XOR is same as the XOR of Y1 and Y2.
If that is the case, then it says that hey, the samples Y1 and Y2 are generated by the mechanism B equal to 1 namely it submits B dash equal to 1. Whereas if the test fails and it says hey. the mechanism the samples Y1 and Y2 are generated by mechanism 0 namely B dash equal to 0. Now let us analyze what is the distinguishing advantage of this particular distinguisher. So let us first analyze what is the probability that our distinguisher is correctly labeling the samples Y1 and Y2 generated by a pseudo random function indeed being the samples of a pseudo random function namely the probability. D outputs B dash equal to 1 given B equal to 1 and I claim that this probability is equal to 1 because if indeed B is equal to 1 that is a case the samples Y1 and Y2 are as per the outputs of a pseudo random function and in that case this condition the check that the adversary or the distinguisher is performing will always pass right that is why with probability 1. If b little b is equal to 1, the strategy of the distinguisher will indeed output b dash equal to 1. On the other hand, let us calculate the second probability that what is the probability that our distinguisher incorrectly labels truly random samples y1 and y2 being the samples of a pseudo random function.
Well, if little b is equal to 0 that means our samples y1 and y2 are independent of each other then the only case the only way the distinguisher can still output b dash equal to 1 is that for uniformly random y1 and y2 this condition holds or in other words the probability that the distinguisher output B dash equal to 1 given B equal to 0 is same as for a uniformly random Y1 and Y2 this condition hold and this can hold only with probability 1 over 2 power n. So, that gives us the distinguishing advantage of the distinguisher that we have designed and if you take the absolute difference it is almost equal to 1 that means with almost 100 percent probability if n becomes large then this 1 minus 2 power of minus n. almost becomes 1. So that is why with almost 100% probability our distinguisher can distinguish apart the outcome of this keyed function f from the output of a truly random function and that is why this function f is not a pseudo random function.
So that means designing pseudo random function is indeed a challenging task. We will see the candidate constructions later on. Now, let us define some other variants of pseudo random functions with more stronger properties and security guarantees. So, the first variant is called as the pseudo random permutation which is also known as block cipher and here again we have a keyed function f. The only difference here is that that a keyed function fk should be now a bijection namely the size of the block and the size of the output should be same big L bits that is the only difference.
And informally the security property that we require here is that we require that once we fix the key by selecting a uniformly random key and the key is not known to the attacker or a distinguisher then though polynomial time distinguisher can distinguish apart the output the behavior or the nature of this keyed function fk from a truly random bijection mapping big L bit strings to big L bit strings which again can be modeled as an indistinguishability experiment. So, this indistinguishability experiment we call as the PRP indistinguishability experiment and we have a bijection here keyed bijection and basically we want to capture the intuition that no distinguisher should be able to distinguish apart the behavior of this keyed bijection from a from an unkeyed truly random bijection. So, the rules of the experiments are as follows, distinguisher queries for several X inputs of its choice and in response the challenger gives backs the answer. Where the answers are prepared in either by following either of the following rules, it tosses a coin if the coin is 0 then all these samples Y1 to YQ are basically generated by running a truly random permutation.
Whereas if the coin toss is 1 then all these samples are generated by running the keyed function F on a uniformly random key not known to the distinguishing. And the challenge for the distinguisher is to find out what exactly is the way this samples why is the way why the samples are generated that means it has to output a bit and our security definition is that we say that a Keat bijection F is a PRP if the probability that any polynomial time distinguisher can correctly identify the nature of the sample is upper bounded by half plus negligible. or equivalently saying that the distinguishing advantage of our distinguisher should be upper bounded by a negligible function.
So in essence everything is same as for the case of pseudo random function the only difference is that we are now basically require we are basically our PRP in the case of PRP the function is now a bijection. So it is interesting to see the relationship between these two primitive pseudo random function and pseudo random permutation. So On your left hand side part you have a pseudo random function the difference here it is a function that means the input length the block length and output length could be different whereas in the case of pseudo random permutation it is a bijection that means in the case of pseudo random functions it could be a many to one function whereas in the case of pseudo random permutation it is a one to one on to mapping. So, since our PRF need not be a bijection, it is easy to see that a PRF need not be a PRP. What about the other way around?
So, if the output size L is greater than equal to little n or in more generic terms if the output size is some polynomial function of the security parameter n then we can view a pseudo random permutation as a pseudo random function. And the intuition for this statement is as follows since we know that our imagine we are given a keyed permutation right. So, this is a FK is a keyed bijection and since it is a secure PRP that means no polynomial polynomial time distinguisher can distinguish apart and interaction with this keyed function fk from a truly random bijection or from a truly random unkeyed bijection right.
That sense both this primitives fk and ftrp are computationally indistinguishable. Now, if we compare a truly random function mapping big L bit strings to big L bit string, how exactly it is going to be different from a truly random permutation? Well, the only difference between a truly random function from an unkeyed truly random function and an unkeyed truly random permutation is that a function need not be a bijection that means there are chances of collisions that means it could be a many to one function where several X inputs could give you the.
same Y output whereas in the case of truly random permutation there are no chances of collisions. So, the only way any distinguisher can distinguish apart a unkeyed truly random function from this keyed bijection FK is the following. If it so happens that our distinguisher is interacting with the unkeyed truly random function and if so happens that some of its queries gives him the same output.
then it can clearly identify that it is interacting with a unkeyed truly random function because if it is interacting with this keyed by ejection FK the collisions are not going to happen. That means we can say that conditioned on the event that Our distinguisher queries are never going to lead to a collision then the interaction of our distinguisher with FK and FTRP, TRF is almost the same as if the distinguisher is interacting with FK versus F truly random permutation and since our function FK is a keyed permutation we know that that interaction is computationally indistinguishable. So conditioned on the event that our distinguisher is not getting collisions from its queries to the other.
The interaction of our distinguisher with the unkeyed truly random function and a keyed bijection FK are almost going to be identical. Now the question is what is the probability of the distinguisher getting a keyed bijection FK? collision by making Q random queries through the unkeyed truly random function.
If it is making Q random queries then using a well known result which we call as the Burde paradox bound which we will discuss more regressly in the context of hash function we can prove that the chances of getting a collision can be upper bounded by the probability Q square by 2 power L. And that is why if your big L is some function polynomial function of the security parameter n then clearly this is a negligible quantity. That means the chances of collisions being happening is negligible and that is why we can say or we can treat the keyed bijection FK also as a pseudo random function. So that is a relationship between pseudo random functions and pseudo random permutations. Now, let us see the final variant of pseudo random functions which we call as strong pseudo random permutations or SPRP which is a special kind of pseudo random permutation and basically here we require that the keyed bijection FK should be indistinguishable from a truly random permutation even if the distinguisher gets oracle access to the inverse of the permutation.
What I mean by that is demonstrated in this experiment. So this indistinguishability experiment is called as that. SPRP indistinguishability experiment and here the distinguisher now gets access or response for two types of queries. It has got oracle access to the values of the permutations and it also has access oracle access to the inverse of the permutation. What I mean by that is it can adaptively ask for the value of the permutations at several X inputs of its choice and in response it gets back the corresponding Y outputs.
And it is also allowed to ask for the inverse of the permutations of several Y values of its choice and sees the corresponding X values. And the way the challenger would have responded is as follows, it would have tossed a uniformly random coin if the coin toss is 0, then all these queries. are responded by evaluating a truly random permutations that means all these x values are evaluated as per this truly random permutations and all this inverse queries are also answered by querying the inverse of that corresponding truly random permutations. On the other hand, if the coin toss B is equal to 1, then all these Y values and all these inverse values are computed by running the Keet function FK and the inverse values.
inverse of that keyed function fk and the challenge for the distinguisher as usual is to identify whether it has interacted with a oracle which represents a truly random permutations or whether it is interacted with an keyed oracle fk and our security definition is we say that the function f in is a pseudo strong pseudo random permutation if no polynomial time distinguisher can correctly identify the nature of its oracle except with probability half plus negligible or put it in other words the distinguishing advantage of our distinguisher should be upper bounded by a negligible quantity. It turns out that if we have a strong pseudo random permutation then by definition it is also a pseudo random permutation and we can give constructions where the construction will be a pseudo random permutation that means it will be secure only if the adversary gets access to the oracle queries for the function output but it need not be a strong pseudo random permutation that means as soon as we provide a distinguisher access to the inverse oracle the adversary can distinguish apart that means the strong pseudo random permutation is a more stronger primitive than the pseudo random permutation. Now, let me end this lecture with by giving an example of how to construct a strong how to construct a pseudo random generator from a pseudo random function. So, imagine you are given a secure PRF which is a keyed function mapping little l bit strings to big L bit strings. Now using this I can construct a pseudo random generator G which takes a key of size or seed of size n bits and it produces an output of size t times big L bit.
And basically the way this algorithm G operates is as follows, it takes the seat K for the algorithm G and treat it as the K for the pseudo random function F and the pseudo random function F is now evaluated at publicly known inputs 1, 2, 3 up to T. That means the block inputs that are used inside this algorithm G are publicly known, they are 1, 2 up to T. It is only the key which is not going to be known to the distinguisher and each invocation of this function f is with the same key which is actually the input of our pseudo random generator G and the output of the pseudo random generator is basically the concatenation of the individual outputs which are obtaining by running the t instances of the keyed function fk. That is the way our pseudo random generator is going to be operated.
Now, we want to prove that if the function fk the keyed function fk is a secure PRF as per our notion of indistinguishability then the algorithm G which we have constructed is also a secure PRG as per the PRG indistinguishability game provided the number of times we have invoked the pseudo random function fk namely T is some polynomial function of the security parameter. And to prove that let us first understand the intuition. We come we basically consider another version of the algorithm G which I call as GTRG where each instances of this keyed function FK. is replaced by an instance of a truly random function mapping little l bit string to big l bit string.
That means the only difference between the algorithm gtrg and the algorithm g that we are actually considering is the nature of the function that we are invoking inside the construction. In the case of g it is basically the keyed function fk and inside the algorithm tgrg it is a unkeyed truly random function. The intuition behind our claim that we want to prove here is the following. If there exists a distinguisher who can distinguish apart this kind of sample from this kind of sample then we can prove through a reduction that using that distinguisher as a subroutine or as a black box. we can design another distinguisher who can distinguish apart the output of a truly random function FTRP from the output of the keyed function FK which is a contradiction to our assumption that the function FK is a keyed PRF.
So let us formally establish the intuition that we are So, you have the two algorithms on your left hand side you have the PRG construction that we have constructed and we want to basically prove that these two constructions are almost identical right. On the right hand side part you have a corresponding truly random generator which is actually generating T blocks each of size bigger bits by running T independent invocations of pseudo random invocations on input 1, 2, T. Now, imagine you have a PRG distinguisher right who can distinguish apart a Y sample generated by the algorithm G from a Y sample generated by GTRG.
Now, using that distinguisher PRG using that PRG distinguisher we are going to design another polynomial time PRF distinguisher and the PRF distinguisher works as follows. It basically invokes an instance of the PRF indistinguishability game. So this part of the experiment which I have highlighted is the PRF indistinguishability experiment where basically the distinguisher ask for the oracle queries at inputs x1 equal to 1, x2 equal to 2 and xt equal to t and in response it gets T blocks each of size bigger bits where as per the PRF indistinguishability game the Y samples are generated as follows.
If the coin toss of the challenger is 0 which can happen with probability 1 by 2 all these samples Y1 to YT are actually the outcomes of a truly random function an unkeed truly random function. Then, the samples y1 to yt basically are the outcomes of the keyed pseudo random function for an unknown key K which is not known to the distinguisher and the goal of the distinguisher is to find out whether the samples are as per the mechanism b equal to 0 or are they are as per mechanism b equal to 1. Now, before we go little bit further, let us understand what is exactly is happening in this PRF indistinguishability experiment. If you see The way our distinguisher for the PRF has queried its challenger and got the response, it knows that if this samples Y1 to Yt are as per the mechanism B equal to 0, then it knows that if it concatenates all this Y block, then basically it corresponds to a sample generated by the algorithm G which we want to prove to be secure. On the other hand, if this blocks Y1 to Yt, are generated as the outcome of the keyed function fk then the PRF distinguisher knows that the concatenated y1 to yt are as the same as if it is generated by running an instance of the truly random generator TRG. And now notice that our PRF distinguisher it itself does not know what exactly is the nature of y1 to yt because that is what its goal is but it knows the fact that if it concatenates these samples y1 to yt.
then either it is going to get a sample that would that an algorithm G would have produced or the algorithm GTRG would have produced. So that is a fact which we are now going to utilize. So the PRF distinguisher is now going to invoke our PRG distinguisher as a subroutine and it challenges the PRG subroutine to identify what exactly is the nature of this. bigger sample Y, capital Y, right. So this big Y is basically the concatenation of the T samples which are thrown to the PRF distinguisher and this PRG distinguisher is used as an oracle here, as a subroutine here.
The PRF distinguisher cannot go inside the PRG distinguisher and find out how exactly the PRG distinguisher it acts. What the PRG distinguisher is going to output? It is going to output a bit.
which I denote by big B, big B equal to 0 indicates that the PRG distinguisher is labeling the sample big Y to be generated as per the truly random generator whereas the output big B equal to 1 is interpreted as if the PRG generator is labeling the sample big Y to be generated by the algorithm G. Now based upon the response that our PRG generator has output. What the PRF distinguisher is going to do is it outputs the same output in the instance of the PRF experiment.
So what exactly we have done here is this PRF distinguisher is playing the dual role. On the left hand side part he is acting as a distinguisher in an instance of the PRF indistinguishability game whereas on the right hand side part of the experiment it is acting as a challenger and creating an instance of the PRG indistinguishability game. Now, let us analyze the success probability of our PRF distinguisher.
I claim that the probability that our PRF distinguisher output B dash equal to 1 given B equal to 1 is same as the probability that our PRG distinguisher outputs big B equal to 1 given the big Y is the output of PRF. the algorithm G. This is because of the following fact, if we are in the case where little b is equal to 1, that means the samples y1 to yt are actually the outputs of the key function fk.
Which further means that the sample Y which is the concatenated of concatenation of this Y samples are actually the output of the algorithm G. So, with whatever probability the PRG distinguisher labels the sample Y to be the outcome of G with the same probability our PRF distinguisher is going to output B dash equal to 1 that is the first case. On the other hand, I claim that the probability that PRF distinguisher outputs B dash equal to 1 given B equal to 0 is same as the probability that our PRG distinguisher outputs big B equal to 1 given that the big Y is the output of TRG. This is because of the fact that if little b is equal to 0. 0 that means, this samples little y1 to little yt are generated or they are the outcomes of a truly random function then it implies that the bigger sample big Y is actually a sample generated by the truly random generator. So, with whatever probability our PRG distinguisher would have labeled a bigger sample Y to be the outcome of the algorithm.
g with the same probability the PRF distinguisher is going to output big B equal to 0. So, that is the second factor. So, what we have established here, we have basically established that distinguishing advantage of our PRF distinguisher is exactly the same as the distinguishing advantage of our PRG distinguisher. That means if the distinguishing advantage of the PRG distinguisher is non-negligible, If, then the distinguishing advantage of our PRF distinguisher is also non-negligible. But this is a contradiction to the fact that we are assuming that the function fk is a keyed secure permutation, is a pseudo random, is a secure pseudo random function because when I say it is a secure pseudo random function that means there exists no polynomial time distinguisher who can significantly distinguish apart that output of that keyed. function from the outcome of an unkept truly random function.
That means the construction G that we have constructed is indeed a pseudo random generator that means no such PRG distinguisher exists and that established a fact that the construction G is a pseudo random generator. So, that brings me to the end of this lecture. Let me summarize what we have discussed in this lecture.
We have discussed, we introduced the concept of pseudo random function, we saw the definition and we introduced various variants of pseudo random functions like pseudo random permutation, strong pseudo random permutation and we had seen how to construct provably secure pseudo random generator from secure pseudo random function. Thank you.