Pseudorandomness and Pseudorandom Generators

A pseudorandom generator is a deterministic function

with $\ell(n) > n$, that maps every $n$-bit seed to an $\ell(n)$-bit output, such that the output distribution — when the seed is chosen uniformly at random — is computationally indistinguishable from the uniform distribution on $\{0,1\}^{\ell(n)}$. The function $\ell(n)$ is called the stretch factor, and it must satisfy $\ell(n) - n \geq 1$ (some works require $\ell(n) \geq n + \omega(\log n)$ so that stretch grows meaningfully with security parameter, but any polynomial stretch above $n$ is the essential requirement). The key technical term is computational indistinguishability. Two probability ensembles $\{X_n\}$ and $\{Y_n\}$ (indexed by a security parameter $n$) are computationally indistinguishable if, for every PPT algorithm $D$ (the "distinguisher"), the quantity

is a negligible function of $n$ — meaning it shrinks faster than the reciprocal of every polynomial, i.e. for every constant $c$, eventually $\mathrm{Adv}(D) < 1/n^c$. Negligibility is exactly the threshold at which an adversary running for polynomially many trials still cannot accumulate a noticeable edge; it is the standard "close enough to impossible" bar throughout modern cryptography. A PRG's security is then defined by requiring the distribution $G(U_n)$ — $G$ applied to a uniform $n$-bit seed $U_n$ — to be computationally indistinguishable from $U_{\ell(n)}$, a truly uniform $\ell(n)$-bit string. Crucially, this is a statement about efficient observers only. An information-theoretic (unbounded) adversary can always distinguish $G(U_n)$ from uniform, because $G$'s range has size at most $2^n$ out of $2^{\ell(n)}$ possible strings — an astronomically small fraction once $\ell(n) > n$. So no PRG can be perfectly random; the entire discipline lives in the gap between "distinguishable in principle" and "distinguishable in polynomial time."

The distinguishing game

PRG security is formalized as a game between a challenger and a distinguisher $D$. ``` PRG-INDISTINGUISHABILITY GAME G_{PRG-DIST}(D, n): 1. Challenger flips a fair coin b ∈ {0, 1}. 2. If b = 0: seed s <- Uniform({0,1}^n) y <- G(s) // pseudorandom string Else: y <- Uniform({0,1}^{ell(n)}) // truly random string 3. Challenger sends y to D. 4. D outputs a guess b' ∈ {0, 1}. 5. D "wins" (succeeds) if b' = b. Distinguishing advantage: Adv(D, n) = | Pr[b' = 1 | b = 1] - Pr[b' = 1 | b = 0] | = 2 * Pr[b' = b] - 1 ``` G is a secure PRG if, for every PPT distinguisher D, Adv(D, n) is negligible in n. The two expressions for advantage are algebraically equivalent — a standard fact worth internalizing. Writing $p_1 = \Pr[b'=1\mid b=1]$ and $p_0 = \Pr[b'=1\mid b=0]$, we have $\Pr[b'=b] = \tfrac12 p_1 + \tfrac12(1-p_0)$, so $2\Pr[b'=b]-1 = p_1 - p_0$, matching the first line up to sign. This means "guessing correctly noticeably more than half the time" and "distinguishing the two conditional output distributions" are the same phenomenon measured two ways.

Building intuition: the next-bit test

A subtler and extremely useful characterization is the next-bit predictor view, originally due to Yao. Say a PPT algorithm $P$ is a next-bit predictor for $G$ if, given the first $i$ bits of $G(s)$ for a random seed $s$, $P$ guesses bit $i+1$ correctly with probability noticeably better than $1/2$, for some index $i$. ``` NEXT-BIT PREDICTION GAME G_{NBP}(P, n, i): 1. s <- Uniform({0,1}^n) 2. y <- G(s) // y has length ell(n) 3. P is given y_1 y_2 ... y_i (the first i bits of y) 4. P outputs a guess g for y_{i+1} 5. P succeeds if g = y_{i+1} ```

Theorem (Yao's next-bit test). $G$ is a secure PRG if and only if no PPT algorithm is a next-bit predictor for $G$ with non-negligible advantage over $1/2$, for any bit position $i$. The "only if" direction is easy: a good next-bit predictor can be turned into a distinguisher (feed it the challenge string, check its guess against a locally supplied extra bit generated similarly — details in the correctness section below). The "if" direction is the interesting one and is proved by a hybrid argument: it shows that if no single bit is predictable, then the entire output is indistinguishable from uniform. This equivalence is enormously useful in practice, because verifying "every bit is unpredictable from its predecessors" is often more tractable than reasoning about the full joint distribution.

A concrete construction template

In practice, PRGs are built by composing a hardness assumption with a stretching mechanism. The canonical template, when a one-way permutation with a hard-core predicate is available, is: ``` CONSTRUCTION: PRG from a one-way permutation f with hard-core bit h Given: f: {0,1}^n -> {0,1}^n (a one-way permutation) h: {0,1}^n -> {0,1} (a hard-core predicate for f) G(s): x0 <- s output_bits <- empty list for i = 1 to k: // k = desired extra output length b_i <- h(x_{i-1}) // leak one "safe" bit x_i <- f(x_{i-1}) // advance the internal state append b_i to output_bits return (x_k, output_bits) // length n + k > n ``` Here $x_k$, the final permuted state, is included in the output because $f$ is a bijection — it costs nothing to reveal (it reveals no information about the seed beyond what an attacker already effectively has), while each $b_i$ leaks exactly one unpredictable bit per application of $f$. The security proof is a reduction: any next-bit predictor against this $G$ is turned into an algorithm that predicts the hard-core bit $h(x_{i-1})$ from $f(x_{i-1})$ alone, contradicting the hard-core predicate property. Composing this with the next-bit theorem gives full PRG security.

Running time. A PRG $G$ is required to be computable by a deterministic algorithm running in time polynomial in $n$ (equivalently, polynomial in the output length $\ell(n)$, since $\ell(n)$ is itself polynomial in $n$). For the one-way-permutation-based construction above, each of the $k$ rounds costs one evaluation of $f$ and one evaluation of $h$; if both are computable in polynomial time (as required for $f$ to be a candidate one-way permutation with efficient forward evaluation), the whole generator runs in time $O(k \cdot T_f)$ where $T_f$ is the cost of one $f$-evaluation — polynomial overall.

Space. The generator needs only $O(n)$ space to hold the current state $x_i$, plus $O(k)$ space to accumulate output bits, so total space is $O(n + k)$, linear in the output length. No PRG needs more space than its output length up to additive lower-order terms, since it is a straight-line, non-branching stretch computation.

Why perfect (information-theoretic) security is impossible. This is the honest limitation to state up front. Fix any $G: \{0,1\}^n \to \{0,1\}^{\ell(n)}$ with $\ell(n) > n$. The image of $G$ has size at most $2^n$, while the codomain has size $2^{\ell(n)}$. An unbounded distinguisher can simply hard-code the entire image set of $G$ (computing it by brute force) and output 1 iff the challenge string lies in that set. Since $|image(G)| / 2^{\ell(n)} \le 2^{n - \ell(n)}$, which vanishes as $\ell(n)$ grows past $n$, this distinguisher achieves advantage close to 1 exactly when $\ell(n)$ is even modestly larger than $n$ — and even when the gap is a single bit, the image covers at most half the space, giving distinguishing advantage at least $1/2$. This proves rigorously that no PRG can fool an unbounded adversary; the entire notion is meaningful only relative to bounded (PPT) adversaries, which is why computational indistinguishability, not statistical indistinguishability, is the correct and unavoidable definitional choice.

Existence is conditional, not unconditional. It remains a major open problem (equivalent to $P \ne NP$ being necessary but not known sufficient) whether PRGs exist unconditionally. What is known: PRGs exist if and only if one-way functions exist (Håstad–Impagliazzo–Levin–Luby, the HILL theorem — one direction is straightforward: a secure PRG immediately yields a one-way function; the deep direction constructs a PRG from any one-way function, not just one-way permutations, using universal hash functions and the Goldreich–Levin hard-core predicate). So all PRG security claims are conditional on a computational hardness assumption; there is no proof of security from "first principles" alone.

Correctness of the next-bit theorem (proof sketch). The forward direction (predictor ⟹ distinguisher) is direct: given a next-bit predictor $P$ that succeeds with probability $\tfrac12 + \varepsilon$ at position $i$, build a distinguisher $D$ that, on challenge string $y$, runs $P$ on the first $i$ bits of $y$ and outputs 1 (claims "pseudorandom") if $P$'s guess matches $y_{i+1}$, else outputs a random guess; a careful accounting shows $D$'s advantage is $\Theta(\varepsilon)$, non-negligible if $\varepsilon$ is. The reverse direction (no predictor at any position ⟹ full indistinguishability) uses a hybrid argument, one of the most important proof techniques in cryptography. Define hybrid distributions $H_0, H_1, \dots, H_{\ell(n)}$ where $H_i$ consists of the first $i$ bits of $G(s)$ followed by $\ell(n) - i$ truly uniform bits. Then $H_0$ is exactly the uniform distribution $U_{\ell(n)}$, and $H_{\ell(n)}$ is exactly $G(U_n)$. If some distinguisher $D$ separated $H_0$ from $H_{\ell(n)}$ with advantage $\varepsilon$, then by a standard triangle-inequality / averaging argument, $D$ must separate some adjacent pair $H_{i-1}$ and $H_i$ with advantage at least $\varepsilon / \ell(n)$. But $H_{i-1}$ and $H_i$ differ only in whether position $i$ is drawn pseudorandomly (via $G$, correlated with the earlier bits) or independently at random — distinguishing them is exactly equivalent to a next-bit prediction task at position $i$. Since $\ell(n)$ is polynomial, dividing a negligible-or-nonexistent quantity by it still leaves something negligible (or the contrapositive: if $\varepsilon$ were non-negligible, $\varepsilon/\ell(n)$ would remain non-negligible, contradicting the no-predictor assumption). This completes the equivalence.

Tradeoffs to be honest about:

• PRGs give computational, not information-theoretic, security — a sufficiently powerful adversary (unbounded time/space) can always break them in principle.
• Security depends on unproven hardness assumptions (one-way functions existing); if $P = NP$, essentially all standard PRG candidates collapse.
• Stretching further (large $\ell(n)$) does not come "for free" in a security proof — the hybrid argument's loss factor of $\ell(n)$ means the underlying one-way function assumption must be very strong (negligible-enough inversion probability) to support large stretch with a tight security bound; in practice, block-cipher/hash-based PRGs sidestep this by direct heuristic construction (e.g., counter mode) rather than a bit-by-bit hybrid.

Because a real cryptographic PRG (e.g., built from AES or SHA-256) is too complex to trace by hand, we illustrate the mechanics and the distinguishing game using a deliberately small, insecure toy generator — this is pedagogically standard: the goal is to see exactly how the game and next-bit test operate, not to see a secure scheme.

Toy generator. Let $n = 4$. Define

where $\mathrm{parity}(s)$ is the XOR of all 4 bits of $s$ — so $\ell(4) = 5$, a stretch of exactly one bit. Trace for a specific seed:

Now run the distinguishing game conceptually. The challenger flips $b$:

• If $b = 0$: samples $s$ uniformly from the 16 possible 4-bit strings, outputs $G(s)$, a 5-bit string whose last bit always equals the XOR of the first four.
• If $b = 1$: samples a uniform 5-bit string — with probability $1/2$ its last bit will not match the XOR of the first four.

Distinguisher strategy. ``` D(y): // y is 5 bits: y1 y2 y3 y4 y5 p <- y1 XOR y2 XOR y3 XOR y4 if p == y5: return 1 // "guess: pseudorandom" else: return 0 // "guess: truly random" ``` Compute $D$'s advantage exactly. When $b=0$ (input is $G(s)$), the parity check always holds by construction, so $\Pr[D \text{ outputs } 1 \mid b=0] = 1$. When $b=1$ (input is truly uniform 5 bits), the last bit is independent and uniform, so it matches the XOR of the first four with probability exactly $1/2$: $\Pr[D \text{ outputs } 1 \mid b=1] = 1/2$.

This is a constant (certainly non-negligible) advantage, and $D$ runs in $O(1)$ time (just four XORs and a comparison) — so this toy $G$ is not a secure PRG. This is exactly the intended lesson: appending a simple deterministic function of the seed (like a parity bit) as "extra output" creates a detectable structural signature. A real PRG's extra bits must be computationally unpredictable given everything already output, which is precisely why constructions rely on one-way functions and hard-core predicates rather than simple linear functions of the seed.

Second trace — the next-bit view. Apply the next-bit predictor test at position $i = 4$ (predicting the 5th bit given the first four). The predictor $P$ simply computes $p = y_1 \oplus y_2 \oplus y_3 \oplus y_4$ and outputs $g = p$. When the string comes from $G$, this succeeds with probability $1$; a real PRG would force $P$'s success probability down to $1/2 + \mathrm{negl}(n)$. This shows concretely how a next-bit predictor and a full distinguisher are two views of the identical weakness, exactly as the theorem predicts.

Every stream cipher — RC4 historically, ChaCha20 in modern TLS and SSH — is fundamentally a PRG whose output is XORed with plaintext; understanding PRG security is a direct prerequisite to understanding Stream Ciphers. Operating-system CSPRNGs (`/dev/urandom` on Linux, `CryptGenRandom`/`BCryptGenRandom` on Windows, `getrandom()` syscalls) are engineered to meet the PRG indistinguishability definition, seeded from hardware entropy sources and then stretched deterministically for all subsequent requests. TLS 1.3 key schedules, SSH session key derivation, and disk-encryption tools (e.g., LUKS, BitLocker) all rely on PRG-like key-derivation functions to expand a single master secret into many independent-looking subkeys. Block ciphers run in counter mode (CTR) are explicitly designed and analyzed as PRGs, forming the bridge to Pseudorandom Functions and Permutations, where a keyed family of functions must look random not just once but under adaptive, repeated querying. Hardware random number generators (Intel's RDRAND) are themselves typically PRGs seeded by a physical entropy source, illustrating that "randomness" in deployed systems is almost always this computational notion rather than a literal physical process observed directly.

Ask the tutor: How does the hybrid-argument proof change if the PRG's stretch factor ℓ(n) grows super-polynomially instead of polynomially?