between Hi and Hi+1 by at least ε / m. Note, that since m are polynomial in l, then ε / m is also polynomial in l and is still a non-negligible advantage. Now, assume we are given l+1 bits that are either output of Gl or a drawn from uniform distribution. Let's reuse the approach of building large pseudorandom generators out of instances of Gl and construct a string of pseudorandom bits of length m−i−1 in the same way the G'l was constructed above using the first l given bits as the seed. Then, let's create a string consisting of i bits drawn from uniform, concatenated with the last one of the given bits, followed by the created m−i−1 bits. The resulting output is either Hi or Hi+1, since the i+1 bit is either drawn from uniform or from Gl. Since by assumption we can distinguish between Hi and Hi+1 with non-negligible advantage, then we can distinguish between U and Gl, which implies that Gl is not a pseudorandom generator, which is a contradiction to the hypothesis. Q.E.D. Now, let's illustrate that if exists, the circuit for distinguishing between Gl and Ul+1 does not have to toss random coins. As we showed above, if exists a circuit C for distinguishing between G'l and Um, where m = poly(l), then exists a circuit C' for distinguishing between Gl and Ul+1 that uses i random bits. For this circuit C' : | Probu, s [C' (u1,...,ui,Gl(s)) = 1 ] − Probu, y [C' (u1,>,...,ui,y) = 1] | ≥ ε / m, where u is a string of i uniformly random bits, s is a string of l uniformly random bits, and y is a string of l+1 uniformly random bits. Then, Probu[ | Probs [C' (u1,...,ui,Gl(s)) = 1] - Proby [C' (u1,...,ui,y) = 1] | ] ≥ ε / m; Which means, there exists some fixed string u of i bits that can be used as an "advice" to circuit C' for distinguishing between Gl and Ul+1. Existence of pseudorandom generators The existence of pseudorandom generators is related to the existence of one-way functions and hard-core predicates. Formally, pseudorandom generators exist if and only if one-way functions exist, or PRG ↔ OWF Definitions One-way functions Intuitively one-way functions are functions that are easy to compute and hard to invert. In other words, the complexity (or circuit size) of the function is