We show that given a PRFG (pseudo-random function generator) G which is
$
\frac{1}
{c} -
$
\frac{1}
{c} -
partially secure, the construction
$
\frac{1}
{c} -
$
\frac{1}
{c} -
$
\frac{1}
{c} -
$
\frac{1}
{c} -
produces a strongly secure PRFG, where
g
i
∈
G and
r
i
are strings of random bits. Thus we present the first “natural” construction of a (totally secure) PRFG from a partially
secure PRFG. Using results of Luby and Rackoff, this result also demonstrates how to “naturally” construct a PRPG from partially
secure PRPG.