So intuitively, a weak OWF is a function that is sometimes hard to invert for every efficient adversary; whereas a OWF is almost always hard to invert for every efficient adversary. The next theorem is a famous result of Yao which shows how to use a weak OWF to build a OWF. Theorem (Yao's Hardness Amplification). Suppose f:{0,1}n{0,1}m is an -weak OWF for a non-negligible parameter >0, and let k=2n/. Then the k-wise product function F(x1,,xk)=(f(x1),,f(xk)) is a OWF from {0,1}nk{0,1}mk. Intuition. The intuition behind the proof is that since an -fraction of the x{0,1}n are such that y=f(x) is hard to invert, at least one of these hard y will appear in a random (y1,,yk) with very high probability. Proof. Suppose A wins the OWF game of F with non-negligible probability 2>0. We construct an efficient adversary B which plays the OWF game of f and uses A to win with probability greater than 1. This breaks the assumption that f is an -weak OWF, B plays against a challenger C as follows: 1. B receives y{0,1}m from C. 2. B performs the following steps k2n/ times: B chooses (x1,,xk){0,1}nk and sets (y1,,yk)=F(x1,,xk){0,1}mk; then B chooses i[k] and overwrites yi with y; B sends (y1,,yk) to A - if A returns (x1,,xk){0,1}nk such that F(x1,,xk)=(y1,,yk) then B outputs xi and halts; otherwise B continues. First we set some shorthand. Let Dy be the distribution specified in the first bullet of Step 2. Specifically, Dy draws (x1,,xk){0,1}nk, sets (y1,,yk)=F(x1,,xk){0,1}mk; then chooses i[k] and overwrites yi with y, outputting (y1,,yk). Also, let us say that A(y1,,yk) wins if A returns (x1,,xk){0,1}nk such that F(x1,,xk)=(y1,,yk). Finally, we say that y{0,1}m is bad, and write yBAD, if PrDy[A(y1,,yk) wins ]/k. Problem 7. Complete the proof that Pr[B inverts y]>1 by doing the following. (a) Prove that if y/BAD then Pr[B inverts y]=12(n). Deduce that it suffices to show that Pry{0,1}m[y/BAD]>1/2. (b) Prove that Pr(y1,,yk){0,1}m+k[A(y1,,yk) wins \& i st yiBAD]. Deduce that Pry{0,1}m[y/BAD]k. (c) Complete the proof by showing that if Pry{0,1)m[y/BAD]1/2, then 2n, a contradiction since is non-negligible