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 💡