Pseudorandom generator

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 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.

Contents 1 Definition 2 Pseudorandom generators in cryptography 2.1 Applications 3 Pseudorandom generators and derandomization 3.1 Pseudorandom generators for polynomial time 3.2 Pseudorandom generators for logarithmic space 4 Constructions of pseudorandom generators 5 Limitations on the provability of pseudorandom generators 6 References

Definition

Let F_n = {f: {0, 1}ⁿ → T} be a class of functions. A function G: {0, 1}^s → {0, 1}ⁿ, where s < n, is a pseudorandom generator against F_n with bias ε if for every f in F_n, the statistical distance between the distributions f(G(X)), where X is sampled from the uniform distribution on {0, 1}^s, and f(Y), where Y is sampled from the uniform distribution on {0, 1}ⁿ, is at most ε.
The quantity s is called the seed length and the quantity n - s is called the stretch of the pseudorandom generator. Functions from the class F_n are sometimes called adversaries.
A pseudorandom generator against a family of adversaries F = {F_n} with bias ε(n) is a collection of pseudorandom generators {G_n: {0, 1}^s(n) → {0, 1}ⁿ}, where G_n is a pseudorandom generator against F_n with bias ε(n).
In most applications, the family F represents some model of computation, and one is interested in desigining a pseudorandom generator that is computable in the same or some closely related model.

Pseudorandom generators in cryptography

Main article: Cryptographically secure pseudorandom number generator

In cryptography, the class F usually consists of all circuit families of size polynomial in the input 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. These pseudorandom generators are sometimes called cryptographically secure pseudorandom generators (CSPRGs).
It is not known if cryptographic pseudorandom generators exist. Their existence would imply that P ≠ NP. However, the existence of cryptographic pseudorandom generators is widely believed to be true^{[citation needed]} and their existence is necessary for many applications in cryptography.
The existence of cryptographic pseudorandom generators is equivalent to the existence of one-way functions (see Pseudorandom generator theorem).

Applications

Pseudorandom generators have numerous applications in cryptography. 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. Key length can be significantly reduced using a pseudorandom generator if perfect security is replaced by semantic security. Common constructions of stream ciphers are based on pseudorandom generators.
Pseudorandom generators may also be used to construct symmetric key cryptosystems, where a large number of messages can be safely encrypted under the same key. Such a construction can be based on a generalization of pseudorandom generators, called pseudorandom functions.

Pseudorandom generators and derandomization

Pseudorandom generators can be used for efficient deterministic simulations of randomized algorithms. In such applications, the class F describes the computations that one wants to simulate, and one is interested in designing an "efficiently computable" pseudorandom generator against F whose seed length is as short as possible. The deterministic simulation proceeds by replacing the random input to the randomized algorithm by the output of the pseudorandom generator and averaging the outputs produced by the algorithm as the pseudorandom generator is computed over all possible seeds.

Pseudorandom generators for polynomial time

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 2^O(n) on inputs of length n but requires circuits of size 2^Ω(n).

Pseudorandom generators for logarithmic space

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. One class for which this has been done is the class of machines whose work space is bounded by . 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 that fools all -space machines. Nisan's generator has been used by Saks and Zhou (1999) to show that probabilistic log-space computation can be simulated deterministically in space . This result is still the best known derandomization result for general log-space machines in 2012.

Constructions of pseudorandom generators

Efficient constructions of pseudorandom generators are known for several natural classes of functions, including the following ones.

• The class of functions computable by randomized logspace Turing Machines that produce a single bit of output.
• The class of functions computable by randomized constant depth circuits that produce a single bit of output.
• The class of linear functions in many variables over some finite field F_q. These pseudorandom generators are sometimes called epsilon-biased generators.
• The class of polynomials of low degree in many variables over some finite field F_q. (See pseudorandom generators for polynomials.)

Limitations on the provability of pseudorandom generators

The pseudorandom generators used in cryptography and universal algorithmic derandomization have not been proven to exist, although their existence is widely believed. Proofs for their existence would imply proofs of lower bounds on the circuit complexity of certain explicit functions. Such circuit lower bounds cannot be proved in the framework of natural proofs assuming the existence of stronger variants of cryptographic pseudorandom generators.