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