Cryptography

We show how to construct a PRP from a PRF. Recall that given $L,R\in \{\mathrm{0,1}{\}}^n$ and $f:\{\mathrm{0,1}{\}}^n\to \{\mathrm{0,1}{\}}^n$, the Feistel permutation is $D_f(L\mid \mid R)=R\mid \mid L\oplus f(R)$. It is clear that $D_f:\{\mathrm{0,1}{\}}^{2n}\to \{\mathrm{0,1}{\}}^{2n}$ is a permutation.

Theorem: [LR] If $f:\{\mathrm{0,1}{\}}^n\times \{\mathrm{0,1}{\}}^s\to \{\mathrm{0,1}{\}}^n$ is a $(t,\epsilon ,q)$-PRF then

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

2. $E_{K_1,K_2,K_3,K_4}^{\mathrm{LR}}=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\prime ,R\prime )$, we would have $E(L\oplus T,R)=(L\prime \oplus T,R\prime )$, 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 $\{\mathrm{0,1}{\}}^{2n}\to \{\mathrm{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{\mid }_R\ne x_j{\mid }_R$, and $E(x_i){\mid }_L\ne E(x_j){\mid }_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\to 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

$${\mathrm{Pr}}_{h\leftarrow H}[h(x)=\alpha \wedge h(y)=\beta ]=\frac{1}{\mid A\mid }\frac{1}{\mid A\mid -1}$$

An example of such a family is

$$H=\{h_{a,b}(x)=\mathrm{ax}+bmodp{\}}_{a\in {𝔽}_p^{*},b\in {𝔽}_p^{*}},h_{a,b}:{𝔽}_p\to {𝔽}_p,\mid H\mid =p(p-1)$$

is such a family.

Now suppose $f:\{\mathrm{0,1}{\}}^n\times \{\mathrm{0,1}{\}}^s\to \{\mathrm{0,1}{\}}^n$, and $H=\{h_{\lambda }:\{\mathrm{0,1}{\}}^{2n}\to \{\mathrm{0,1}{\}}^{2n}{\}}_{\lambda \in \Lambda }$. For $M\in \{\mathrm{0,1}{\}}^{2n}$, define

$$E_{{\lambda }_1,{\lambda }_2,K_1,K_2}^{\mathrm{NR}}(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^{\mathrm{NR}}$ is a $(t\mathrm{,2}\epsilon +q^2/2^n+q^2/2^{n+1},q)$-SPRP for any $q>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 ${𝒫}_{2n}=\{\{\mathrm{0,1}{\}}^{2n}\to \{\mathrm{0,1}{\}}^{2n}$ permutaitons $\}$, and write $E$ for $E^{\mathrm{NR}}$. We use a hybrid argument. For all $t$-time $A$,

$$\begin{array}{ccc}& & \mid {\mathrm{Pr}}_{K_1,K_2\leftarrow \{\mathrm{0,1}{\}}^s,{\lambda }_1,{\lambda }_2\leftarrow \Lambda }[A^{E_{K_1,K_2,{\lambda }_1,{\lambda }_2},E^{-1}}]-{\mathrm{Pr}}_{\sigma \leftarrow {𝒫}_{2n}}[A^{\sigma ,{\sigma }^{-1}}]\mid \\ & \le & \mid {\mathrm{Pr}}_{K_1,K_2\leftarrow \{\mathrm{0,1}{\}}^s,{\lambda }_1,{\lambda }_2\leftarrow \Lambda }[A^{E_{K_1,K_2,{\lambda }_1,{\lambda }_2},E^{-1}}]-{\mathrm{Pr}}_{f_1,f_2\leftarrow {ℱ}_n,{\lambda }_1,{\lambda }_2\leftarrow \Lambda }[A^{E_1,E_1^{-1}}]\mid \\ & +& \mid {\mathrm{Pr}}_{f_1,f_2\leftarrow {ℱ}_n,{\lambda }_1,{\lambda }_2\leftarrow \Lambda }[A^{E_1,E_1^{-1}}]-\mathrm{Pr}[A^{{\mathrm{RR}}^{-1},({\mathrm{RR}}^{-1}{)}^{-1}}]\mid \\ & +& \mid \mathrm{Pr}[A^{{\mathrm{RR}}^{-1},({\mathrm{RR}}^{-1}{)}^{-1}}]-{\mathrm{Pr}}_{\sigma \leftarrow {𝒫}_{2n}}[A^{\sigma ,{\sigma }^{-1}}]\mid \end{array}$$

(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 ${\mathrm{RR}}^{-1}$ and $({\mathrm{RR}}^{-1}{)}^{-1}$, consistent random values are returned (i.e. consistent with previous values). [Hence it is not necessarily a permutation.]

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 $\mathrm{PRF}\Rightarrow \mathrm{PRNG}\Rightarrow \text{one-way functions}$. We would like to know if $\mathrm{PRP}\Rightarrow \mathrm{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 $\{\mathrm{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 :\{\mathrm{0,1}{\}}^n\times \{\mathrm{0,1}{\}}^s\to \{\mathrm{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){\mid }_{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<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 ${\mathrm{DES}}_{K_1}\oplus {\mathrm{DES}}_{K_2}$.