Pseudorandomness generator

From CRYPTUTOR

Jump to: navigation, search

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.

See also

Personal tools