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].