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 Luby-Rackoff 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 one-to-one 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 one-to-one 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?

Luby-Rackoff 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(L||R) = R||L \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

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

  2. $ 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 two-round 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, three-round Feistel does not produce SPRP’s. [Exercise]

However, note that with two-round 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 two-round 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 Luby-Rackoff 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

\[Pr_{h\leftarrow H}[h(x) = \alpha \wedge h(y) =\beta] = \frac{1}{|A|}\frac{1}{|A|-1} \]

An example of such a family is

\[ H = \{h_{a,b} (x) = ax+b \mod p\}_{a \in \mathbb{F}_p^*, b\in\mathbb{F}_p^*}, h_{a,b}: \mathbb{F}_p \rightarrow \mathbb{F}_p, |H| = p(p-1) \]

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

\[ E^{NR}_{\lambda_1,\lambda_2,K_1,K_2}(M) = h_{\lambda_1} ( D_{f_{K_1}} (D_{f_{K_2}} ( h_{\lambda_2} (M) ) ) ) \]

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

\[ \array { & & | Pr_{K_1,K_2 \leftarrow \{0,1\}^s, \lambda_1,\lambda_2 \leftarrow \Lambda} [A^{E_{K_1,K_2,\lambda_1,\lambda_2},E^{-1}}] - Pr_{\sigma\leftarrow\mathcal{P}_{2n}}[A^{\sigma,\sigma^{-1}}] | \\ &\le& |Pr_{K_1,K_2\leftarrow\{0,1\}^s,\lambda_1,\lambda_2\leftarrow\Lambda} [A^{E_{K_1,K_2,\lambda_1,\lambda_2},E^{-1}}] - Pr_{f_1,f_2\leftarrow\mathcal{F}_n, \lambda_1,\lambda_2\leftarrow\Lambda} [A^{E_1,E_1^{-1}}]| \\ &+& |Pr_{f_1,f_2\leftarrow\mathcal{F}_n,\lambda_1,\lambda_2\leftarrow\Lambda} [A^{E_1,E_1^{-1}}] - Pr[A^{RR^{-1},(RR^{-1})^{-1}}]| \\ &+& |Pr[A^{RR^{-1},(RR^{-1})^{-1}}] - Pr_{\sigma\leftarrow\mathcal{P}_{2n}}[A^{\sigma,\sigma^{-1}}]| } \]

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

\[ \text {one-way function} \Rightarrow \text {PRNG (BM)} \Rightarrow \text {PRF (GGM)} \Rightarrow \text {PRP (LR)} \]

As for the converses, from the first assignment, we know that $PRF \Rightarrow PRNG \Rightarrow \text {one-way functions}$. We would like to know if $PRP \Rightarrow PRF$. This is of practical interest because we would like to take off-the-shelf 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}$.