# Pseudo-Random Permutations

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

Ben Lynn blynn@cs.stanford.edu 💡