much smaller than that of its inverse. Formally: A function ƒ: {0,1}n → {0,1}n is (S,ε) one-way if for any circuit C of size ≤ S, Prob[ƒ(C(ƒ(x))) = ƒ(x)] ≤ ε. Moreover, ƒ is a one-way function if ƒ can be computed in polynomial time ƒ is (poly(n), 1/poly(n)) one-way Hard-core predicate Function B: {0,1}n → {0,1} is a hard-core predicate for function ƒ if B can be computed in polynomial time for any polynomial size circuit C and any non-negligible ε = 1/poly(n), Probx~U [C(ƒ(x)) = B(x)] ≤ 1/2+ε In other words, it is hard to predict B(x) from function ƒ(x). Proof Here an outline of the proof is given. Please see references for detailed proofs. PRG → OWF Consider a pseudorandom generator Gl: {0,1}l → {0,1}2l. Let's create the following one-way function ƒ: {0,1}n → {0,1}n that uses the first half of the output of Gl as its output. Formally, ƒ(x,y) → Gl(x) A key observation that justifies such selection, is that the image of the function is of size 2n and is a negligible fraction of the pre-image universe of size 22n. To prove that ƒ is indeed a one-way function let's construct an argument by contradiction. Assume there exists a circuit C that inverts ƒ with advantage ε: Prob[ƒ(C(ƒ(x,y))) = ƒ(x,y)] > ε Then we can create the following algorithm that will distinguish Gl from uniform, which contradicts the hypothesis. The algorithm would take an input of 2n bits z and compute (x,y) = C(z). If Gl(x) = z the algorithm would accept, otherwise it rejects. Now, if z is drawn from uniform distribution, the probability that the above algorithm accepts is ≤ 1/2l, since the size of image is 1/2l of the size of the pre-image. However, if z was drawn from the output of Gl then the probability of acceptance is > ε by assumption of the existence of circuit C. Therefore, the advantage that circuit C has in distinguishing between the uniform U and output of Gl is > ε − 1/2l, which is non-negligible and thus contradicts our assumption of Gl being a pseudorandom generator. Q.E.D. OWF → PRG For this case we prove a weaker version of the theorem: One-way permutation → pseudorandom generator A one-way permutation is a one-way function that is also a permutation of the input bits. A pseudorandom generator can be constructed from one-way permutation ƒ as