Building a PRG

From CRYPTUTOR

A pseudorandom generator can be built from any one-way function, although the construction is somewhat involved. A simpler and more efficient construction can be obtained using a one-way permutation.

[edit]

Constructing a PRG with stretch 1

For any one-way permutation $f$ with hard-core predicate $B$ , the following function is a PRG with stretch 1 (i.e, it maps $k$ bits to $k + 1$ bits):

$G(x) = (f(x), B(x))\,$

Since $f$ is length-preserving, it is clear to see that $G$ 's output has one more bit than its input. The fact that it is a PRG is a direct consequence of the following observations:

When $x$ is distributed uniformly on $k$ -bit strings, then $f (x)$ is also distributed uniformly on $k$ -bit strings, since $f$ is a permutation.
Since $B (x)$ is pseudorandom given $f (x)$ , the distribution $(f (x), B (x))$ is indistinguishable from the distribution $(f (x), b)$ , where $b$ is an independently random bit. But this second distribution is the uniform distribution on $(k + 1)$ -bit strings.

This construction can yield a PRG with larger stretch by using a longer hard-core function instead of a single hard-core bit, if one is available for the one-way permutation.

[edit]

Constructing a PRG with arbitrary stretch

A PRG with arbitrary (polynomial) stretch can also be built from a PRG with smaller stretch (even one-bit). Let $G$ be a PRG with stretch 1, and interpret its output as having two parts $G (x) = (G 1 (x), G 2 (x))$ , where $| G 1 (x) | = | x |$ . Using a hybrid argument, we can show that the following function is also a PRG with $t$ output bits, where $t$ is any polynomial in the security parameter:

$G^*(x) = \Big( G_2(x), G_2( G_1(x)), G_2( G_1^{(2)}(x)), \ldots, G_2( G_1^{(t-1)}(x) ) \Big)$ .

Here, the notation $f (i)$ denotes the function $f$ composed with itself $i$ times.

For a one-way permutation $f$ , applying the Goldreich-Levin predicate and these two constructions yields the PRG:

$G(x,r) = \Big( \langle x, r \rangle, \langle f(x), r \rangle, \langle f^{(2)}(x), r\rangle, \ldots, \langle f^{(t-1)}(x), r \rangle \Big)$ .

[edit]

References

Johan Håstad, Russell Impagliazzo, Leonid Levin , Michael Luby, A pseudorandom generator from any one-way function, SIAM J. Comp., v28, n4, August 1999, pp1364-1396.

Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Building_a_PRG"

Category: Constructions