A truly random function from {0,1}^n to {0,1}^n requires 2^n * n bits to specify (a lookup table). A PRF with an n-bit key specifies 2^n outputs using only n bits. Why doesn't this compression make PRFs trivially distinguishable?
Think about your answer, then reveal below.
Model answer: A truly random function can produce 2^{n*2^n} possible input-output mappings, while a PRF with n-bit keys produces only 2^n mappings. An unbounded adversary could enumerate all 2^n PRF-generated functions and check membership. But an adversary with polynomial oracle access can query at most polynomially many points — far too few to detect the compression. The PRF guarantee is that no polynomial-time adversary, even with adaptive queries, can distinguish F_k from a random function with non-negligible advantage.
This parallels the PRG situation: computational indistinguishability allows a massive compression that would be statistically detectable but is computationally invisible. A polynomial-time adversary sees polynomially many input-output pairs, and the PRF guarantee says these look exactly like random input-output pairs.
Question 2 Multiple Choice
The GGM construction builds a PRF from a PRG with expansion factor 2. The key is the PRG seed, and to evaluate F_k(x) for input x = x_1x_2...x_n, you start with k and iteratively apply G, choosing the left or right half based on each bit of x. Why does this work?
AEach bit of x selects a random function from a pre-computed table
BThe construction builds a binary tree of depth n. The root is labeled with key k; each internal node's children are the two halves of the PRG applied to the node's label. The leaf reached by input x is F_k(x). A hybrid argument shows that replacing any single node's PRG output with truly random values is indistinguishable (by PRG security), and there are only polynomially many hybrids across the n levels
CThe XOR of all path nodes ensures output randomness
DG is applied n times to create a hash chain
The GGM tree is a beautiful construction. At level 0, the root holds k. At level 1, G(k) = (k_0, k_1). At level 2, G(k_0) = (k_{00}, k_{01}) and G(k_1) = (k_{10}, k_{11}). Input x = x_1...x_n walks from root to leaf, turning left (first half) or right (second half) at each level based on x_i. The security proof replaces real PRG outputs with random values level by level, using the PRG security at each step. After n hybrid steps, all leaves are independent random values — exactly a random function.
Question 3 True / False
AES is modeled as a pseudorandom permutation (PRP) rather than a pseudorandom function (PRF). The PRP/PRF switching lemma says the distinction doesn't matter when the number of queries q satisfies q^2 << 2^n.
TTrue
FFalse
Answer: True
The switching lemma bounds the distinguishing advantage between a random permutation and a random function by q^2/2^{n+1}, where q is the number of queries and n is the block size. For AES with n = 128, this is negligible as long as q << 2^64. Since practical applications rarely process 2^64 blocks (that's 2^68 bytes ≈ 256 exabytes) with a single key, PRP and PRF are effectively interchangeable for AES. This is why AES can be used wherever a PRF is theoretically required.
Question 4 Multiple Choice
CPA-secure symmetric encryption can be built from a PRF: to encrypt message m, choose random r and output (r, F_k(r) XOR m). Why does the PRF property make this secure?
AThe PRF encrypts the randomness r, hiding the key
BIf F_k is a PRF, then F_k(r) for a random r is indistinguishable from a random string. So F_k(r) XOR m looks like random XOR m = random. An adversary who can distinguish this from random can distinguish F_k from a random function, contradicting the PRF property. The fresh random r ensures different encryptions of the same message produce different ciphertexts (semantic security)
CThe XOR operation provides information-theoretic security like a one-time pad
DThe PRF ensures that r cannot be guessed by the adversary
This is essentially CTR mode for a single block. The security reduction is clean: assume adversary A breaks CPA security. Construct distinguisher D that simulates the encryption scheme using its oracle (either F_k or a random function). If the oracle is random, the scheme is a one-time pad and A has zero advantage. If the oracle is F_k and A has advantage epsilon, then D distinguishes with advantage epsilon. Since F_k is a PRF, epsilon must be negligible.
Question 5 True / False
A PRF is a stronger primitive than a PRG: any PRF can be used to construct a PRG, but the GGM construction shows PRGs are sufficient to build PRFs.
TTrue
FFalse
Answer: True
To build a PRG from a PRF, simply fix the input and vary the key: G(k) = F_k(0) || F_k(1) || ... || F_k(m). Since F_k for a random k produces outputs indistinguishable from random, this concatenation is indistinguishable from a random string. Combined with GGM (PRG → PRF), this shows PRGs and PRFs are equivalent — they can be built from each other. Both are equivalent to one-way functions, completing the circle of equivalences.