A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A pseudorandom generator (PRG) is a deterministic function G: {0,1}^n → {0,1}^l(n) with l(n) > n (expansion) such that the output on a random seed is computationally indistinguishable from a truly random string of length l(n). No efficient statistical test can tell PRG output from random with non-negligible advantage. PRGs exist if and only if one-way functions exist (HILL theorem). The Goldreich-Levin hard-core bit construction turns any OWF into a PRG by extracting one pseudorandom bit per invocation, then iterating. PRGs are the theoretical foundation of stream ciphers and the basis for building pseudorandom functions.
A pseudorandom generator (PRG) is a deterministic algorithm that stretches a short, truly random seed into a longer output that is computationally indistinguishable from a truly random string of the same length. The seed might be 128 bits; the output might be megabytes. No efficient algorithm — no statistical test, no machine learning model, no adversarial strategy running in polynomial time — can tell the PRG's output from genuine randomness with non-negligible advantage. This is a strictly computational guarantee: an all-powerful adversary could detect the pseudorandomness (only 2128 of the 2huge possible output strings are reachable), but no adversary with bounded resources can.
The existence of PRGs is equivalent to the existence of one-way functions — the most fundamental assumption in cryptography. The forward direction (OWFs imply PRGs) was proven by Hastad, Impagliazzo, Levin, and Luby (the HILL theorem). The construction uses the Goldreich-Levin hard-core bit: given any one-way function f, there exists a predicate b(x) that is easy to compute from x but looks random given only f(x). Define G(x) = (f(x), b(x)) — this expands by one bit, and the extra bit is pseudorandom. Iterating (compute f, extract a hard-core bit, use f(x) as the new state) yields arbitrary expansion. The reverse direction is simpler: a PRG is itself a one-way function (inverting G on a random output requires finding the seed from an exponentially small set).
PRGs are the theoretical foundation of stream ciphers (which produce a long keystream from a short key and encrypt by XOR) and the first step in the construction chain that builds all of symmetric cryptography from OWFs: OWFs → PRGs → pseudorandom functions → MACs → secure encryption. Each step in this chain is proven by reduction, ensuring that breaking the higher-level primitive implies breaking the lower-level one, which ultimately implies breaking the one-way function.
In practice, deployed CSPRNGs (ChaCha20, AES-CTR used as a PRNG) are not built through the theoretical OWF-to-PRG construction — that construction is correct but horrendously slow, extracting one pseudorandom bit per OWF invocation. Instead, practical PRGs are designed directly using concrete ciphers and analyzed under specific assumptions about those ciphers. The theoretical framework provides the definitions (what it means to be pseudorandom) and the feasibility result (PRGs can exist), while practice provides efficient instantiations. Understanding the theory explains why the definitions look the way they do and what guarantees they provide — which is essential for correctly using and analyzing the practical constructions.