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. 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.
Definition Let A = { A : { 0 , 1 } n → { 0 , 1 } ∗ } {\displaystyle {\mathcal {A}}=\{A:\{0,1\}^{n}\to \{0,1\}^{*}\}} be a class of functions. These functions are the statistical tests that the pseudorandom generator will try to fool, and they are usually algorithms. Sometimes the statistical tests are also called adversaries or distinguishers. The notation in the codomain of the functions is the Kleene star. A function G : { 0 , 1 } ℓ → { 0 , 1 } n {\displaystyle G:\{0,1\}^{\ell }\to \{0,1\}^{n}} with ℓ < n {\displaystyle \ell <n} is a pseudorandom generator against A {\displaystyle {\mathcal {A}}} with bias ε {\displaystyle \varepsilon } if, for every A {\displaystyle A} in A {\displaystyle {\mathcal {A}}} , the statistical distance between the distributions A ( G ( U ℓ ) ) {\displaystyle A(G(U_{\ell }))} and A ( U n ) {\displaystyle A(U_{n})} is at most ε {\displaystyle \varepsilon } , where U k {\displaystyle U_{k}} is the uniform distribution on { 0 , 1 } k {\displaystyle \{0,1\}^{k}} . The quantity ℓ {\displaystyle \ell } is called the seed length and the quantity n − ℓ {\displaystyle n-\ell } is called the stretch of the pseudorandom generator. A pseudorandom generator against a family of adversaries ( A n ) n ∈ N {\displaystyle ({\mathcal {A}}_{n})_{n\in \mathbb {N} }} with bias ε ( n ) {\displaystyle \varepsilon (n)} is a family of pseudorandom generators ( G n ) n ∈ N {\displaystyle (G_{n})_{n\in \mathbb {N} }} , where G n : { 0 , 1 } ℓ ( n ) → { 0 , 1 } n {\displaystyle G_{n}:\{0,1\}^{\ell (n)}\to \{0,1\}^{n}} is a pseudorandom generator against A n {\displaystyle {\mathcal {A}}_{n}} with bias ε ( n ) {\displaystyle \varepsilon (n)} and seed length ℓ ( n ) {\displaystyle \ell (n)} . In most applications, the family A {\displaystyle {\mathcal {A}}} 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.
In cryptography
… excerpt ends here. Continue reading the full article.
