These are used to model block ciphers. The ideal block cipher is a collection $E = \{\pi_1,...,\pi_{2^s}\}$ of random permutations $\pi_i:\{0,1\}^n \rightarrow \{0,1\}^n$, and encryption is described by $C = \pi_k(M)$, where $k$ is the shared key in $\{1,...,2^s\}$, and decryption is $M = \pi_k^{1}(C)$. Of course this is impossible to achieve in practice, so we use pseudo random permutations. We adopt the LubyRackoff definition ['88].
$\pi:\{0,1\}^n \times \{0,1\}^s \rightarrow \{0,1\}^n$ is a $(t,\epsilon,q)$PRP if

For any $K \in \{0,1\}^s$, $\pi_k$ is a onetoone function from $\{0,1\}^n$ to $\{0,1\}^n$.

For any $K \in \{0,1\}^s$, there is an "efficient" algorithm to evaluate $\pi_K(x)$.

For any $t$time algorithm $A$ we have
\[ Pr_{K\leftarrow\{0,1\}^s}[A^{\pi_K}]  Pr_{\sigma\leftarrow\mathcal{P}} [A^\sigma] \lt \epsilon \]where $A$ makes $q$ oracle queries and $\mathcal{P} = \{\pi:\{0,1\}^n \rightarrow\{0,1\}^n, \pi$ a permutation $\}$ is the set of all permutations on $\{0,1\}^n$.
In other words, under a chosen plaintext attack, $\pi_K$ cannot be distinguished from a random permutation. But the definition does not cater for chosen ciphertext attacks, which inspires the following:
$\pi:\{0,1\}^n \times \{0,1\}^s \rightarrow \{0,1\}^n$ is a $(t,\epsilon,q)$SPRP (Strong PRP) if

For any $K \in \{0,1\}^s$, $\pi_k$ is a onetoone function from $\{0,1\}^n$ to $\{0,1\}^n$.

For any $K \in \{0,1\}^s$, there is an "efficient" algorithm to evaluate $\pi_K(x)$ and $\pi_K^{1}(x)$.

For any $t$time algorithm $A$ we have
\[ Pr_{K\leftarrow\{0,1\}^s}[A^{\pi_K , \pi_K^{1}}]  Pr_{\sigma\leftarrow\mathcal{P}} [A^{\sigma,\sigma^{1}}] \lt \epsilon \]where $A$ makes $q$ oracle queries.
Suppose DES is a $(t,\epsilon,q)$PRP. Recall it acts as a permutation on 64 bits at a time. Using DES, can we build a PRP that acts on blocks twice as large, i.e. $\pi:\{0,1\}^{128} \times\{0,1\}^{56}\rightarrow\{0,1\}^{128}$? In general, can we construct large SPRP’s from smaller ones?
LubyRackoff Construction
We show how to construct a PRP from a PRF. Recall that given $L,R \in\{0,1\}^n$ and $f:\{0,1\}^n\rightarrow\{0,1\}^n$, the Feistel permutation is $D_f(LR) = RL \oplus f(R)$. It is clear that $D_f:\{0,1\}^{2n} \rightarrow \{0,1\}^{2n}$ is a permutation.
Theorem: [LR] If $f:\{0,1\}^n\times\{0,1\}^s\rightarrow\{0,1\}^n$ is a $(t,\epsilon,q)$PRF then

$ E^{LR}_{K_1,K_2,K_3} = D_{F_{K_1}}(D_{F_{K_2}}(D_{F_{K_3}})) $ is a $(T,\epsilon+q^2/2^n,q)$PRP.

$ E^{LR}_{K_1,K_2,K_3,K_4} = D_{F_{K_1}}(D_{F_{K_2}}(D_{F_{K_3}}(D_{F_{K_4}}))) $ is a $(T,\epsilon+q^2/2^n,q)$SPRP.
We cannot get away with fewer rounds. A permutation $E$ constructed using only a tworound Feistel network cannot be a PRP, for if we let $E(L,R) = (L',R')$, we would have $E(L\oplus T, R) = (L' \oplus T, R')$, which happens with very low probability for a random permutation.
Similarly, threeround Feistel does not produce SPRP’s. [Exercise]
However, note that with tworound Feistel, $E = D_{f_1}(D_{f_2})$ cannot be distinguished from a random permutation $\{0,1\}^{2n} \rightarrow \{0,1\}^{2n}$ under a known (random) plaintext attack and ciphertext attack, that is, if we are given $\{(x_1, E(x_1)), ..., (x_q,E(x_q))\}$ for random $x_1,...,x_q$. This observation inspires the following:
Define condition (*) as follows: for all $i \ne j, x_i _R \ne x_j _R$, and $E(x_i) _L \ne E(x_j) _L$. (This condition does not hold for the attack on tworound Feistel.)
It turns out that when (*) holds, $\{(x_1, E(x_1), ..., (x_q,E(x_q)\}$ is from the same distribution as $q$ input/output pairs of a random permutation.
In the LubyRackoff construction, the role of $D_{f_1}, D_{f_4}$ is to ensure condition (*) holds for $D_{f_2}(D_{f_3})$. In fact, there is a better way of making sure the condition holds [NR’98]: replace $D_{f_1}, D_{f_4}$ by pairwise independent permutations:
Definition: $H = \{h_\lambda : A \rightarrow A\}_{\lambda\in\Lambda}$ is a family of pairwise independent permutations if $h_\lambda$ is a permutation for any $\lambda\in\Lambda$ and for all $\alpha \ne \beta \in A$, we have
An example of such a family is
is such a family.
Now suppose $f:\{0,1\}^n \times \{0,1\}^s \rightarrow \{0,1\}^n$, and $H = \{h_\lambda : \{0,1\}^{2n} \rightarrow \{0,1\}^{2n}\}_{\lambda\in\Lambda}$. For $M \in \{0,1\}^{2n}$, define
Theorem: If $H$ is a family of pairwise independent permutations and $f$ is a $(t,\epsilon,q)$PRF then $E^{NR}$ is a $(t,2\epsilon + q^2/2^n + q^2/2^{n+1},q)$SPRP for any $q \gt 0$.
So it is secure as long as $q \ll 2^{n/2}$. For example, with DES, $n=32$, so $q \ll 2^{16}$, which is useless. (In contrast, AES has blocksizes of 128, 192 and 256 bits.)
Proof: Let $\mathcal{P}_{2n} = \{ \{0,1\}^{2n} \rightarrow \{0,1\}^{2n}$ permutations $\}$, and write $E$ for $E^NR$. We use a hybrid argument. For all $t$time $A$,
(let us call the three quantities $(1)$, $(2)$ and $(3)$) where $E_1^{\lambda_1,\lambda_2,f_1,f_2} = h_{\lambda_1} ( D_{f_1} ( D_{f_2} ( h_{\lambda_2} )))$ (that is, we replace the PRF’s with random functions) and when $A$ queries $RR^{1}$ and $(RR^{1})^{1}$, consistent random values are returned (i.e. consistent with previous values).
It can be shown that $(1) \le 2\epsilon$, using the definition of PRF. It can also be shown that $(3) \le q^2/2^{2n+1}$ using an information theoretic argument based on the birthday paradox. Lastly, $(2) \le q^2/2^n$, by using the fact that condition (*) holds.
The story so far:
As for the converses, from the first assignment, we know that $PRF \Rightarrow PRNG \Rightarrow \text {oneway functions}$. We would like to know if $PRP \Rightarrow PRF$. This is of practical interest because we would like to take offtheshelf PRP’s such as DES or AES and use them as PRF’s (e.g. for MAC’s).
If we simply use a PRP as a PRF: from above, a $(t,\epsilon,q)$SPRP on $\{0,1\}^n$ is only a $(t,\epsilon+q^2/2^{n+1},q)$PRF (insecure for $q \approx 2^{n/2}$).
Another method[BI’99]: Let $\pi:\{0,1\}^n \times \{0,1\}^s \rightarrow \{0,1\}^n$ be a $(t,\epsilon,q)$PRP. Define $F_{K_1,K_2}(x) = \pi_{K_1}(x) \oplus \pi_{K_2}(x)$. Then $F_{K_1,K_2}$ is a $(t,\epsilon+q/2^n+(q/2^n)^{3/2} n , 2q)$PRF. (i.e. secure until $q \approx 2^n/n^{2/3}$).
Yet another method[BI’99]: Define $F_K(x) = \pi_K(x)_{1...m}$ for some $m \le n$. Then $F_K$ is a $(t,\epsilon+q 2^{m/2}/2^n , q)$PRF for any $q \lt 2^m$. For example, for $m = (2/3)n$, we need $q \ll 2^{2n/3}$ for security.
Now we have a good way of doubling the blocksize of DES. If try to use DES directy in the LR construction we have weak bounds. Instead, we shoould use $DES_{K_1} \oplus DES_{K_2}$.