Pseudorandom Functions

Core Idea

A pseudorandom function (PRF) family {F_k} maps inputs to outputs such that F_k (for a random key k) is computationally indistinguishable from a truly random function, even to an adversary with adaptive oracle access. PRFs are the theoretical model for block ciphers and the core building block for MACs, CPA-secure encryption, and key derivation. The GGM construction proves that PRGs imply PRFs, completing the chain: OWFs → PRGs → PRFs. A pseudorandom permutation (PRP) is a PRF that is also a bijection — the formal model for block ciphers like AES. The PRP/PRF switching lemma shows PRPs and PRFs are interchangeable for most applications when the domain is large.

Explainer

A pseudorandom function (PRF) family is a collection of keyed functions {F_k} such that when k is chosen randomly, the function F_k is computationally indistinguishable from a truly random function — even to an adversary who can adaptively choose inputs and observe outputs. This is a stronger guarantee than PRGs: the adversary has oracle access, meaning they can query F_k on any input of their choosing and see the corresponding output, yet they still cannot tell F_k apart from a genuinely random input-output mapping.

The formal definition captures the ideal behavior of a block cipher. AES with a random key should behave like a random permutation (a special case of a random function that is also a bijection). Every output should appear random given all previously observed input-output pairs, and no pattern in the outputs should reveal the key or predict future outputs. The PRP/PRF switching lemma shows that for large domains (like AES's 128-bit block space), random permutations and random functions are indistinguishable until the adversary has made close to 2^{n/2} queries, making the distinction irrelevant in practice.

The GGM construction (Goldreich, Goldwasser, Micali) builds a PRF from any PRG with expansion factor 2. Think of it as a binary tree: the root holds the key k. Applying the PRG to k produces two values (left and right children). Applying the PRG to each child produces four grandchildren, and so on. To evaluate F_k on an n-bit input x, walk from the root to a leaf, going left when the next input bit is 0 and right when it is 1. The leaf value is the output. The security proof uses a hybrid argument: replace the PRG output at each level with truly random values, one level at a time. Each replacement is undetectable by PRG security, and after n levels all leaves are independent random values — a truly random function. This construction, combined with the HILL theorem (OWFs → PRGs), proves that OWFs suffice for PRFs, completing the foundational chain of cryptographic primitives.

PRFs are the workhorse building block of modern cryptography. CPA-secure encryption: to encrypt message m, pick random r and output (r, F_k(r) XOR m) — this is essentially CTR mode, secure because F_k(r) is pseudorandom. MACs: F_k(m) is a secure MAC for fixed-length messages because forging a tag on a new message requires predicting a PRF output on an unqueried input. Key derivation: F_k(context) derives application-specific keys that are pseudorandom even if the adversary knows other derived keys. The universality of PRFs means that understanding this single primitive — a keyed function indistinguishable from random — unlocks the construction of most symmetric cryptographic tools.