Pseudorandom Functions

If Alice and Bob want to communicate privately in the presence of an adversary, they must share some secret. The longer the shared secret is, the more data they can send.

You just learned about PRGs, which can upgrade a short shared secret into a longer one. This chapter introduces pseudorandom functions, which take the idea of a PRG to an extreme. Using a PRF, Alice and Bob can expand a short shared secret into an effectively unlimited amount of shared secret data.

6.1. Motivating and defining PRFs

Alice and Bob want to appear (to the adversary) as though they have not just a uniformly sampled string but a huge, shared dictionary data structure filled with uniformly sampled strings. A dictionary is like an array that is indexed by strings rather than integers. A dictionary, indexed by $n$-bit strings and filled with uniformly sampled $m$-bit strings, would be accessed via the following interface:

At each distinct position in this data structure, you'll find an independent, uniformly sampled $m$-bit string. Of course, that $m$-bit string never changes after it is chosen, so if you call query twice with the same input, you'll get the same output.

We can even consider values of $n$ like $n=\secpar$, which cause the dictionary to be exponentially large. In that case, the code written above would require exponential time to initialize the dictionary. On the other hand, a polynomial-time calling program would only be able to access a tiny fraction of its entries. We can use the following trick to implement an “exponentially large” dictionary, in polynomial time: Instead of sampling all entries eagerly at the beginning of time, the library can sample them lazily at the moment they are requested:

This way, if the calling program runs in polynomial time, then the library does too. We refer to this idiom as a lazy random dictionary. The goal of a pseudorandom function is to provide the same functionality as a lazy random dictionary.

A pseudorandom function (PRF) takes two inputs: Just like a PRG, a PRF expects a uniformly chosen seed. A PRF also expects an input corresponding to the value $X$ in the libraries above, the “index” into the lazy random dictionary. In our usual approach to security definitions, the victim is responsible for choosing the seed: uniformly, secretly, and in this case, reused in every call to the PRF. The other PRF input is left completely under the adversary's control.

Why “function?” A PRF is a function in the sense that a dictionary is like a function that maps $n$-bit inputs to $m$-bit outputs, represented as a simple truth table. A (lazy) random dictionary is the truth table of a function chosen uniformly from the set of all such functions.

Key derivation: One of the most common applications of a PRF is key derivation. Imagine Alice and Bob share a secret key, $\key$, but want to try out dozens of cryptographic algorithms. As a general rule, it's not safe to reuse the same key for many different algorithms, since the security definition for each algorithm assumes that its key is used for nothing else.

So instead of using their shared key $\key$ for multiple purposes, they treat it as a “master key” and use a PRF to derive any needed application-specific keys. They can use $F(\key, \bit{xyz})$ as their key for the XYZ algorithm; $F(\key,\bit{abc})$ as their key for the ABC algorithm. They can use $F(\key,\bit{this})$ for this and $F(\key,\bit{that})$ for that, and so on. The security property of a PRF is that these application-specific keys are indistinguishable from unrelated, independent, uniformly chosen keys.

6.2. How to attack PRFs

Let's gain some intuition about PRFs by seeing attacks against some insecure constructions.

Remember, a PRF is a deterministic function, by design. Don't try to attack a PRF by calling it twice on the same input and observing that the output repeats. This is not an attack, because both $\lib{prf-real}$ and $\lib{prf-rand}$ repeat outputs when $\prfquery$ is called on a repeated input.

6.2.1. A first example

6.2.2. A second example

Below is an unsuccessful attempt to use a PRF with shorter input length to build one with a larger input length.

Here's a slightly different way to think about this attack. Imagine xor'ing all four of these expressions together:

Each term of the form $F(\cdot,\cdot)$ appears exactly twice overall, meaning that every term will cancel when the values are xor'ed. Hence, $Y_1 \oplus Y_2 \oplus Y_3 \oplus Y_4 = \bit 0^m$, which is equivalent to the condition $Y_1 \oplus Y_2 = Y_3 \oplus Y_4$ used in the attack above.

The Golden Rule: The previous attack involved finding inputs to $H$ that led to repeated inputs to the underlying PRF $F$. This is the first example of a more general principle that applies whenever a PRF is used as a component in a larger construction. Remember, a PRF produces pseudorandom outputs only when it is called on distinct inputs.

In the next sections, we will see examples of how this Golden Rule appears in security proofs.

6.3. An example proof involving PRFs

Now let's see an example of a security proof involving PRFs. In this case, we show that composing a PRF with itself, using independent keys, results in a secure PRF.

Proof idea: The goal is to show that $H$ is a secure PRF—that is, when $H$ is called on distinct inputs, its outputs are pseudorandom. Working backward from our goal, what can we say about the outputs of $H$?

Outputs of $H$ are computed as direct outputs of $F$, which is itself a secure PRF. But remember to be careful, don't forget the Golden Rule! A PRF's outputs are pseudorandom only when its inputs are distinct. The PRF inputs in question are the intermediate values labeled $Y$ in the construction. Indeed, if two different inputs for $H$ produce the same $Y$, then they will produce identical outputs from $H$. So can we say anything about these $Y$ values being distinct (for distinct $X$)?

It might not be immediately clear whether the $Y$ values can repeat, but what is hopefully clear is that they are computed as outputs of $F(\key_1,\cdot)$, where $F$ is a secure PRF. Furthermore, the inputs to this $F$ are the inputs to $H$, which we are assuming to be distinct. Thus, the $Y$ values are pseudorandom; they are indistinguishable from uniformly sampled values.

But uniformly sampled values repeat only with negligible probability (if they are sufficiently long, as they are here); that is precisely the lesson of the birthday bound (section 4.5). This is the final puzzle piece in the proof.

The formal details of the proof follow below. Pay close attention to how these main ideas are formalized: (1) $Y$-values are pseudorandom and, therefore, indistinguishable from uniformly chosen values; (2) uniformly chosen values repeat only with negligible probability; and (3) distinct $Y$-values lead to pseudorandom outputs of $H$.

6.4. Building a PRG from a PRF: The CTR construction

A PRG is in many ways a simpler object than a PRF, because a PRG is “allowed” to generate its entire output as a monolithic string. A PRF must provide easy access to individual blocks of its output. (I hesitate to call this random access, since it invokes a different meaning of the word random.)

For theoretical and pedagogical purposes, it is natural to use simpler objects (PRG) to build more complex objects (PRF), as in the previous section. In practice, however, it's more common to have access to a PRF than to a PRG. If we want a PRG, we must therefore construct one from a PRF. It is not hard to do so, since this is the “easy direction”—a simple object built from a more complex one.

The intuition for the CTR construction is reasonably clear. If $F$ is a secure PRF and we call it on distinct inputs $0, 1, \ldots, k-1$, then the resulting outputs $F(\seed,0), F(\seed,1), \ldots, F(\seed,k-1)$ look independently pseudorandom. However, the proof is not as simple as you might expect because of a mismatch between the PRG and PRF security games:

• In the PRG security definition, the libraries model many instances of the PRG. Each call to $\prgsamp$ represents a new instance of the PRG with a freshly sampled seed.

• In the PRF security definition, the libraries model a single instance of the PRF, with a single PRF key that is used for the entire lifetime of the computation. All calls to $\prfquery$ use that same key.

We want to prove that construction 6.4.1 is a secure PRG. In the $\lib{prg-real}^G$ library, the construction $G$ will be invoked many times, each time on a freshly sampled seed $\seed$. Then $G$ proceeds to use $\seed$ as a PRF key. When we apply the security of a PRF in a hybrid proof, we can reason only about a single PRF key.

To account for this mismatch, we use a proof with a sequence of many hybrids—one hybrid for each call that the adversary makes to $\prgsamp$. Hybrid #$h$ acts like $\lib{prg-rand}$ for the first $h$ calls to $\prgsamp$, and acts like $\lib{prg-real}$ for the remaining calls. Then hybrids $h$ and $h+1$ are different only in how they respond to the adversary's $(h+1)$th call to $\prgsamp$. This difference involves only a single call to $G$, and, therefore, only a single PRF seed. We can use the security of the PRF $F$ to argue that hybrids $h$ and $h+1$ are indistinguishable.

6.5. ☆ Building a PRF from a PRG: The GGM construction

We can construct a PRF from a PRG by cleverly connecting many PRG invocations together in a binary tree. Each leaf of the tree corresponds to one of the PRF's outputs. We can compute one of those outputs—without computing them all—by traversing a path from the root to the leaf. We can use the bits of the PRF input $X$ to decide whether to go left or right at each step of the traversal. If $X$ has $n$ bits, then the binary tree has $n$ levels.

Construction 6.5.1 (The GGM construction)

Let $G$ be a length-doubling PRG. Then the GGM construction—named after its creators Goldreich, Goldwasser, and Micali—is defined as the following function $F : \bits^\secpar \times \bits^n \to \bits^\secpar$:

$F(\key,X)$:

$R := \key$

for $i = 1$ to $n$:

$S_0 \| S_1 := G(R)$

$R := S_{X[i]}$

return $R$

$\quad$

$X[i]$ denotes the $i$th bit of the string $X$, numbering the bits from 1 to $n$.

It's important to keep in mind that the GGM algorithm computes only a single path in this binary tree. It never computes the entire tree—it would be too large. The binary tree is only a conceptual tool, for understanding this construction, just like how an exponentially large random dictionary is a conceptual tool that helps us understand a lazy random dictionary.

To build intuition about the proof, let's just imagine an algorithm that generated the entire GGM binary tree, ignoring the fact that this would take exponential time. Proving that the values on the leaves are pseudorandom would be similar to previous proofs that involve several PRG instances connected together (claim 5.4.3). In our binary tree, the root node has uniform input and sends outputs of $G$ to its children. Such a tree is indistinguishable from a similar one that skips the root level and directly sends truly uniform values to the nodes of the second level. After this change, the two nodes in the second level now have uniform input, so this modified tree is indistinguishable from one that skips the first two levels and directly sends truly uniform values to the nodes of the third level.

A picture is forming of one hybrid for each level of the tree. In hybrid #$h$, the top $h$ levels of the tree are skipped, and inputs to layer $h$ of the tree are sampled uniformly.

This picture gives a good intuition about the necessary sequence of hybrids. However, all of these hybrids would require exponential time if the tree is sufficiently tall. We can avoid this, however, by generating these truncated binary trees in a lazy manner, just how $\lib{prf-rand}$ generates a random dictionary in a lazy manner. All of the difficulty in this proof stems from generating the binary tree lazily.

Proof:

We introduce the following library $\L_h$ with an integer parameter $h$:

$\L_{h}$

$\prfquery(X)$:

$P := \text{first } h \text{ bits of } X$

if $\prftable[P]$ undefined:

$\prftable[P] \gets \bits^\secpar$

$R := \prftable[P]$

for $i = h+1$ to $n$:

$S_0 \| S_1 := G(R)$

$R := S_{X[i]}$

return $R$

$\quad$

$\L_h$ implements a binary tree that skips the first $h$ layers and gives uniform inputs to nodes at layer $h+1$. However, $\L_h$ implements this tree lazily by storing the uniform values at layer $h$ in a lazy random dictionary. Using this library $\L_h$, we will break the proof into three steps:

1. $\lib{prf-real}^F \equiv \L_0$.

2. $\lib{prf-rand}^F \equiv \L_n$, where $n$ is the input length of the PRF construction.

3. For every $h \in \{1, \ldots, n\}$, we have $\L_{h-1} \indist \L_h$.

These three facts prove the claim because they imply that:

$\lib{prf-real}^F \equiv \L_0 \indist \L_1 \indist \cdots \indist \L_n \equiv \lib{prf-rand}^F.$

First, let's see why $\L_0$ is identical to $\lib{prf-real}^F$. In $\L_0$, $P$ is always the empty string $\epsilon$. The only part of $\prftable[\cdot]$ that is ever accessed is the single value $\prftable[\epsilon]$. If we give $\prftable[\epsilon]$ a simpler name like “$\key$,” and sample it at the beginning of time instead of the first time it is used, we obtain exactly $\lib{prf-real}^F$:

$\L_0$

$\prfquery(X)$:

$P :=$ first 0 bits of $X$

// $\Rightarrow$ $P := \epsilon$

if $\prftable[P]$ undefined:

$\prftable[P] \gets \bits^\secpar$

$R := \prftable[P]$

for $i = \hl{1}$ to $n$:

$S_0 \| S_1 := G(R)$

$R := S_{X[i]}$

return $R$

$\equiv$

$\lib{prf-real}^F$

// $\key = \prftable[\epsilon]$

$\key \gets \bits^\secpar$

$\prfquery(X)$:

$R := K$

for $i = 1$ to $n$:

$S_0 \| S_1 := G(R)$

$R := S_{X[i]}$

return $R$

Next, let's see why $\L_n$ is identical to $\lib{prf-rand}^F$. In $\L_n$, $P$ equals the entire input $X$. The for-loop ranges “from $n+1$ to $n$,” so it is never taken. Removing the for-loop, and replacing every reference to $P$ with a corresponding reference to $X$, we obtain $\lib{prf-rand}^F$:

$\L_{n}$

$\prfquery(X)$:

$P :=$ first $n$ bits of $X$

// $\Rightarrow$ $P := X$

if $\prftable[P]$ undefined:

$\prftable[P] \gets \bits^\secpar$

$R := \prftable[P]$

// for-loop never taken:

for $i = \hl{n+1}$ to $n$:

$S_0 \| S_1 := G(R)$

$R := S_{X[i]}$

return $R$

$\equiv$

$\lib{prf-rand}^F$

$\prfquery(X)$:

if $\prftable[X]$ undefined:

$\prftable[X] \gets \bits^\secpar$

return $\prftable[X]$

Finally, we need to show that $\L_{h-1} \indist \L_h$, for $h \in \{1, \ldots, n\}$. We do so with the following sequence of hybrids.

Hybrid Sequence:

[ [ ['145','add','hl'], ['148','add','hl'], ['141','add','hl'], ['33','remove','slide-up'], ['15','add','slide-down'] ], [ ['26','add','hl'], ['26','remove','hidden'], ['27','add','hl'], ['27','remove','hidden'], ['28','add','hl'], ['28','remove','hidden'], ['142','add','hl'], ['142','remove','slide-left'], ['3','add','hidden'], ['145','remove','hl'], ['145','add','slide-left'], ['148','remove','hl'], ['148','add','slide-left'], ['141','remove','hl'], ['141','add','slide-right'] ], [ ['26','remove','hl'], ['27','remove','hl'], ['28','remove','hl'], ['142','remove','hl'], ['10','add','hl'], ['144','add','hl'], ['50','remove','slide-up'], ['33','add','slide-down'] ], [ ['145','add','hl'], ['145','remove','slide-left'], ['10','remove','hl'], ['10','add','hidden'], ['144','remove','hl'], ['144','add','slide-right'] ], [ ['145','remove','hl'], ['26','add','hl'], ['147','add','hl'], ['68','remove','slide-up'], ['50','add','slide-down'] ], [ ['56','add','hl'], ['56','remove','hidden'], ['144','add','hl'], ['144','remove','slide-right'], ['61','add','hl'], ['61','remove','hidden'], ['148','add','hl'], ['148','remove','slide-left'], ['26','remove','hl'], ['26','add','hidden'], ['147','remove','hl'], ['147','add','slide-right'] ], [ ['56','remove','hl'], ['144','remove','hl'], ['61','remove','hl'], ['148','remove','hl'], ['156','add','hl'], ['61','add','hl'], ['86','remove','slide-up'], ['68','add','slide-down'] ], [ ['78','add','hl'], ['78','remove','hidden'], ['156','remove','hl'], ['156','add','slide-left'], ['61','remove','hl'], ['61','add','hidden'] ], [ ['78','remove','hl'], ['153','add','hl'], ['150','add','hl'], ['104','remove','slide-up'], ['86','add','slide-down'] ], [ ['154','add','hl'], ['154','remove','slide-left'], ['153','remove','hl'], ['153','add','slide-right'], ['150','remove','hl'], ['150','add','slide-right'] ], [ ['154','remove','hl'], ['8','add','hl'], ['155','add','hl'], ['121','remove','slide-up'], ['104','add','slide-down'] ], [ ['156','add','hl'], ['156','remove','slide-left'], ['8','remove','hl'], ['8','add','hidden'], ['155','remove','hl'], ['155','add','slide-right'] ], [ ['156','remove','hl'], ['5','add','hl'], ['78','add','hl'], ['138','remove','slide-up'], ['121','add','slide-down'] ], [ ['125','remove','hidden'], ['155','add','hl'], ['155','remove','slide-right'], ['150','add','hl'], ['150','remove','slide-right'], ['130','add','hl'], ['130','remove','hidden'], ['5','remove','hl'], ['5','add','hidden'], ['78','remove','hl'], ['78','add','hidden'] ], [ ['155','remove','hl'], ['150','remove','hl'], ['130','remove','hl'] ] ]

The starting point is $\L_{h-1}$.

Unroll the first iteration of the for-loop ($i=h$). Since $h \in \{1, \ldots, n\}$, the loop indeed has a first iteration. The change has no effect on the calling program.

Replace a redundant variable to clean things up.

We can rename $S_0$ and $S_1$ to $\prftable[P\|\bit0]$ and $\prftable[P\|\bit1]$. Then we can select the correct one using the entire $h$-bit prefix $P'$ of $X$, not just the $h$-th individual bit.

The library samples $\prftable[P]$ and then later (perhaps many times) computes $G(\prftable[P])$. We could instead compute $G(\prftable[P])$ immediately when $\prftable[P]$ is sampled and store the results for later.

The library assigns $\prftable[P]$ and $\prftable[P']$ at the same time, for all possible pairs $P$ and $P'$, so it doesn't matter which of $\prftable[P]$ or $\prftable[P']$ we use in the if-condition.

Now $\prftable[P]$ is used only as the seed to the PRG, so we can apply the security of the PRG $G$. The standard three-hop maneuver is not shown.

The library simultaneously samples both $\prftable[P']$ and its “sibling”: the same string as $P'$ with last bit flipped. But only one of these values is needed in a single call to $\prfquery$. Since these values are sampled independently, we can sample only the needed one and defer the sibling value until later (if needed). The result is $\L_{h}$, which completes the proof.

$\L_{h-1}$

$\L_{h}$

$\prfquery$($X$):

$P := \text{first } h-1 \text{ bits of } X$

$P' := \text{first } h \text{ bits of } X$

if

$\prftable[P]$ undefined:

$\prftable[P']$ undefined:

$\prftable[P] \gets \bits^\secpar$

$\prftable[P\|\bit{0}] \,\big\|\, \prftable[P\|\bit{1}]$

${}:= G(\prftable[P])$

 // $\rightarrow$

${}\gets \bits^{2\secpar}$

$\prftable[P'] \gets \bits^\secpar$

$R := \prftable[P]$

$S_0 \| S_1 := {}$

$G(R)$

$G(\prftable[P])$

$\prftable[P\|\bit{0}] \,\big\|\, \prftable[P\|\bit{1}] := G(\prftable[P])$

$R := {}$

$S_{X[h]}$

$\prftable[ P' ]$

for $i = {}$

$h$ to $n$:

$h+1$ to $n$:

$S_0 \| S_1 := G(R)$

$R := S_{X[i]}$

return $R$