Pseudorandom generator

From Wikipedia, the free encyclopedia

Let G be a deterministic polynomial time function from N^<ω to N^<ω with stretch function

l:N → N,

so that if x has length n then G(x) has length l(n). Then let G_n be the distribution on strings of length l(n) defined by the output of G on a randomly selected string of length n selected by the uniform distribution.

Then we say G is a pseudorandom generator if

{G_n}_{n ∈ N}

is pseudorandom.

In effect, G translates a random input of length n to a pseudorandom output of length l(n). Assuming

l(n) > n,

this expands a random sequence (and can be applied multiple times, since G_n can be replaced by the distribution of G(G(x))).

Oftentimes, we are concerned not with the behavior of G on all strings, but only on strings of some prescribed length. This case allows a slightly easier definition:

A function $G_l: \left \{0,1\right\}^n \rightarrow \left \{0,1\right\}^m\,$ with $n < m\,$ is a pseudorandom generator if

$G_l\,$ can be computed in $poly(n)\,$ time, and
$G_l(x)\,$ is pseudorandom.

It is an open problem whether or not pseudorandom generators exist. It is known that if one-way functions or hard-core predicates exist, then pseudorandom generators exist. It is also known that if

l(n) > n,

there is some other pseudorandom generator with

l(n) > p(n)

for any polynomial, p(n). This follows from the following theorem:

Theorem: If there is a pseudorandom generator

$G_l: \left \{0,1\right\}^{n} \rightarrow \left \{0,1\right\}^{n+1}\,$