In computational complexity theory and cryptography, the existence of pseudorandom generators is related to the existence of one-way functions through a number of theorems, collectively referred to as the pseudorandom generator theorem. Introduction Pseudorandomness A distribution is considered pseudorandom if no efficient computation can distinguish it from the true uniform distribution by a non-negligible advantage. Formally, a family of distributions Dn is pseudorandom if for any polynomial size circuit C, and any ε inversely polynomial in n |Probx∈U [C(x)=1] − Probx∈D [C(x)=1] | ≤ ε. Pseudorandom generators A function Gl: {0,1}l → {0,1}m, where l < m is a pseudorandom generator if: Gl can be computed in time polynomial in l Gl(x) is pseudorandom, when x is uniformly random. One additional pseudorandom bit implies polynomially more pseudorandom bits It can be shown that if there is a pseudorandom generator Gl: {0,1}l → {0,1}l+1, i.e. a generator that adds only one pseudorandom bit, then for any m = poly(l), there is a pseudorandom generator G'l: {0,1}l → {0,1}m. The idea of the proof is as follows: first s bits from uniform distribution Ul are picked and used as the seed to the first instance of Gl, which is known to be a pseudorandom generator. Next, the output of the first instance of Gl is divided into two parts: first l bits are fed into the second instance of Gl as a seed, while the last bit becomes the first bit of the output. Repeating this process for m times yields an output of m pseudorandom bits. It can be shown that such G'l, that consists of m instances of Gl, is indeed a pseudorandom generator by using a hybrid approach and proof by contradiction as follows: Consider m+1 intermediate distributions Hi: 0 ≤ i ≤ m, where first i bits are chosen from the uniform distribution, and last m − i bits are chosen from the output of G'l. Thus, H0 is the full output of G'l and Hm is a true uniform distribution Um. Therefore, distributions Hi and Hi+1 will be different in only one bit (bit number i+1). Now, assume that G'l is not a pseudorandom distribution; that is, there exists some circuit C that can distinguish between G'l and Um with an advantage ε = 1/poly(l). In other words, this circuit can distinguish between H0 and Hm. Therefore, there exists such i that the circuit C can distinguish