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