A pseudorandom generator allows us to take a small amount of uniformly sampled bits, and “amplify” them into a larger amount of uniform-looking bits. A PRG must run in polynomial time, so the length o...A pseudorandom generator allows us to take a small amount of uniformly sampled bits, and “amplify” them into a larger amount of uniform-looking bits. A PRG must run in polynomial time, so the length of its pseudorandom output can only be polynomial in the security parameter. But what if we wanted even more pseudorandom output? Is it possible to take λ uniformly sampled bits and generate 2λ pseudorandom bits?
