follows: Gl: {0,1}l→{0,1}l+1 = ƒ(x).B(x), where B is hard-core predicate of ƒ and "." is a concatenation operator. Note, that by the theorem proven above, it is only needed to show the existence of a generator that adds just one pseudorandom bit. Hard-core predicate → PRG First, let's show that if B is a hard-core predicate for ƒ then Gl is indeed pseudorandom. Again, we'll use an argument by contradiction. Assume that Gl is not a pseudorandom generator; that is, there exists circuit C of polynomial size that distinguishes Gl(x) =ƒ(x).B(x) from Ul+1 with advantage ≥ε, where ε is non-negligible. Note, that since ƒ(x) is a permutation, then if x is drawn from uniform distribution, then so if ƒ(x). Therefore, Ul+1 is equivalent to ƒ(x).b, where b is a bit drawn independently from a uniform distribution. Formally, Probx~U [C(G(x))=1] − Probx~U,b~U [C(x.b)=1] ≥ ε Let's construct the following algorithm C''': 1. Given z=f(x) guess bit b 2. Run C on z.b 3. IF C(z.b)=1 4. output b 5. ELSE 6. output 1-b Given the output of ƒ the algorithm first guesses bit b by tossing a random coin, i.e. Prob[b=0] = Prob[b=1] = 0.5. Then, algorithm (circuit) C is run on f(x).b and if the result is 1 then b is outputted, otherwise the inverse of b is returned. Then probability of C guessing B(x) correctly is: Probx~U [C'''(z)=B(x)] = Prob[b=B(x) ∧ C(z.b)=1] + Prob[b≠B(x) ∧ C(z.b)=0] = Prob[b=B(x)]⋅Prob[C(z.b)=1 | b=B(x)] + Prob[b≠B(x)]⋅Prob[C(z.b)=0 | b≠B(x)] = 1/2⋅Prob[C(z.b)=1 | b=B(x)] + 1/2⋅Prob[C(z.b)=0 | b≠B(x)] = (1−1/2)⋅Prob[C(z.b)=1 | b=B(x)] + 1/2⋅(1−Prob[C(z.b)=1 | b≠B(x)]) = 1/2+Probz.b~G(x) [C(z.b)=1] − 1/2⋅(Prob[C(z.b)=1 | b=B(x)]+Prob[C(z.b)=1 | b≠B(x)]) = 1/2+Probz.b~G(x) [C(z.b)=1] − Probz.b~U [C(z.b)=1] ≥ 1/2+εThis implies that circuit C can predict B(x) with probability more than 1/2 + ε, which means that B cannot be a hard-core predicate for ƒ and the hypothesis is contradicted. Q.E.D. OWP → hard-core predicate The outline of the proof is as follows: If ƒ{0,1}n→{0,1}n is a one-way permutation, then so is ƒ'{0,1}2n→{0,1}2n, where ƒ'(x,y)=ƒ(x).y by definition. Then B(x,y)=x⋅y is a hard-core predicate for ƒ', where ⋅ is a vector dot product. To prove that it is indeed hard-core let's assume otherwise, and show a contradiction with the hypothesis of ƒ being one-way. If B is not a hard-core predicate, then there exists a circuit C that predicts it, so Probx,y[C(ƒ(x),y)=x⋅y] ≥ 1/2+ε. That fact can be used to recover x by