Pseudorandom Functions and Permutations

A function family is a collection of functions $\{F_k\}_{k \in \{0,1\}^n}$ where each $F_k: \{0,1\}^m \to \{0,1\}^\ell$ is indexed by a key $k$. We write $F: \{0,1\}^n \times \{0,1\}^m \to \{0,1\}^\ell$ for the two-argument description, with $F(k, x) = F_k(x)$. The family is efficient if there is a polynomial-time algorithm computing $F(k,x)$ given both arguments. A pseudorandom function (PRF) is an efficient function family such that, when the key $k$ is chosen uniformly at random and hidden from an adversary, the function $F_k(\cdot)$ is computationally indistinguishable from a function $f$ drawn uniformly at random from the set of all functions $\{0,1\}^m \to \{0,1\}^\ell$. The adversary is modeled as interacting with an oracle: it submits inputs $x_1, x_2, \dots$ adaptively and receives outputs, but never sees the key or the internal randomness. Formally, for every probabilistic polynomial-time (PPT) oracle adversary $\mathcal{A}$,

where the first probability is over the random key $k$ and $\mathcal{A}$'s coins, and the second is over a uniformly random function $f$ (drawn from the exponentially large space of all such functions) and $\mathcal{A}$'s coins. A pseudorandom permutation (PRP) is the same idea specialized to bijections. Here $m = \ell$, and each $F_k$ is required to be a permutation of $\{0,1\}^m$ — invertible, and efficiently invertible given $k$ (this second requirement matters for decryption). The security definition compares $F_k$ against a permutation $\pi$ drawn uniformly at random from the symmetric group on $\{0,1\}^m$, rather than against an arbitrary random function. This is precisely the abstraction that models a block cipher: the key selects one specific, secret shuffling of the $2^m$ possible blocks, and no efficient adversary with oracle access can tell it apart from a "perfectly random shuffle." Two terminological refinements matter. A strong PRP (or "super PRP") requires indistinguishability even when the adversary is given a two-way oracle — it may query both $F_k(\cdot)$ and $F_k^{-1}(\cdot)$ — modeling an attacker who can both encrypt and decrypt under a fixed unknown key. An ordinary PRP only grants forward queries. Real block ciphers such as AES are conjectured to be strong PRPs.

The definition above is a game, not an algorithm, so "how it works" means: how do we use this game to certify security, how do we build a PRF from more primitive assumptions, and how does the PRF/PRP distinction actually bite in practice?

The distinguishing game. Security is defined operationally via an experiment run against an adversary $\mathcal{A}$ who does not know which "world" it is in. ``` Experiment PRF-Distinguish[A, n]: b ← {0, 1} // choose a world uniformly if b == 0: k ← {0,1}^n Oracle := F_k(·) // real keyed function else: f ← Uniform( Func[m -> ℓ] ) // truly random function Oracle := f(·) b' ← A^Oracle(1^n) // A queries oracle adaptively return (b' == b) Advantage(A) := | 2 · Pr[PRF-Distinguish[A,n] returns true] - 1 | ``` $F$ is a PRF iff `Advantage(A)` is negligible in $n$ for every PPT $\mathcal{A}$. The PRP game is identical except the two branches instantiate a keyed permutation $F_k$ and a uniformly random permutation $\pi$, and (for the strong PRP notion) the oracle also answers inverse queries in both worlds.

Building a PRF from a PRG (GGM construction). The theoretical anchor result is that PRFs can be constructed from any length-doubling pseudorandom generator, which in turn can be built from any one-way function. This is the Goldreich–Goldwasser–Micali (GGM) construction. Let $G: \{0,1\}^n \to \{0,1\}^{2n}$ be a PRG, and write $G(s) = G_0(s) \, \| \, G_1(s)$ as its left and right $n$-bit halves. Define the keyed family $F: \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ by walking down a binary tree of depth $n$ determined by the input bits: ``` Function F(k, x): // k is the n-bit key (root seed) s := k for i := 1 to n: if x[i] == 0: s := G_0(s) else: s := G_1(s) return s ``` Each key $k$ defines a full binary tree of depth $n$ with $2^n$ leaves, one per possible input $x$; the value $F_k(x)$ is the leaf reached by following the path dictated by the bits of $x$. Crucially, the algorithm only ever expands the single root-to-leaf path actually queried — it runs in time $O(n \cdot T_G(n))$ per evaluation, where $T_G$ is the PRG's running time, and never materializes the exponential tree.

Switching between PRF and PRP: the birthday bound. In practice we often want the stronger, structured object (a PRP, i.e., a block cipher) but analyze protocols as if a plain PRF were available, since PRFs compose more simply in proofs. The PRF/PRP switching lemma justifies this: a random permutation and a random function are themselves hard to distinguish, as long as the number of queries $q$ is small relative to the domain size $N = 2^m$. ``` Experiment Func-vs-Perm[A, N, q]: b ← {0,1} if b == 0: Oracle := f, f ← Uniform(Func[N -> N]) else: Oracle := π, π ← Uniform(Perm[N]) b' ← A^Oracle // A makes at most q queries return (b' == b) ``` No adversary, however unbounded computationally, can win this game with advantage exceeding

This bound is intrinsic to the birthday paradox: a random function occasionally repeats an output value on two distinct queries (a "collision"), while a permutation by definition never does. An adversary's best strategy is exactly to look for a repeated output among its $q \le N$ queries.

Efficiency of the definitions themselves. Being a PRF/PRP is a property of an efficient family: evaluating $F_k(x)$ must run in time polynomial in the security parameter $n$ (in practice, a fixed constant number of cipher rounds, e.g. 10–14 for AES). This is separate from the security claim, which is a statement about the absence of efficient distinguishers, not about running time of $F$ itself.

GGM construction cost. If $G$ runs in time $T_G(n)$, evaluating $F_k(x)$ for an $n$-bit input requires exactly $n$ sequential applications of $G$, giving time $O(n \cdot T_G(n))$ and using $O(n)$ space for the path of intermediate seeds (no exponential blowup, since only one root-to-leaf path is ever computed). Correctness of GGM as a PRF reduces to a hybrid argument over the levels of the tree: 1. Define hybrid $H_i$: the first $i$ levels of the tree are generated by real PRG expansions, and the values at depth $i$ (there are $2^i$ of them, but only those on paths actually queried are materialized) are replaced, level by level, with fresh true randomness. 2. $H_0$ is the real GGM function $F_k$; $H_n$ is a truly random function (every leaf value is an independent uniform string, since it was replaced with fresh randomness before ever being run through $G$ again). 3. If $H_{i-1}$ and $H_i$ were distinguishable with non-negligible advantage $\varepsilon$, that distinguisher can be converted into a distinguisher for the PRG $G$ itself (comparing $G(s)$ against a truly random $2n$-bit string) with related advantage — because the only difference between $H_{i-1}$ and $H_i$ at any queried node is whether its two children came from applying $G$ to a pseudorandom seed or were chosen freshly at random. 4. A standard hybrid/triangle-inequality argument sums the $n$ level-by-level advantages: if $G$ has distinguishing advantage at most $\delta(n)$, then $F$'s distinguishing advantage is at most $n \cdot \delta(n)$, still negligible since $n$ is polynomial and $\delta$ is negligible. This is the formal sense in which "PRFs exist if PRGs exist if one-way functions exist" — a foundational, unconditional-modulo-OWF existence result, even though in deployed systems we instead use heuristic constructions like AES for speed.

PRF/PRP switching lemma, proof sketch. Consider any adversary making $q$ distinct queries to either a uniformly random function $f: [N] \to [N]$ or a uniformly random permutation $\pi$. Couple the two experiments by using the same underlying randomness except where they must differ: sample $\pi$ first, and let $f$ agree with $\pi$ unless a "collision" would be forced. Concretely, condition on the event $\mathsf{NoCollision}$ that all $q$ answers from $f$ happen to be distinct (exactly as a permutation's must be). Given $\mathsf{NoCollision}$, the transcript is identically distributed in both experiments, so no adversary — regardless of running time — can distinguish them at all. The adversary can only win by exploiting $\lnot\mathsf{NoCollision}$, and

by a union bound over the $\binom{q}{2}$ pairs of queries, each colliding with probability $1/N$ under a random function. This gives the stated bound and explains why block ciphers with $m = 128$-bit blocks (like AES, $N = 2^{128}$) remain safely modeled as PRPs (equivalently, safely swapped for PRFs) as long as query counts stay far below $2^{64}$ — the birthday bound on a 128-bit block.

Honest tradeoffs. GGM is a beautiful existence proof but is far too slow for practice: each evaluation costs $n$ PRG calls (e.g. $n=128$ calls to build one output), whereas AES computes a comparable-security output in about 10 rounds. Deployed PRFs/PRPs (AES, ChaCha20-based PRFs, HMAC) are not proven secure from weaker assumptions; they are conjectured secure based on decades of public cryptanalysis withstanding differential and linear attacks. The abstraction is what lets protocol designers reason rigorously despite this gap: assume the primitive is a PRF/PRP, prove the protocol secure relative to that assumption, and let cryptanalysis separately stress-test the primitive.

Take a tiny toy instance to make the game concrete: $m = 3$-bit inputs, so the domain has $N = 8$ points, and suppose a distinguisher $\mathcal{A}$ is trying to tell apart a keyed PRP $F_k$ (modeling a toy 3-bit block cipher) from a uniformly random permutation $\pi$ of $\{0,1,\dots,7\}$, using $q = 4$ queries.

The adversary sees only one column (it does not know which world it's in) and must guess. Notice both columns list four distinct 3-bit strings — consistent with either column being a genuine permutation's outputs, so nothing here looks locally wrong. If instead the "real" column had repeated a value (say $F_k(011) = 101$, matching $F_k(000)$), that would be an instant giveaway that this could not be the ideal-permutation world, since $\pi$ never repeats. This is exactly the birthday-bound argument in miniature: with $N=8$ and $q=4$ queries, the chance a random function would accidentally avoid all repeats is

meaning a random function reveals itself (via a repeat) with probability around $59\%$ at just $q=4$ out of $N=8$ — small domains make PRF/PRP switching risky, which is exactly why the switching lemma's bound $q(q-1)/2N$ demands $N$ be exponentially large (as it is for a 128-bit block cipher) before the two notions are safely interchangeable. Now trace the GGM construction concretely for $n = 3$ with key $k = s_0 = 010$ and a (toy, illustrative) PRG doubling rule $G(s) = (s \oplus 100)\,\|\,(s \oplus 111)$, so $G_0(s) = s \oplus 100$ and $G_1(s) = s \oplus 111$: ``` F(k=010, x=101): level 1, bit=1: s := G_1(010) = 010 ⊕ 111 = 101 level 2, bit=0: s := G_0(101) = 101 ⊕ 100 = 001 level 3, bit=1: s := G_1(001) = 001 ⊕ 111 = 110 return 110 ``` Different inputs walk different root-to-leaf paths through the same tree rooted at $k$, and the hybrid argument says that as long as $G$ is a good PRG, no efficient observer of these leaf values can tell they came from a deterministic tree walk rather than from $2^3 = 8$ independent coin flips.

The formal definitions of pseudorandom functions and their reduction to one-way primitives are due to Oded Goldreich, Shafi Goldwasser, and Silvio Micali, whose 1984 construction (published 1986) turned "randomness that merely looks random" into a fully composable, keyed cryptographic tool. This built directly on Andrew Yao's and Manuel Blum's earlier work formalizing computational indistinguishability and pseudorandom generators, and set the stage for the modern provable-security paradigm used throughout symmetric cryptography.

Every symmetric-key primitive deployed at scale is, at heart, a claim about being a PRF or PRP. AES is analyzed and standardized as a strong pseudorandom permutation; its security in modes like GCM and CBC is proven assuming AES meets that bar. HMAC, used to authenticate essentially all TLS records and countless API requests, is proven a secure MAC under the assumption that its underlying compression function behaves as a PRF. Key derivation functions (HKDF, used throughout TLS 1.3 and Signal's key ratcheting) rely on PRF security to argue that derived subkeys look independent and random even though they come from one master secret. Stream cipher and CTR-mode encryption treat the block cipher as a PRF evaluated on a counter, directly invoking the PRF definition rather than the permutation one, since no inversion is needed there. The GGM construction itself, while impractical to deploy directly, remains foundational in theory: it underlies feasibility results for oblivious transfer, garbled circuits, and constrained/updatable PRFs used in advanced protocols like private set intersection and searchable encryption. Understanding PRFs and PRPs is thus the prerequisite for reading any serious security proof about a block cipher or a MAC, and for understanding why "AES is secure" is really shorthand for "AES is assumed to be a strong PRP."

Ask the tutor: How does the Luby–Rackoff construction turn a PRF into a provably secure PRP using a Feistel network?