Pseudorandom Generator

A pseudorandom generator is a deterministic algorithm that expands a short random seed into a long sequence of bits that appears random to any efficient observer. The defining property is not statistical resemblance to true randomness in an absolute sense, but \*computational indistinguishability\*: no polynomial-time algorithm can reliably distinguish the generator's output from a truly random sequence with more than negligible advantage.

The concept is central to the derandomization program, where pseudorandom generators convert hardness into randomness: if sufficiently hard computational problems exist, they can be used to construct generators that fool all efficient algorithms. The seed length, the stretch (how much the seed is expanded), and the class of fooled observers are the three parameters that define a generator's power. The Nisan-Wigderson Theorem provides the canonical construction, showing that exponential circuit lower bounds imply polynomial-time derandomization.

Pseudorandom generators also underpin modern cryptography, where they protect secrets by making encrypted messages computationally indistinguishable from random noise. The distinction between complexity-theoretic and cryptographic generators is subtle: the former must fool observers with bounded resources, while the latter must fool adversaries who may have more resources than the legitimate user but are limited by what they can observe.

The mathematical theory of pseudorandomness also intersects with randomness extractors — algorithms that convert weak random sources into nearly uniform distributions — and with the broader question of whether indistinguishability obfuscation can serve as a cryptographic primitive sufficient for constructing all of cryptography.