Pseudo-random generators under uniform assumptions
Johan Håstad · 1990
We prove that given a function f which is oneway in the uniform model (i.e.cannot be inverted except on a vanishing fraction of the inputs by a probabilistic polynomial time Turing machine) it is possible to construct a pseudo random bit-generator which passes all probabilistic polynomial time statistical tests.