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\).

The proof on this page.

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:

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

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\),

\[ 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 \]