Foundations of CryptographyProf. Dr. Ashish Choudhury(Former) Infosys Foundation Career Development Chair ProfessorInternational Institute of Information Technology-BangaloreLecture-11Provably Secure Instantiation of PRGHello everyone, welcome to lecture 10, the plan for this lecture is as follows.(Refer Slide Time: 00:33)In this lecture, we will discuss about the theoretical instantiation of pseudo random generators for which we will introduce the concept of one way function. And after introducing the concept of one way function, we will see how to design PRG with one bit expansion and then we will see how to design PRG with arbitrary expansion.(Refer Slide Time: 00:53)So, the question that we want to answer is do PRG's exist. So, recall that in the last lecture, we had seen that if you have a pseudo random generator, then using that you can design stream ciphers, which allow you to encrypt long messages using short key. So, the question that we not want to answer is do such PRG's exist or not. And to recall, a PRG is a deterministic algorithm which takes a seed or an input of size l bits which we denote by s.And it expands its output and it produces an output which is significantly larger than the input and the security of PRG means that the output of this deterministic algorithm G should be computationally indistinguishable from the output of a truly random generator of the same size,right. So, it turns out that there are 2 ways to design PRGs. The first way is provably secure constructions of PRGs from one way function.And when I say provably secure I mean that the constructions that we give using one wayfunction for that we give a proof that indeed the construction is PRG in the sense that they are exist no polynomial time distinguisher which can distinguish outcome of the resultant PRG from the corresponding true random number generator. Unfortunately, we cannot use them in practice because the amount of computation that are involved in the resultant construction are of order of several magnitude.On the other hand, there are practical instantiations of pseudo random generators, but unfortunately they are not provably secure in the sense we believe that they are heuristically secure because ever since their construction, no weakness have been reported for such pseudo random generators, but the advantage of search heuristically secure pseudo random generators are they are super fast.So, that is why in practice we prefer to use such an instantiation. So, the focus for this lecture will be the provably secure construction instantiations of pseudo random generators from one way function. In the next picture we will discuss about the practical instantiations of pseudo random generator.(Refer Slide Time: 03:00)So let me introduce the concept of one way function or OWF in short, so it is a function from the domain of bit string to the codomain of bit string denoted by f. And, informally, it is a function which is easy to compute, but difficult to invert. More specifically, there are 2 requirements of this function. The first requirement is that it should be easy to compute. Namely, if you are given any input x, computing the value of the function on that input x should be polynomial time,polynomial in the size of the input x.The second requirement, which is the interesting property from this one way function is the hard to invert property namely, the requirement is that if you are given a random sample y, from the codomain, then finding the preimage or one of the preimages of this given y in polynomial time should be difficult except with a negligible probability. And this property is modeled by an experiment.(Refer Slide Time: 03:58)So in this experiment, we are given the description of a publicly known function f. And the name of the experiment is Invert, played with respect to a polynomial time algorithm whose goal is to invert the output of a function on a random sample with respect to the function f, and n is the security parameter here. So in this experiment, we have 2 entities, namely the verifier and adversary. So the rules of the experiment are as follows.The verifier here picks a random x from the domain which is an arbitrary bit string and computes the value of the function on that input x, which is given as a challenge for the adversary. So the adversary is not aware of the input x, it only sees the output of the function on the input x, namely y and the goal or the challenge for the adversary is to invert to sample y namely to find at least one of the preimages of this given value y.So it submits his response namely x’ and we say that the function f has one wayness property, iffor any polynomial time algorithm A participating in this experiment there exist a negligible function say negl(n) such that the probability is that the probability that adversary is indeed able to output x’, which is actually a preimage of the given y is upper bounded by a negligible function.That means we require that no polynomial time algorithm should be able to invert this random yexcept with a negligible probability. So, in this definition the requirement is that the success probability of that adversary to invert the random y should be upper bounded by a negligible function not by 0, because they are always exist a guessing strategy by the adversary namely adversary can simply guess a random x’.And there always exists a nonzero probability that the guessed x’ indeed turns out to be one of the preimages of the given y, that is why in the definition, we do not require that we do not enforce that the condition that it A should be able to invert the sample y should be upper bounded by 0, we give the leverage and the upper bound the success probability of the adversary by a negligible probability.Also notice that it is not required by the adversary to find the exact x, because the function can be a many to one function. So, it could be possible that the given y which is thrown as a challenge to the adversary has several preimages. The goal of the adversary is to find one of those preimages right.(Refer Slide Time: 06:25)So let us see an example to make our understanding clear, consider the function f which is a 2input function and the function is from the set of natural numbers to the set of natural numbers. So, the function takes 2 inputs from the set of natural numbers and output of the function is basically the product of the 2 inputs. Now, the question is this function a one way function that means if someone gives you the value of x dot y, your x and y are not known to you. Will you be able to invert or find one of the preimages namely a pair of x, y such that whose product is equal to the given product in polynomial amount of time, and it turns out that they are exist, indeed, there indeed exists a simple algorithm to find one of the preimages and the algorithm is as follows. So you are given a random sample z, which is basically the output of the function on a pair of unknown inputs x, y. And your inversion algorithm is as follows.The algorithm checks whether z is even or not, if z is even then the algorithm outputs the following pair of preimages, the first preimage x’ is 2 and a second preimage y’ is z/2. So, that is a pair of inputs which would actually give you the output z, whereas if the sample z which is given to you is odd then you just randomly output x’, y’ on the set of natural numbers.So, it turns out that the success probability of this inversion algorithm is actually 3 by 4. Because since the function is a 2 input function, the possible values of x, y could be (odd, odd), (odd, even), (even, odd) and (even, even). And it turns out that out of this 4 combinations, for 3 of the combinations, your z will always be even. And if z is even and indeed the inversion algorithm that is used here, namely outputting 2 and z/2 as the possible preimage is a successful algorithm.The only problematic case is when the sample x, y is actually an odd, odd pair in which your z may not be z will not be an even number, in which case you might be outputting an incorrect x’, y’. So, it turns out that in three fourths of the instances, the adversary or this algorithm will be able to successfully invert the given value z. Hence, this function f is not a one way function because the success probability of inversion is 3/4, which is a significant amount of probabilityright.On the other hand, let us slightly modify this function. So, my function f(x, y) is still the product of x and y but instead of saying that x and y are random natural numbers, put the restriction here that x and y are random prime numbers of roughly same size. And it turns out that this function is now conjectured to be a one way function if x and y are large prime numbers say of order 1024 bits.So I stress here that it is just conjectured that this function f(x, y) where x and y are arbitrary large prime numbers is a one way function because till now, we do not have any polynomial time algorithm to invert this function. It is not proved formally that indeed this function is a one way function. And later on, when we will be discussing about the public key cryptography, and we will be discussing number theory where we will see several such candidate one way functions, which are conjecture on several hard so called number theoretic hard problems.So for the moment, we will believe that this function f(x, y) where x and y are arbitrary large numbers and the function is a product of x and y is a candidate one way function.(Refer Slide Time: 10:02)So now let us define another related concept namely that of one way permutation or OWP. And basically a one way permutation is a one way function, which also happens to be a bijection. Namely, the mapping is now a one-one onto mapping. That means each y from the codomain will have a unique preimage. And the requirement or the hard to invert part for one way permutation is that if you are given a random y from the codomain, the challenge for the adversary is to find out a unique preimage x which would have actually given that y in polynomial amount of time.So the difference here is for the case of one way function, the random challenge y could have several preimages and your goal was to find one of those preimages. In the case of one way permutation, random sample y which is given to you will have only a unique preimage. And your goal is to find that unique preimage and polynomial amount of time. Notice that both in the case of one way function as well as in one way permutation, we put the restriction that the inversion algorithm should take polynomial amount of time.Because if we do not put any restriction on the amount of time, which is given to the inversion algorithm, then there are always exists a brute force algorithm namely, the algorithm can try over all possible candidate x from the set of candidate x and definitely it will hit upon one x which will be give the random y which is thrown as the challenge, but the running time of this brute force algorithm will be exponentially or it will be proportional to the size of the domain.And the size of the domain is exponentially large than the inversion algorithms running time is also exponential. So, that is why in the experiment, where we model the inversion part both for the one way function as well as one way permutation we put the restriction that running time of that adversary should be polynomial time.(Refer Slide Time: 11:52)So, now let us discuss another interesting related concept namely that of hard-core predicate which will be useful when we will design our candidate pseudo random generator from one way function and the motivation for this hard-core predicate is as follows. So imagine you are given a function f, which is a one way function or a one way permutation. And if you are given the value of function on a random input x, then definitely computing the entire x in polynomial amount of time is difficult.Because that is what is the property of a one way function or one way permutation, but that does not necessarily mean that you cannot compute anything about x in polynomial time, there might be some information about x, which you can compute from the value of f(x) in polynomial amount of time. So basically hard-core predicate models what can be computed about x from a f(x) in polynomial amount of time and what cannot be computed.To make my point more clear, consider the function ?:{0,1} ∗ → {0,1} ∗ and say this function f is a one way function and using this function we design another function g, which is now a 2input function and the function g on the input pair x1, x2 is defined as the output consisting of x1as it is, and the second part of the output of this function g is actually the value of the function f on the second part of the input, namely x2 , ?(x1, x2) ∶= (x1, ?(x2)).That is the way I am defining my function g. And my claim is that if the size of x1 and x2 are roughly same, namely some polynomial function in the security parameter, then if the function f with which we start is a one way function, then the constructed function g, which is constructed like this is also a one way function right. So basically, the idea here is that if g is not a one way function, that means if someone gives you the value of g(x1, x2), and you can actually find out x1, x2 in polynomial amount of time. Then intuitively using that algorithm, you can also compute the value of x2 using just given f(x2), so we can formally established his fact using a reduction argument. So I am not going into the reduction argument. But basically the idea here is that if f is one way function and the function g, which is a 2 input function constructed like this is also a one way function provided both x1 and x2 are roughly same size.Now, if you see the function g, it turns out that even though it is a one way function, by seeing the output of this function g on a random pair of input, you actually end up learning the one half of the input, right. Because the first half of the output is actually the first half of the input as it is.In that sense, even though this function g is a one way function, it is not the case that if I give you the value of this function g on an arbitrary pair of input, you cannot compute back the entire input in polynomial amount of time.There is something which you can compute, there is something which you cannot compute in polynomial amount of time. So this notion of hard-core predicate precisely models, what is polynomial time computable from the value of the function f(x) on random input x, right.(Refer Slide Time: 15:01)So let us see the formal definition of this hard-core predicate. So, imagine you are given a function from a domain of bit string to the codomain of bit string and I stress that the function may not be a one way function it could be a normal function. So, we are given a function f and corresponding to the function f we define another function hc which is a Boolean function that means, it takes an arbitrary binary string as an input and it produces a Boolean output 0, 1.And then we see that this function hc associated with a function f is a hard-core predicate if the following 2 conditions hold. So, the first condition is that if you are given random input text and computing the value of this function, hard-core predicate namely hc of f should be polynomial time computable that means you should be able to compute the value of hc of x in polynomial time polynomial in the size of the input x.The second interesting property which actually makes hard-core predicate very interesting is the following that if you are given the value of f(x) for a randomly chosen x, then it is not possible to compute the value of hc(x) with probability significantly better than half in polynomial amount of time. That means the challenge here is that if I give you f(x) and I do not to tell you the value of x, where x is randomly chosen, then even after learning f(x), we should not be able to compute the value of the function hc of x in polynomial amount of time, except with probability, negligible better than half. If that is the case, then we say that the function hc(x), hc is actuallythe hard-core predicate associated with the function f. So this requirement of inability to compute the value of hc(x) with probability significantly better than half by a polynomial time algorithm is modeled by an experiment which we call as hard-core experiment.And now this experiment is designed with respect to a function f which is publicly known, which is a candidate function which could be a candidate one way function or one way permutation or it could just be a function and associated with the function f we have a candidate hard-core predicate, which is a Boolean function and experiment involves 2 entities. So the rule of the experiment is as follows.The verifier here picks a random x from the domain, computes the value of the function on that input x. And the corresponding output y is given as a challenge to the adversary. And the goal of the adversary or the challenge for the adversary is after seeing the value of y it has to compute the value of hc(x) without knowing the x. So, say hc(x) is going to be a bit it submits the adversary outputs a bit which could be either 0 or 1.And we say that adversary has won the game if actually b = hc(x). So, that means, we say that the function hc associated with the function f is a hard-core predicate, if for any polynomial time algorithm participating in this experiment, the probability that adversary outputs b where b is actually equal to hc of x is upper bounded by half plus some negligible probability or negligible function in the security parameter.If that is the case, then we say that the function hc is a hard-core predicate associated with the function f. So, notice there is in definition, we bounded success probability of the adversary to be half plus negligible, we do not require that the success probability of the adversary should be 0, because there is always a guessing strategy or guessing adversary who can just guess a bit and there always exist a probability of 1/2 that the guest is indeed the value of hc(x) correctly.Apart from that we are also willing to give that adversary an extra negligible advantage and successfully outputting the hard-core predicate, because we are in a computationally secure world right. So that is the definition of hard-core predicate.(Refer Slide Time: 18:53)So now the question is, if we are given a candidate one way function or one way permutationdoes there exist an associated hard-core predicate or not. And it turns out that interestingly the answer is yes. And that is because of a very fundamental theorem and cryptography, which is also called as Goldreich-Levin theorem. And Goldreich-Levin theorem basically shows you how to construct a hard-core predicate associated with any given one way function, or any given one way permutation.So we will not be going into the proof of the Goldreich-Levin theorem, we will just roughly see the theorem statement and intuition of the security. So the theorem statement is as follows. So imagine you are given a candidate one way function say f or a candidate one way permutation. Now using this candidate function f, we construct a 2 input function g, and the construction of gis as follows. So it passes the input as x, r.And the output of g is defined as follows. So we evaluate the function f on the first part of the input of g. That constitutes the first part of the output of g, and the second part of the input of g is copied as it is in the output of the g. And here the size of the 2 inputs of the g, namely x and r are of same order. So that is the way we define our function g. Now we can prove formally that if the function f with which we start with is a one way function or one way permutation then the function g which we have constructed like (f(x), r) is also a one way function or one way permutation respectively.And the proof is by a reduction argument. Namely, we can show that if you have a polynomial time algorithm to invert the output of the function g that you have constructed on a random pair of input x, r. That means if you have an algorithm who without knowing the random pair of input x, r, but just seeing the value of g(x, r) can give you back x, r in polynomial amount of time. Then using the same inversion algorithm we can construct another polynomial time algorithm, which when given the value of f(x) on a random x without knowing the value of x can actually give you back the value of x, which is a contradiction to the fact that f is a one way function or a one way permutation.So that is a straightforward reduction argument using which we can prove this theorem. So, now we will focus on the function g. And what Goldreich-Levin theorem shows you basically that if this function g is a one way function, then we can associate a corresponding hard-core predicte with this function g. Namely, the hard-core predicate is the Boolean function, which basically takes random linear combination of the bits of the input x, right.So what we consider here is that your r is interpreted as a bit string of length n, and your x is also considered as a bit string of length n, these are the 2 inputs for the function g, and associated hard-core predicate, which is associated with the function g is denoted by the function gl. And the function gl is basically random linear combination of the bits of the x, where the combiners are defined by the bit representation of the input r.And what the Goldreich-Levin theorem claims basically that this function gl(x, r) is the hard?core predicate associated with the function g. That means, if someone gives you the value of the function g(x, r), for a random x and r, then, except with probability half plus negligible no polynomial time algorithm can compute the value of gl(x, r). And the intuition behind this the proof of the Goldreich-Levin theorem is that even though you are given f(x) since you do not know the value of x, basically the challenge for computing the Goldreich gl, the output of the function gl(x, r) is basically to compute the XOR of the random subsets of the bit of x but since the adversary will not know the exact bits of the x, it will be difficult for the adversary tocompute that XOR of the random subsets of the bits of x. That is basically the intuition of this theorem. However, it turns out that the proof of this theorem is indeed challenging and involved.So, the students who are interested to go through the proof of this Goldreich-Levin theorem they can refer to the book by Katz and Lindel, where they have given the detailed proof, but for our discussion, we will assume that the function gl(x, r) is associated hard-core predicate which is associated with our candidate one way function g(x, r) right.(Refer Slide Time: 23:36)So, assuming we have now a hard-core predicate, and we have a candidate one way permutation let us see how we can construct PRG with minimal expansion, and what we mean by minimal expansion is that we will assume that we are given a candidate one way permutations from the set of n bit strings to the set of n bit strings. That means the function f takes an input which is a string of length n and it produces output which is also a string of length n.And it is a one way permutation. And associated with the function f, we have a hard-corepredicate. Now given this we will construct a pseudo random generator where the construction of the pseudo random generator is as follows. Namely, we can prove that no polynomial time distinguisher exists for our construction, otherwise, it reduces to the security of the underlying one way function and the hard-corepredicate. I hope you enjoyed this lecture. Thank you.