Pseudorandom generators


In theoretical computer science and cryptography, a Pseudorandom generators (PRG) or pseudorandom number generator (PRNG) is a class of statistical tests is a deterministic procedure that maps a random seed to a longer pseudorandom string such that no statistical test in the class can distinguish between the output of the generator and the uniform distribution.

The random seed is typically a short binary string drawn from the uniform distribution.

Many different classes of statistical tests have been considered in the literature, among them the class of all Boolean circuits of a given size. It is not known whether good pseudorandom generators for this class exist, but it is known that their existence is in a certain sense equivalent to (unproven) circuit lower bounds in computational complexity theory. Hence the construction of pseudorandom generators for the class of Boolean circuits of a given size rests on currently unproven hardness assumptions.

Generally, Pseudorandom generators are not suitable for Cryptography as the output of a Cryptographically secure pseudorandom number generator must guarantee the output is random.

In Cryptography discussions we typically make a Computational Hardness Assumption.

More Information#

There might be more information for this subject on one of the following: