Pseudorandomness generator
From CRYPTUTOR
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.
[edit]
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
such that:
-
for all k. The quantity 
is often called the stretch of G.
-
for all strings x.
-
- Pseudorandomness: The distribution
is a pseudorandom distribution. That is, it is computationally indistinguishable from the uniform distribution on 
-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 
.
[edit]
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.
[edit]
