# Pseudo-Random Functions

Suppose Alice wishes to authenticate herself to Bob, by proving she knows a secret that they share. With PRNG’s they could proceed as follows. They both seed a PRNG with the shared secret. Bob picks sends Alice some random number $$i$$, and Alice proves she knows the share secret by responding with the $$i$$th random number generated by the PRNG.

But this solution requires state, and they both have to compute $$i$$ random numbers. Instead, we would like "random access" to the sequence. This is the intuition behind pseudo-random functions: Bob gives alice some random $$i$$, and Alice returns $$F_K(i)$$, where $$F_K(i)$$ is indistinguishable from a random function, that is, given any $$x_1,...,x_m,F_K(x_1),...,F_K(x_m)$$, no adversary can predict $$F_K(x_{m+1})$$ for any $$x_{m+1}$$

Definition: a function $$f:\{0,1\}^n \times \{0,1\}^s\rightarrow\{0,1\}^m$$ is a $$(t,\epsilon,q)$$-PRF if

• Given a key $$K\in\{0,1\}^s$$ and an input $$X\in\{0,1\}^n$$ there is an "efficient" algorithm to compute $$F_K(X) = F(X, K)$$.

• For any $$t$$-time oracle algorithm $$A$$, we have

$|Pr_{K\leftarrow\{0,1\}^s}[A^{f_K}] - Pr_{f\in\mathcal{F}}[A^f]| \lt \epsilon$

where $$\mathcal{F} = \{f:\{0,1\}^n\rightarrow\{0,1\}^m\}$$ and $$A$$ makes at most $$q$$ queries to the oracle.

PRF’s can also be used for symmetric encryption: pick random $$R$$, then output $$E_K(M) = \langle F_K(R) \oplus M, R\rangle$$ (roughly speaking, if $$F$$ is a PRF, then $$E$$ is semantically secure). They are also can be used as MAC’s: $$MAC_K(M) = F_K(M)$$.

## Goldreich-Goldwasser-Micali

PRNG’s can be used to construct PRF’s [GGM’84]. Let $$G:\{0,1\}^s\rightarrow\{0,1\}^{2s}$$ be a PRNG. Define $$G_0,G_1$$ to be the left and right halves of $$G$$, so that $$G(X)=G_0(X)||G_1(X)$$. For any $$K \in \{0,1\}^s$$, define $$F_K:\{0,1\}^n\rightarrow\{0,1\}^s$$ by

$F_K(x_1...x_n) = G_{x_n}(G_{x_{n-1}}(...(G_{x_2}(G_{x_1}(K))...))$

Theorem: If $$G$$ is a $$(t,\epsilon)$$-PRNG then $$F$$ is a $$(t-cn,\epsilon q n,q)$$-PRF for some constant $$c$$.

## A Number Theoretic PRF

It is possible to construct a PRF based on the DDH assumption [NR’96]. Let $$G$$ be a cyclic group of prime order $$q$$ generated by $$g$$. Then a key has the form $$\bar{K} = (K_0,...,K_n)\in\mathbb{Z}_q^{n+1}$$, and for $$X \in \{0,1\}^n$$, define

$F_K(X)=F_K(x_1 ... x_n) = g^{K_0 \prod_{i=1}^n K_i^{x_i}}$

The running time is roughly two exponentiations.

Theorem: If $$G$$ satisfies the $$(t,\epsilon)$$-DDH assumption then $$F$$ is a $$(t-cn,\epsilon Q n,Q)$$-PRF for some constant $$c$$.

## A Parallel PRF

The following construction [NR’95] can be evaluated efficiently in parallel. The seed is $$[a_{1,0}, a_{1,1},...,a_{n,0},a_{n,1} \in \{0,1\}^s]$$. Then to compute $$F^{NR}(x_1 ... x_n)$$, start with $$a_{1,x_1} a_{2,x_2} ... a_{n,x_n}$$, and squish pairs of strings together using $$S : \{0,1\}^s \times \{0,1\}^s \rightarrow \{0,1\}^s$$. Then take the $$n/2$$ outputs and squish them in pairs again. Then repeat the process until there is one string in $$\{0,1\}^s$$ left.

When $$S$$ is a synthesizer, $$F^NR$$ is a PRF. It turns out trapdoor permutations imply synthesizers. An open problem is to construct a parallel PRF from one-way permutations.

## PRF’s as MAC’s

Recall a MAC is a pair of algorithms $$(MAC, MAC-verify)$$ such that

• $$MAC_K(M) : \{0,1\}^m \times \{0,1\}^s \rightarrow \{0,1\}^T$$ is an "efficient" algorithm, where the tag length $$T \ll n$$.

• $$MAC-verify(M,T,K)$$ is an "efficient" predicate.

The $$MAC$$ algorithm may be randomized.

Security: A MAC is $$(t,\epsilon,q)$$-secure if no $$t$$-time algorithm can succeed with probability more than $$\epsilon$$ in existentially forging a MAC with a $$q$$-chosen message attack. In more detail, consider the following game:

1. The challenger picks a random $$K \leftarrow \{0,1\}^s$$.

2. The adversary asks for the MACs of messages $$M_i$$ for $$1\le i \le q$$.

3. The adversary sends $$\langle M, T \rangle$$ where $$M \ne M_i$$ for any $$1 \le i \le q$$ and wins if $$MAC-verify(M,T,K)$$ is true.

The MAC is $$(t,\epsilon,q)$$-secure if for all $$t$$-time adversaries $$A$$ we have $$Pr[A wins] \lt \epsilon$$.

It is easily seen that if $$F$$ is a $$(t,\epsilon,q)$$-PRF then $$F$$ is also a $$(t,\epsilon + 1/2^T,q)$$-MAC.

Thus PRF’s imply (deterministic) MAC’s, but the converse is not true. For example, if $$F$$ is a $$(t,\epsilon,q)$$-PRF then $$MAC_K(M) = F_K(M)||1$$ is a $$(t,\epsilon+1/2^T,q)$$-MAC but not a PRF. In some sense, PRF’s are overkill for MAC’s. This motivates the following definition.

## Unpredictable Functions

A function $$f:\{0,1\}^n \times \{0,1\}^s \rightarrow \{0,1\}^T$$ is a $$(t,\epsilon,q)$$-unpredictable function if

1. Given $$K \in \{0,1\}^s$$, $$f_K(x)$$ can be "efficiently" computed.

2. For all $$t$$-time algorithms $$A$$ that make at most $$q$$ queries to $$f$$,

$Pr_{K\leftarrow\{0,1\}^s}[A^{f_K} = (M,Tag), f_K(M) = Tag] \lt \epsilon$

where $$A$$ did not query the oracle at $$M$$.

Every PRF is an UF, but not conversely. However, PRF’s can be constructed from UF’s via the Goldreich-Levin method: $$F'_{K,R} = \langle F_K(X), R\rangle \in \{0,1\}$$.

## Enlarging the domain of PRF’s

Recall that CBC-F for a keyed function $$F$$ on a message $$M$$ is defined as follows. Break $$M$$ into blocks $$M_i$$. Then

$CBC-F(M) = F_K(...F_K(F_K(F_K(M_1) \oplus M_2) \oplus M_3) ...)$

*Theorem: *[BRK’92] (Security of CBC-MAC)

Let $$F:\{0,1\}^n \times \{0,1\}^s \rightarrow \{0,1\}^T$$ be a $$(t,\epsilon,q)$$-PRF. Then $$CBC-F(M_1,...,M_b)$$ is a $$(t,\epsilon+q^2 b^2 / 2^{n-1} ,q/b)$$-PRF.

Intuitively, CBC-F is secure if $$b \ll 2^{n/2}/q$$. For larger $$b$$ there is a known attack (birthday attack).

## Enlarging the domain of UF’s

We present three methods for doing this.

Theorem 1: Let $$F:\{0,1\}^n\times\{0,1\}^s\rightarrow\{0,1\}^T$$ be a $$(t,\epsilon,q)$$-UF, and let $$H:\{0,1\}^*\rightarrow\{0,1\}^n$$ be a collision-resistant hash function. Then

$HMAC_K(M) = F_K(H(M))$

is a $$(t,\epsilon,q)$$-UF.

Theorem 2: Let $$f:\{0,1\}^n\times\{0,1\}^s\rightarrow\{0,1\}^T$$ be a $$(t,\epsilon,q)$$-PRF, and let $$H=\{h_K:\{0,1\}^N\rightarrow\{0,1\}^n$$ be a family of hash functions such that for all $$x\ne y \in \{0,1\}^N$$, we have $$Pr_{h\leftarrow H}[h(x) = h(y)] \lt \epsilon'$$. Then

$HF_{K_1,K_2}(M) = f_{K_1}(h_{K_2}(M))$

is a $$(t,\epsilon+\epsilon',q)$$-MAC.

Theorem 3: Let $$f:\{0,1\}^n\times\{0,1\}^s\rightarrow\{0,1\}^T$$ be a $$(t,\epsilon,q)$$-PRF, and let $$H=\{h_K:\{0,1\}^N\rightarrow\{0,1\}^n$$ be a family of hash functions such that for all $$x, y \in \{0,1\}^N$$ and for all $$r \in {0,1}^T$$, we have $$Pr_{h\leftarrow H}[h(x) \oplus h(y) = r] \lt \epsilon'$$. Then

$CWH_{K_1,K_2}(M) = [h_{K_2}(M) \oplus f_{K_1}(R), R], R\leftarrow\{0,1\}^n$

is a $$(t,\epsilon+\epsilon',q)$$-MAC.

Note the last theorem involves a nondeterministic MAC. In short, for a secure MAC, we can do PRF(UHF), or UF(CRHF) (so weaken the requirements on one function but strengthen the requirements on the other), or [UHF(M) $$\oplus$$ PRF®, R].

Ben Lynn blynn@cs.stanford.edu 💡