Pseudorandom generator
Encyclopedia
In theoretical computer science
, a pseudorandom generator (PRG) is a deterministic procedure
that produces a pseudorandom distribution from a short uniform input, known as a random seed
.
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 Fn are sometimes called adversaries.
A pseudorandom generator against a family of adversaries F = {Fn} with bias ε(n) is a collection of pseudorandom generators {Gn: {0, 1}s(n) → {0, 1}n}, where Gn is a pseudorandom generator against Fn 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.
, 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 and their existence is necessary for many applications in cryptography
.
The existence of cryptographic pseudorandom generators is equivalent to the existence of one-way function
s (see Pseudorandom generator theorem
).
. Common constructions of stream cipher
s 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 function
s.
A fundamental question in computational complexity theory is whether all polynomial time randomized algorithm
s 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).
of certain explicit functions. Such circuit lower bounds cannot be proved in the framework of natural proof
s assuming the existence of stronger variants of cryptographic pseudorandom generators.
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, a pseudorandom generator (PRG) is a deterministic procedure
Deterministic algorithm
In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...
that produces a pseudorandom distribution from a short uniform input, known as a random seed
Random seed
A random seed is a number used to initialize a pseudorandom number generator.The choice of a good random seed is crucial in the field of computer security...
.
Definition
Let Fn = {f: {0, 1}n → T} be a class of functions. A function G: {0, 1}s → {0, 1}n, where s < n, is a pseudorandom generator against Fn with bias ε if for every f in Fn, 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}n, 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 Fn are sometimes called adversaries.
A pseudorandom generator against a family of adversaries F = {Fn} with bias ε(n) is a collection of pseudorandom generators {Gn: {0, 1}s(n) → {0, 1}n}, where Gn is a pseudorandom generator against Fn with bias ε(n).
In most applications, the family F represents some model of computation
Model of computation
In computability theory and computational complexity theory, a model of computation is the definition of the set of allowable operations used in computation and their respective costs...
, and one is interested in desigining a pseudorandom generator that is computable in the same or some closely related model.
Pseudorandom generators in cryptography
In cryptographyCryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, the class F usually consists of all circuit
Circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them....
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
Negligible
Negligible refers to the quantities so small that they can be ignored when studying the larger effect. Although related to the more mathematical concepts of infinitesimal, the idea of negligibility is particularly useful in practical disciplines like physics, chemistry, mechanical and electronic...
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 and their existence is necessary for many applications in cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
.
The existence of cryptographic pseudorandom generators is equivalent to the existence of one-way function
One-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...
s (see Pseudorandom generator theorem
Pseudorandom generator theorem
In computational complexity theory and cryptography, the existence of pseudorandom generators is related to the existence of one-way functions through a number of theorems, collectively referred to as the pseudorandom generator theorem.- Pseudorandomness :...
).
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 securitySemantic security
Semantic security is a widely used definition for security in an asymmetric key encryption algorithm. For a cryptosystem to be semantically secure, it must be infeasible for a computationally bounded adversary to derive significant information about a message when given only its ciphertext and...
. Common constructions of stream cipher
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
s are based on pseudorandom generators.
Pseudorandom generators may also be used to construct symmetric key cryptosystems
Symmetric-key algorithm
Symmetric-key algorithms are a class of algorithms for cryptography that use trivially related, often identical, cryptographic keys for both encryption of plaintext and decryption of ciphertext. The encryption key is trivially related to the decryption key, in that they may be identical or there is...
, 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 function
Pseudorandom function
In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish between a function chosen randomly from the PRF family and a random oracle...
s.
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.A fundamental question in computational complexity theory is whether all polynomial time randomized algorithm
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
s for decision problems
Computational problem
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring...
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
Avi Wigderson
Avi Wigderson is an Israeli mathematician and computer scientist, a professor of mathematics at the Institute for Advanced Study in Princeton. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural...
provided a candidate pseudorandom generator with these properties. In 1997 Russell Impagliazzo
Russell Impagliazzo
Russell Impagliazzo is a professor of computer science at the University of California, San Diego. He received his doctorate from the University of California, Berkeley. His advisor was Manuel Blum. He spent two years as a postdoc at the University of Toronto. He is a 2004 Guggenheim fellow...
and Avi Wigderson
Avi Wigderson
Avi Wigderson is an Israeli mathematician and computer scientist, a professor of mathematics at the Institute for Advanced Study in Princeton. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural...
proved that the construction of Nisan and Wigderson is a pseudorandom generator assuming that there exists a decision problem
Computational problem
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring...
that can be computed in time 2O(n) on inputs of length n but requires circuits
Circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them....
of size 2Ω(n).
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 MachinesTuring machineA Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
that produce a single bit of output. - The class of functions computable by randomized constant depth circuitsAC0AC0 is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all families of circuits of depth O and polynomial size, with unlimited-fanin AND gates and OR gates....
that produce a single bit of output. - The class of linear functionLinear functionIn mathematics, the term linear function can refer to either of two different but related concepts:* a first-degree polynomial function of one variable;* a map between two vector spaces that preserves vector addition and scalar multiplication....
s in many variables over some finite fieldField (mathematics)In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
Fq. These pseudorandom generators are sometimes called epsilon-biased generatorsEpsilon-Biased Sample SpacesIn computer science \epsilon-biased sample spaces, also known as \epsilon-biased generators or small-bias probability spaces, refer to small probability spaces that approximate larger spaces as defined below...
. - The class of polynomialPolynomialIn mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
s of low degree in many variables over some finite fieldField (mathematics)In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
Fq. (See pseudorandom generators for polynomialsPseudorandom generators for polynomialsIn theoretical computer science a pseudorandom generator for low-degree polynomials is an efficiently computable function whose output is indistinguishable from the uniform distribution by evaluation of low-degree polynomials in the following sense....
.)
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 complexityCircuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them....
of certain explicit functions. Such circuit lower bounds cannot be proved in the framework of natural proof
Natural proof
In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense "natural", it can be shown that no such proof can possibly be used to solve the P vs...
s assuming the existence of stronger variants of cryptographic pseudorandom generators.