]> Cryptography - Pseudo-Random Permutations

These are used to model block ciphers. The ideal block cipher is a collection $E=\left\{{\pi }_{1},...,{\pi }_{{2}^{s}}\right\}$ of random permutations ${\pi }_{i}:\left\{0,1{\right\}}^{n}\to \left\{0,1{\right\}}^{n}$, and encryption is described by $C={\pi }_{k}\left(M\right)$, where $k$ is the shared key in $\left\{{1,...,2}^{s}\right\}$, and decryption is $M={\pi }_{k}^{-1}\left(C\right)$. Of course this is impossible to achieve in practice, so we use pseudo random permutations. We adopt the Luby-Rackoff definition ['88].

$\pi :\left\{0,1{\right\}}^{n}×\left\{0,1{\right\}}^{s}\to \left\{0,1{\right\}}^{n}$ is a $\left(t,\epsilon ,q\right)$-PRP if

• For any $K\in \left\{0,1{\right\}}^{s}$, ${\pi }_{k}$ is a one-to-one function from $\left\{0,1{\right\}}^{n}$ to $\left\{0,1{\right\}}^{n}$.

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

• For any $t$-time algorithm $A$ we have

$\mid {\mathrm{Pr}}_{K←\left\{0,1{\right\}}^{s}}\left[{A}^{{\pi }_{K}}\right]-{\mathrm{Pr}}_{\sigma ←𝒫}\left[{A}^{\sigma }\right]\mid <\epsilon$

where $A$ makes $q$ oracle queries and $𝒫=\left\{\pi :\left\{0,1{\right\}}^{n}\to \left\{0,1{\right\}}^{n},\pi$ a permutation $\right\}$ is the set of all permutations on $\left\{0,1{\right\}}^{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 :\left\{0,1{\right\}}^{n}×\left\{0,1{\right\}}^{s}\to \left\{0,1{\right\}}^{n}$ is a $\left(t,\epsilon ,q\right)$-SPRP (Strong PRP) if

• For any $K\in \left\{0,1{\right\}}^{s}$, ${\pi }_{k}$ is a one-to-one function from $\left\{0,1{\right\}}^{n}$ to $\left\{0,1{\right\}}^{n}$.

• For any $K\in \left\{0,1{\right\}}^{s}$, there is an "efficient" algorithm to evaluate ${\pi }_{K}\left(x\right)$ and ${\pi }_{K}^{-1}\left(x\right)$.

• For any $t$-time algorithm $A$ we have

$\mid {\mathrm{Pr}}_{K←\left\{0,1{\right\}}^{s}}\left[{A}^{{\pi }_{K},{\pi }_{K}^{-1}}\right]-{\mathrm{Pr}}_{\sigma ←𝒫}\left[{A}^{\sigma ,{\sigma }^{-1}}\right]\mid <\epsilon$

where $A$ makes $q$ oracle queries.

Suppose DES is a $\left(t,\epsilon ,q\right)$-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 :\left\{0,1{\right\}}^{128}×\left\{0,1{\right\}}^{56}\to \left\{0,1{\right\}}^{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 \left\{0,1{\right\}}^{n}$ and $f:\left\{0,1{\right\}}^{n}\to \left\{0,1{\right\}}^{n}$, the Feistel permutation is ${D}_{f}\left(L\mid \mid R\right)=R\mid \mid L\oplus f\left(R\right)$. It is clear that ${D}_{f}:\left\{0,1{\right\}}^{2n}\to \left\{0,1{\right\}}^{2n}$ is a permutation.

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

1. ${E}_{{K}_{1},{K}_{2},{K}_{3}}^{\mathrm{LR}}={D}_{{F}_{{K}_{1}}}\left({D}_{{F}_{{K}_{2}}}\left({D}_{{F}_{{K}_{3}}}\right)\right)$ is a $\left(T,\epsilon +{q}^{2}/{2}^{n},q\right)$-PRP.

2. ${E}_{{K}_{1},{K}_{2},{K}_{3},{K}_{4}}^{\mathrm{LR}}={D}_{{F}_{{K}_{1}}}\left({D}_{{F}_{{K}_{2}}}\left({D}_{{F}_{{K}_{3}}}\left({D}_{{F}_{{K}_{4}}}\right)\right)\right)$ is a $\left(T,\epsilon +{q}^{2}/{2}^{n},q\right)$-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\left(L,R\right)=\left(L\prime ,R\prime \right)$, we would have $E\left(L\oplus T,R\right)=\left(L\prime \oplus T,R\prime \right)$, 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}}\left({D}_{{f}_{2}}\right)$ cannot be distinguished from a random permutation $\left\{0,1{\right\}}^{2n}\to \left\{0,1{\right\}}^{2n}$ under a known (random) plaintext attack and ciphertext attack, that is, if we are given $\left\{\left({x}_{1},E\left({x}_{1}\right)\right),...,\left({x}_{q},E\left({x}_{q}\right)\right)\right\}$ 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\left({x}_{i}\right){\mid }_{L}\ne E\left({x}_{j}\right){\mid }_{L}$. (This condition does not hold for the attack on two-round Feistel.)

It turns out that when (*) holds, $\left\{\left({x}_{1},E\left({x}_{1}\right),...,\left({x}_{q},E\left({x}_{q}\right)\right\}$ 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}}\left({D}_{{f}_{3}}\right)$. 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=\left\{{h}_{\lambda }:A\to A{\right\}}_{\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←H}\left[h\left(x\right)=\alpha \wedge h\left(y\right)=\beta \right]=\frac{1}{\mid A\mid }\frac{1}{\mid A\mid -1}$

An example of such a family is

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

is such a family.

Now suppose $f:\left\{0,1{\right\}}^{n}×\left\{0,1{\right\}}^{s}\to \left\{0,1{\right\}}^{n}$, and $H=\left\{{h}_{\lambda }:\left\{0,1{\right\}}^{2n}\to \left\{0,1{\right\}}^{2n}{\right\}}_{\lambda \in \Lambda }$. For $M\in \left\{0,1{\right\}}^{2n}$, define

${E}_{{\lambda }_{1},{\lambda }_{2},{K}_{1},{K}_{2}}^{\mathrm{NR}}\left(M\right)={h}_{{\lambda }_{1}}\left({D}_{{f}_{{K}_{1}}}\left({D}_{{f}_{{K}_{2}}}\left({h}_{{\lambda }_{2}}\left(M\right)\right)\right)\right)$

Theorem: If $H$ is a family of pairwise independent permutations and $f$ is a $\left(t,\epsilon ,q\right)$-PRF then ${E}^{\mathrm{NR}}$ is a $\left(t,2\epsilon +{q}^{2}/{2}^{n}+{q}^{2}/{2}^{n+1},q\right)$-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}=\left\{\left\{0,1{\right\}}^{2n}\to \left\{0,1{\right\}}^{2n}$ permutaitons $\right\}$, 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}←\left\{0,1{\right\}}^{s},{\lambda }_{1},{\lambda }_{2}←\Lambda }\left[{A}^{{E}_{{K}_{1},{K}_{2},{\lambda }_{1},{\lambda }_{2}},{E}^{-1}}\right]-{\mathrm{Pr}}_{\sigma ←{𝒫}_{2n}}\left[{A}^{\sigma ,{\sigma }^{-1}}\right]\mid \\ & \le & \mid {\mathrm{Pr}}_{{K}_{1},{K}_{2}←\left\{0,1{\right\}}^{s},{\lambda }_{1},{\lambda }_{2}←\Lambda }\left[{A}^{{E}_{{K}_{1},{K}_{2},{\lambda }_{1},{\lambda }_{2}},{E}^{-1}}\right]-{\mathrm{Pr}}_{{f}_{1},{f}_{2}←{ℱ}_{n},{\lambda }_{1},{\lambda }_{2}←\Lambda }\left[{A}^{{E}_{1},{E}_{1}^{-1}}\right]\mid \\ & +& \mid {\mathrm{Pr}}_{{f}_{1},{f}_{2}←{ℱ}_{n},{\lambda }_{1},{\lambda }_{2}←\Lambda }\left[{A}^{{E}_{1},{E}_{1}^{-1}}\right]-\mathrm{Pr}\left[{A}^{{\mathrm{RR}}^{-1},\left({\mathrm{RR}}^{-1}{\right)}^{-1}}\right]\mid \\ & +& \mid \mathrm{Pr}\left[{A}^{{\mathrm{RR}}^{-1},\left({\mathrm{RR}}^{-1}{\right)}^{-1}}\right]-{\mathrm{Pr}}_{\sigma ←{𝒫}_{2n}}\left[{A}^{\sigma ,{\sigma }^{-1}}\right]\mid \end{array}$

(let us call the three quantities $\left(1\right)$, $\left(2\right)$ and $\left(3\right)$) where ${E}_{1}^{{\lambda }_{1},{\lambda }_{2},{f}_{1},{f}_{2}}={h}_{{\lambda }_{1}}\left({D}_{{f}_{1}}\left({D}_{{f}_{2}}\left({h}_{{\lambda }_{2}}\right)\right)\right)$ (that is, we replace the PRF's with random functions) and when $A$ queries ${\mathrm{RR}}^{-1}$ and $\left({\mathrm{RR}}^{-1}{\right)}^{-1}$, consistent random values are returned (i.e. consistent with previous values). [Hence it is not necessarily a permutation.]

It can be shown that $\left(1\right)\le 2\epsilon$, using the definition of PRF. It can also be shown that $\left(3\right)\le {q}^{2}/{2}^{2n+1}$ using an information theoretic argument based on the birthday paradox. Lastly, $\left(2\right)\le {q}^{2}/{2}^{n}$, by using the fact that condition (*) holds.

The story so far:

$\text{one-way function}⇒\text{PRNG (BM)}⇒\text{PRF (GGM)}⇒\text{PRP (LR)}$

As for the converses, from the first assignment, we know that $\mathrm{PRF}⇒\mathrm{PRNG}⇒\text{one-way functions}$. We would like to know if $\mathrm{PRP}⇒\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 $\left(t,\epsilon ,q\right)$-SPRP on $\left\{0,1{\right\}}^{n}$ is only a $\left(t,\epsilon +{q}^{2}/{2}^{n+1},q\right)$-PRF (insecure for $q\approx {2}^{n/2}$).

Another method[BI'99]: Let $\pi :\left\{0,1{\right\}}^{n}×\left\{0,1{\right\}}^{s}\to \left\{0,1{\right\}}^{n}$ be a $\left(t,\epsilon ,q\right)$-PRP. Define ${F}_{{K}_{1},{K}_{2}}\left(x\right)={\pi }_{{K}_{1}}\left(x\right)\oplus {\pi }_{{K}_{2}}\left(x\right)$. Then ${F}_{{K}_{1},{K}_{2}}$ is a $\left(t,\epsilon +q/{2}^{n}+\left(q/{2}^{n}{\right)}^{3/2}n,2q\right)$-PRF. (i.e. secure until $q\approx {2}^{n}/{n}^{2/3}$).

Yet another method[BI'99]: Define ${F}_{K}\left(x\right)={\pi }_{K}\left(x\right){\mid }_{1...m}$ for some $m\le n$. Then ${F}_{K}$ is a $\left(t,\epsilon +q{2}^{m/2}/{2}^{n},q\right)$-PRF for any $q<{2}^{m}$. For example, for $m=\left(2/3\right)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}}$.