A pseudorandomness generator (PRG), or pseudorandom generator, is a function that, when given a short random string as input, outputs a longer string which "appears random" to all efficient computations.
A function G is a pseudorandomness generator if it has the following properties:
- Efficiency: G is computable in (deterministic) polynomial time in the input length.
- Regular stretch: There is a polynomial such that:
- for all k. The quantity is often called the stretch of G.
- for all strings x.
- Pseudorandomness: The distribution is a pseudorandom distribution. That is, it is computationally indistinguishable from the uniform distribution on -bit strings. Here k is the security parameter of the PRG.
Note that since pseudorandomness is formally defined for an ensemble of distributions, the above definition implicitly refers to the ensemble .
PRGs exist if and only if one-way functions exist. It is easy to see that a PRG can be viewed as a one-way function, whereas the construction of a PRG from a one-way function is quite involved. However, if the one-way function is a one-way permutation, a PRG can be constructed much more efficiently.