In theoretical computer science and cryptography, a pseudorandom generator (PRG) for 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 itself is typically a short binary string drawn from the uniform distribution.
Hence the construction of pseudorandom generators for the class of Boolean circuits of a given size rests on currently unproven hardness assumptions.
These functions are the statistical tests that the pseudorandom generator will try to fool, and they are usually algorithms.
represents some model of computation or some set of algorithms, and one is interested in designing a pseudorandom generator with small seed length and bias, and such that the output of the generator can be computed by the same sort of algorithm.
usually consists of all circuits of size polynomial in the input and with a single bit output, and one is interested in designing pseudorandom generators that are computable by a polynomial-time algorithm and whose bias is negligible in the circuit size.
The existence of cryptographically secure pseudorandom generators is widely believed.
This is because it has been proven that pseudorandom generators can be constructed from any one-way function which are believed to exist.
For instance, pseudorandom generators provide an efficient analog of one-time pads.
It is well known that in order to encrypt a message m in a way that the cipher text provides no information on the plaintext, the key k used must be random over strings of length |m|.
Perfectly secure encryption is very costly in terms of key length.
Common constructions of stream ciphers are based on pseudorandom generators.
In the 1980s, simulations in physics began to use pseudorandom generators to produce sequences with billions of elements, and by the late 1980s, evidence had developed that a few common generators gave incorrect results in such cases as phase transition properties of the 3D Ising model and shapes of diffusion-limited aggregates.
Then in the 1990s, various idealizations of physics simulations—based on random walks, correlation functions, localization of eigenstates, etc., were used as tests of pseudorandom generators.
Yongge Wang showed that NIST testing is not enough to detect weak pseudorandom generators and developed statistical distance based testing technique LILtest.
Physical computers are deterministic machines, and obtaining true randomness can be a challenge.
If a full derandomization is desired, a completely deterministic simulation proceeds by replacing the random input to the randomized algorithm with the pseudorandom string produced by the pseudorandom generator.
The simulation does this for all possible seeds and averages the output of the various runs of the randomized algorithm in a suitable way.
A fundamental question in computational complexity theory is whether all polynomial time randomized algorithms for decision problems can be deterministically simulated in polynomial time.
The existence of such a simulation would imply that BPP = P. To perform such a simulation, it is sufficient to construct pseudorandom generators against the family F of all circuits of size s(n) whose inputs have length n and output a single bit, where s(n) is an arbitrary polynomial, the seed length of the pseudorandom generator is O(log n) and its bias is ⅓.
In 1991, Noam Nisan and Avi Wigderson provided a candidate pseudorandom generator with these properties.
In 1997 Russell Impagliazzo and Avi Wigderson proved that the construction of Nisan and Wigderson is a pseudorandom generator assuming that there exists a decision problem that can be computed in time 2O(n) on inputs of length n but requires circuits of size 2Ω(n).
While unproven assumption about circuit complexity are needed to prove that the Nisan–Wigderson generator works for time-bounded machines, it is natural to restrict the class of statistical tests further such that we need not rely on such unproven assumptions.
Using a repeated squaring trick known as Savitch's theorem, it is easy to show that every probabilistic log-space computation can be simulated in space
Noam Nisan (1992) showed that this derandomization can actually be achieved with a pseudorandom generator of seed length
Nisan's generator has been used by Saks and Zhou (1999) to show that probabilistic log-space computation can be simulated deterministically in space
When the statistical tests consist of all multivariate linear functions over some finite field
Constant depth circuits that produce a single output bit.
[citation needed] The pseudorandom generators used in cryptography and universal algorithmic derandomization have not been proven to exist, although their existence is widely believed[citation needed].
Such circuit lower bounds cannot be proved in the framework of natural proofs assuming the existence of stronger variants of cryptographic pseudorandom generators.