A PRG G maps 128-bit seeds to 256-bit outputs. There are 2^128 possible outputs (one per seed), but 2^256 possible 256-bit strings. Why doesn't this make PRG output trivially distinguishable from random?
Think about your answer, then reveal below.
Model answer: The 2^128 outputs form a vanishing fraction (2^{-128}) of all 2^256 strings, so a distinguisher with unlimited computation could check membership in this set. But no efficient (polynomial-time) distinguisher can perform this check — it would require either inverting G (which is hard by the OWF assumption) or enumerating all 2^128 seeds. Computational indistinguishability means no polynomial-time test can detect the difference, not that the distributions are identical. The distinction between information-theoretic and computational indistinguishability is precisely the gap that makes PRGs possible.
This is the fundamental insight of computational cryptography. Perfect randomness requires as many random bits as output bits (Shannon's theorem). PRGs cheat by producing output that is statistically biased but computationally indistinguishable from random. Any test that detects the bias requires super-polynomial time, so for all practical purposes the output is random.
Question 2 Multiple Choice
The Goldreich-Levin theorem states that any one-way function f has a hard-core predicate: a bit b(x) that is easy to compute from x but indistinguishable from random given only f(x). How does this yield a PRG?
AThe hard-core bit is used as the PRG's expansion factor
BGiven OWF f and hard-core predicate b, define G(x) = (f(x), b(x)). The output is one bit longer than the input (the hard-core bit is the 'extra' bit), and indistinguishability follows because b(x) looks random given f(x). Iterating this construction by feeding f(x) back as input yields arbitrary-length expansion
CThe hard-core bit replaces the need for a seed
DHard-core predicates are used to verify PRG output, not to construct it
G(x) = (f(x), b(x)) expands by exactly one bit. Since b(x) is indistinguishable from random given f(x), the output (f(x), b(x)) is indistinguishable from (f(x), r) where r is a truly random bit. Iterating — computing G(x) = (f(f(...f(x)...)), b(x), b(f(x)), ..., b(f^{n-1}(x))) — produces n pseudorandom bits from one seed. Each bit is hard-core with respect to the remaining state, so the full output is indistinguishable from random. This is the HILL construction that proves OWFs imply PRGs.
Question 3 True / False
A PRG with expansion factor 2 (mapping n bits to 2n bits) can be composed with itself to achieve any polynomial expansion factor.
TTrue
FFalse
Answer: True
Given G: {0,1}^n → {0,1}^{2n}, split the output into two n-bit halves: G(s) = (s0, s1). Use s0 as the seed for the next application: G(s0) = (s00, s01). This tree-based construction produces 2^k * n bits from an n-bit seed after k levels, with each level doubling the output. A hybrid argument shows that distinguishing the composed output from random requires distinguishing a single application — if the single-step PRG is secure, so is the composed version.
Question 4 Multiple Choice
Why is computational indistinguishability (rather than statistical indistinguishability) the right definition for PRGs?
AStatistical indistinguishability is impossible to achieve with deterministic functions
BComputational indistinguishability requires that no polynomial-time algorithm can distinguish the distributions, which is exactly the threat model in cryptography (polynomial-time adversaries). Statistical indistinguishability would require the output distribution to be close to uniform in total variation distance — impossible when the output is longer than the seed, since only 2^n of 2^{l(n)} strings are reachable
CComputational indistinguishability is weaker and therefore easier to prove
DStatistical tests are unreliable, so computational indistinguishability avoids them
A PRG with expansion maps 2^n inputs to 2^{l(n)} outputs where l(n) > n. The output distribution has weight on only 2^n points in a space of 2^{l(n)}, so its statistical distance from uniform is at least 1 - 2^{n-l(n)} — essentially 1 for any meaningful expansion. Statistical indistinguishability is literally impossible. Computational indistinguishability is achievable because detecting this statistical bias requires super-polynomial computation. This is the core idea enabling all of computational cryptography.
Question 5 Short Answer
A CSPRNG used in practice (like ChaCha20) and a theoretical PRG built from OWFs serve the same conceptual purpose but differ dramatically in efficiency. What explains the gap?
Think about your answer, then reveal below.
Model answer: The OWF-to-PRG construction (HILL theorem) is an existential proof — it shows PRGs exist if OWFs exist but produces an impractical construction that extracts one bit at a time through iterated OWF evaluation. Practical CSPRNGs like ChaCha20 are designed directly for efficiency using concrete assumptions about a specific cipher's security, without going through the OWF abstraction. The theoretical construction proves possibility; the practical design achieves performance. They meet the same definition but are separated by many orders of magnitude in speed.
This gap between theory and practice is common in cryptography. Theory provides feasibility results and definitional frameworks; practice provides efficient instantiations justified by concrete security analysis. The theoretical result assures us that the goal is achievable; the practical construction is what actually gets deployed.