Problem 3. Complete both of the following points. (a) Prove that every PRG is also a OWF. Specifically, suppose G:{0,1}n{0,1}m for m>n is a PRG, prove G is also a OWF. (b) Prove now that not every OWF with m>n is a PRG. Specifically, let f:{0,1}n{0,1}m with m>n be a OWF. Use f to build another function f:{0,1}n{0,1}m+1 which is a OWF but which is not a PRG. Prove that f is a OWF (assuming f is) but is not a PRG. (c) Suppose (Gen, Enc, Dec) is a PKE scheme. Recall that we normally model the key generation procedure Gen() as a randomized procedure which takes no input and which outputs a key pair (pk, sk). Let us instead for this problem be explicit about the randomness used by Gen. So we will think of Gen() as a deterministic function which takes as input a random string r{0,1}k and outputs (pk,sk). Prove that when modeled this way, Gen is a OWF. Remark: This proves that for PKE to exist, OWF must exist. It is possible to argue along similar lines and use the encryption procedure in any encryption scheme (PKE or SKE) to build a OWF. Thus, even for SKE to exist, OWF must exist