Lemma (Goldreich-Levin, Prediction Implies Inversion). Let f:{0,1}n{0,1}m be a function. If no efficient adversary can win the inversion game of f with non-negligible probability (i.e., if f is a OWF ), then no efficient adversary can win the inner product prediction game of f with probability 1/2+ for a non-negligible >0. Proof. Assume for contradiction that an efficient adversary A can solve the inner product prediction challenge for f with probability 1/2+ for non-negligible >0. Consider the adversary B who attempts the inversion challenge for f as follows: 1. Input and Random Choices: B receives input y=f(x){0,1}m for a random x {0,1}n, and chooses random strings r1,,rk{0,1}n and random bits g1,,gk{0,1} for a parameter k=2log(1/)+log(n)+1. For a subset S{1,,k} let rS=iSri {0,1}n and gS=iSgi{0,1}. 2. Conduct a Poll: For all t=1,,n and S{1,,k}, let x^S,t=A(f(x),rSet)gS, where et is the t-th "unit" string (i.e., the t th bit of et is 1 , all other bits are 0 ); then let 3. Output: Let x^=x^1x^n; if f(x^)=f(x), then output x^; if f(x^)=f(x) then halt giving no output. Problem 8. Complete the following outline to prove that if A completes the inner product prediction challenge for f with probability 1/2+, then B completes the inversion challenge for f with probability at least 2/4n. (a) Assume that Prx,r{0,1}n[A(f(x),r)=x,r]=1/2+. Let us say that x is good if Prr{0,1}n[A(f(x),r)=x,r]1/2+/2. Prove that with probability at least /2, the x{0,1}n chosen by the inner product prediction challenge (i.e., the x{0,1}n which is behind the y=f(x){0,1}m sent to B in Step 1) is good. (b) Consider now the bits g1,,gk{0,1} chosen by B during Step 1. Prove that with probability 2k=2/2n,gS=rS,x holds for all S{1,,k}. In this case, we say that the bits g1,,gk are correct. (c) Assume g1,,gk{0,1} are correct. Prove that A(f(x),rSet)=rSet,x occurs if and only if x^S,t=xt, the t-th bit of x. For t=1,,n and S{1,,k}, define the indicator random variable XS,t (over the random experiment r1,,rk{0,1}n ) which is 1 if A(f(x),rSet)=rSet,x and 0 if not. Prove that for all t=1,,n and non-empty S{1,,k},E[XS,t]1/2+. (d) Prove that for all t[n] and non-empty, distinct S,T{1,k},E[XS,tXT,t]=E[XS,t]. E[XT,t]. Deduce that for all t=1,,n : Prr1,,rk{0,1}n[#{non-emptyS{1,,k}:x^S,t=xt}21(2k1)]2k122n1. (e) Put everything together to conclude that Pr[B(f(x))=x]2/4n