Cryptography: PRG, PRF and PRP

The main purpose of this post is to show that the three fundamental cryptographic primitives PRG, PRF and PRP are in fact equivalent in the sense of (semantic) security. We shall do this by showing that

• PRG to PRF: using GGM PRF construction
• PRF to PRP: by the Luby-Rackoff Theorem (ie., a 3-round Feistel cipher) 
• PRP to PRG: using counter mode

PRG to PRF

Since PRF is somewhat a "random access" version of PRG, one may want to simulate a PRF $F(k,i)$ by enumerating a PRG $G(k)$ to its $i$th value. However, this design takes exponential time and is thus not satisfactory. There are many method to build an efficient secure PRF out of a secure PRG, and here we present the arguably most intuitive one (which is also the first one): the Goldreich-Goldwasser-Micali construction [GGM'84]. Given a PRG $G:\{0,1\}^m\rightarrow\{0,1\}^{2m}$, let $G_0,G_1$ be the left and right halves of $G$, ie., $G(k)=G_0(k)||G_1(k)$. A PRF $F:\{0,1\}^m \times \{0,1\}^n\rightarrow \{0,1\}^m$ is defined by $$F(k, x_1...x_n) = G_{x_n}(G_{x_{n-1}}(...(G_{x_2}(G_{x_1}(k))...)).$$ The security of the construction can be easily proven by induction on $n$. Its fixed parameter security is given by the following theorem, though we omit the proof due to its technicality:

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

Note that the PRF expansion lemma also implies that one can build a secure PRF out of a secure PRG.

PRP to PRG

Counter mode.

Example. (OTP vs PRF) A one-bit PRF defined by $E(k,m)=k\oplus m$ is secure, since its distribution is exact the set of all one-bit PRPs. However, an $n$-bit PRF defined in similar way is no longer a secure PRF, since $E(k,m_1)\oplus E(k,m_2) = m_1\oplus m_2$ is obviously not random.

Example. (PRP vs PRF) A secure invertible PRF is clearly a secure PRP. A secure PRP, however, may not be a secure PRF, since a PRP must be invertible, and thus is not random when looked upon as a PRF. On the other hand, the PRF Switching Lemma tolds as if the input length is sufficiently large, then a secure PRP is indeed a secure PRF by thr PRF Switching Lemma: Let $E$ be an secure PRP over $(\mathcal K, \mathcal M)$. For an adversary that makes at most $q$ queries, then $$|Adv_{PRF}(A,E)-Adv_{PRP}(A,E)|\le q^2/|\mathcal M|.$$

Exhaustive search attacks

Ideal ciphers

A block cipher is a function $E:\mathcal K \times \mathcal M \rightarrow \mathcal C$. Here we shall let $|\mathcal K| = n$ and $|\mathcal M| = |\mathcal C| = poly(n)$, where $n$ is called the security parameter. A block cipher $E$ is called an ideal cipher if for any $m\in \mathcal M$, $Adv(E(k,m),r)$ is negligible for $r \in_r \{0,1\}^{poly(n)}$ and $k \in_r \mathcal K$. Another characterization of an ideal block cipher $E$ is $\{E(k,m)\} \approx_p \{f_k(m)\}$ for any $m\in \mathcal M$, where ${f_k}$ are a random subset of the family of all invertible functions from $\mathcal M$ to $\mathcal C$. The second characterization is especially helpful, because it allows us to approximate an ideal cipher by a random invertible functions.

Fact. Let $E:\mathcal K\times\mathcal M\rightarrow \mathcal C$ be an ideal cipher. For all $c,m$, the probability that a cipher-text can only be decrypted by the encryption key is $$P\{k'\neq k, E(k',m)=c\} \le \sum_{k'\in\mathcal K,k'\neq k} P\{E(k',m)=c\} \le \frac{|\mathcal K|}{|\mathcal M|}.$$ Assuming that DES is ideal, the probability that one can recover a unique key from $N$ input-output pairs is larger than $1-N2^{56-64N}$. When $n=1$, the probability is roughly 99.5% --- already high enough for an exhaustive search attack to be reasonable.

Attacks on block ciphers

To attack a block cipher $(E,D)$, we are given a few input-output pairs $(m_i, c_i=E(k,m_i))$, $i=1,...,n$ to find the key $k$. The ciphers we are interested here are DES and some of its strengthened versions
DES:   $E(k,m)$ for $k\in \{0,1\}^{56}$, $m\in \{0,1\}^{64}$
2DES: $E^2((k_1,k_2),m) = E(k_2,E(k_1,m))$
3DES: $E^3((k_1,k_2,k_3),m) = E(k_3,D(k_2,E(k_1,m)))$
DX:     $E^x((k_1,k_2,k_3),m) = k_3\oplus E(k_2, k_1\oplus m)$

DES Challenge: Broken by exhaustive search attack since 1997.

2DES Challenge: Given $c,m$, find $k_1,k_2$ such that $E(k_2,E(k_1,m))=c$.

1. Build a sorted table $T$ such that for each $k_1$, $T[k_1]=E(k_1,m)$.
2. For each $k_1$, check whether $D(k_2,c)$ is in the table.

Both steps take $O(56 \cdot 2^{56})=O(2^{62})$ time and $O(2^{56})$ space, which turns out to be the total cost of the attack (called the meet-in-the-middle attack). This complexity is considered tractable with technology of nowadays.

3DES Challenge: Given $c,m$, find $k_1,k_2,k_3$ such that $E(k_3,D(k_2,E(k_1,m)))=c$.

1. Build a sorted table $T$ such that for each $k_1$, $T[k_1]=E(k_1,m)$.
2. For each $k_1,k_2$, check whether $E(k_2,D(k_3,c))$ is in the table.

The first step takes $O(56\cdot 2^{56})$ time and the second step takes $O(56\cdot 2^{56}\cdot 2^{56})=O(2^{118})$ time. Both steps take $O(2^{56})$ space. In practice, we regard a cipher as sufficiently secure if it takes $\omega(2^{90})$ time to compromise. This is why 3DES is widely used today while DES and 2DES are not.

Security of stream ciphers

Perfect Security. A cipher $(E,D)$ over $(\mathcal K, \mathcal M, \mathcal C)$ is called perfectly secure if for all $c\in \mathcal C$, $k \in_r \mathcal K$, and $m_1,m_0\in \mathcal M$ with $|m_1| = |m_0|$, $$P\{ E(k,m_0)=c \} = P\{E(k,m_1)=c \}.$$ The canonical example of perfectly secure cipher is the one-time pad (OTP). This definition of security, however, turns out to be too strict for practical ciphers: It is clear that a necessary condition for perfect security is $|\mathcal K| \ge |\mathcal M|$, since for any $c \in\mathcal C$ and any $m \in\mathcal M$ there must exist $k \in\mathcal K$ such that $E(k,m)=c$. Hence perfect security can be guaranteed only if $|k|=\omega(|m|)$, which made perfectly secure ciphers hard to use in practice. (Recall that a stream cipher uses symmetric key. If we have a secure channel to transfer a key as long as a message, why not using it to transfer the message in the first place?)

Semantic Security. A cipher $(E,D)$ over $(\mathcal K, \mathcal M, \mathcal C)$ is called semantically secure if for $k \in_r \mathcal K$ and all $m_0,m_1\in \mathcal M$ with $|m_0| = |m_1|$, there is no efficient algorithm that can distinguish $E(k,m_0)$ from $E(k,m_1)$ with non-negligible probability. This fact can also be written as $\{E(k, m_0)\} \approx_p \{E(k, m_1)\},$ which means the two distributions are computationally indistinguishable.

Recall that a PRG is secure if it is computational indistinguishable from a true RNG. The following theorem connects the definition of secure PRGs and and the definition of semantic security.

Theorem. A stream cipher derived from a secure PRG is semantically secure.

The intuition of behind the theorem is as follows. It is clear that any stream cipher derived from a true RNG is semantically secure. Therefore, if a PRG derives a stream cipher that is not semantically secure, then there exists an efficient way to distinguish the PRG from a true RNG (i.e., by deriving a stream cipher and then testing the semantic security of the derived cipher), which would imply that the PRG is not secure.

Before we proceed to a formal proof, we need to make the statement ‘‘distinguish A from B’’ more precise. We define the advantage of an adversary $A$ over an algorithm $G$ with respect to $G'$ as $$Adv(A,G,G')=|P\{A(G(X))=1\} - P\{A(G'(Y))=1\}|,$$ where $X$ and $Y$ and random variables. The larger the advantage is, the more capable $A$ can distinguish $G$ from $G'$. With this definition, we see that $G(X) \approx_p G'(Y)$ if and only if $Adv(A,G,G')$ is negligible for all efficient adversaries $A$. We shall write $Adv(A,G)$ for simplicity when $G'$ is clear from the context.
Now suppose that $E$ is a stream cipher derived from PRG $G$.

Proof of the theorem. It suffices to show that for any adversary $A$ for the cipher, there is an adversary $B$ for the PRG such that $Adv(A,E) \le 2Adv(B,G).$ Our approach, which is quite standard in proving results concerning strength of security, is to build adversary $B$ using $A$ as an oracle. Formally, we define $B_i(X)=A(m_i\oplus G(X))$ for $i\in \{0,1\}$ and let $B=B_j$ where $j=\arg\max_i\{Adv(B_i,G) \}$. The construction of $B_0$ is illustrated as follows.

When $Y$ is uniformly random, there is no way to tell $m_0\oplus Y$ from $m_1 \oplus Y$, and thus $P\{A(m_0\oplus Y)=1\} = P\{A(m_1 \oplus Y)=1\}$. Now, note that

$Adv(A,E)=|P\{A(m_0 \oplus G(X))=1\} - P\{A(m_1 \oplus G(X))=1\}| \\ = |P\{A(m_0 \oplus G(X))=1\} - P\{A(m_0 \oplus Y)=1\} + P\{A(m_1 \oplus Y)=1\} - P\{A(m_1 \oplus G(X))=1\}| \\ \le |P\{A(m_0 \oplus G(X))=1\} - P\{A(m_0 \oplus Y)=1\}| + |P\{A(m_1 \oplus Y)=1\} - P\{A(m_1 \oplus G(X))=1\}| \\ =Adv(B_0,G) + Adv(B_1,G) \le 2Adv(B,G).$

This completes the proof. $\square$