# Pseudorandomness generator

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.

## Definition

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 $\ell$ such that:
• $\ell(k) > k$ for all k. The quantity $\ell(k)-k$ is often called the stretch of G.
• $|G(x)| = \ell(|x|)$ for all strings x.
• Pseudorandomness: The distribution $\mathcal{G}_k = \{G(s)\}_{s\gets\{0,1\}^k}$ is a pseudorandom distribution. That is, it is computationally indistinguishable from the uniform distribution on $\ell(k)$-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 $\{\mathcal{G}_k\}_k\,$.

## Existence

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.