PseudoRandom 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 pseudorandom 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
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)\).
GoldreichGoldwasserMicali
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
Theorem: If \(G\) is a \((t,\epsilon)\)PRNG then \(F\) is a \((tcn,\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
The running time is roughly two exponentiations.
Theorem: If \(G\) satisfies the \((t,\epsilon)\)DDH assumption then \(F\) is a \((tcn,\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 oneway permutations.
PRF’s as MAC’s
Recall a MAC is a pair of algorithms \((MAC, MACverify)\) 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\).

\(MACverify(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:

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

The adversary asks for the MACs of messages \(M_i\) for \(1\le i \le q\).

The adversary sends \(\langle M, T \rangle\) where \(M \ne M_i\) for any \(1 \le i \le q\) and wins if \(MACverify(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

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

For all \(t\)time algorithms \(A\) that make at most \(q\) queries to \(f\),
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 GoldreichLevin method: \(F'_{K,R} = \langle F_K(X), R\rangle \in \{0,1\}\).
Enlarging the domain of PRF’s
Recall that CBCF for a keyed function \(F\) on a message \(M\) is defined as follows. Break \(M\) into blocks \(M_i\). Then
*Theorem: *[BRK’92] (Security of CBCMAC)
Let \(F:\{0,1\}^n \times \{0,1\}^s \rightarrow \{0,1\}^T\) be a \((t,\epsilon,q)\)PRF. Then \(CBCF(M_1,...,M_b)\) is a \((t,\epsilon+q^2 b^2 / 2^{n1} ,q/b)\)PRF.
Intuitively, CBCF 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 collisionresistant hash function. Then
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
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
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].