CS276 Lecture 15 (draft)

Summary

Today we give a construction of a pseudorandom permutation (block cipher) given a pseudorandom function, and we begin its analysis.

1. Feistel Permutations

Let ${F:\{ 0,1 \}^m \rightarrow \{ 0,1 \}^m}$ be a function. We define the Feistel permutation ${D_F: \{ 0,1 \}^{2m} \rightarrow \{ 0,1 \}^{2m}}$ associated with ${F}$ as

$\displaystyle D_F(x,y) := y, x\oplus F(y) \ \ \ \ \ (1)$

Note that this is an injective (and hence bijective) function, because its inverse is given by

$\displaystyle D^{-1} _F(z,w) := F(z) \oplus w ,z$

Also, note that ${D_F}$ and ${D^{-1}_F}$ are efficiently computable given ${F}$ .

Unfortunately, it is clear that, even if ${F_K}$ is a pseudorandom function, then ${D_{F_K}}$ does not look like a random permutation: ${D_{F_K}(0^{2m})}$ is zero in half of its bits. (By ${0^{2m}}$ we mean a sequence of ${m}$ zeroes.)

Also, even repeating the construction twice does not help. If we pick two random keys ${K_1,K_2}$ , and consider the permutation ${P(x) := D_{F_{K_2}} (D_{F_{K_1}} (x) )}$ , then ${P}$ does not look like a random permutation: consider ${P(0^{2m})}$ and ${P (1^m,0^m)}$ , and notice that the first ${m}$ bits of the first string are the complement of the first ${m}$ bits of the second string.

What happens if we repeat the construction three times? We still do not get a pseudorandom permutation.

Exercise 1 (Not Easy) Show that there is an efficient oracle algorithm ${A}$ such that

$\displaystyle \mathop{\mathbb P}_{\Pi : \{ 0,1 \}^{2m} \rightarrow \{ 0,1 \}^{2m} } [ A^{\Pi,\Pi^{-1} } () = 1] = 2^{-\Omega(m) }$

where ${\Pi}$ is a random permutation, but for every three functions ${F_1,F_2,F_3}$ , if we define ${P(x) := D_{F_3} (D_{F_2} ( D_{F_1} (x )))}$ we have

$\displaystyle A^{P,P^{-1} } () = 1$

Finally, however, if we repeat the construction four times, with four independent pseudorandom functions, we get a pseudorandom permutation.

2. The Luby-Rackoff Construction

Let ${F: \{ 0,1 \}^k \times \{ 0,1 \}^m \rightarrow \{ 0,1 \}^m}$ be a pseudorandom function, we define the following function ${P: \{ 0,1 \}^{4k} \times \{ 0,1 \}^{2m} \rightarrow \{ 0,1 \}^{2m}}$ : given a key ${\overline K (K_1,\ldots,K_4)}$ and an input ${x}$ ,

$\displaystyle P_{\overline K} (x) := D_{F_{K_4}} ( D_{F_{K_3}} ( D_{F_{K_2}} (D_{F_{K_1}} (x ))))\ \ \ \ \ (2)$

Theorem 1 If ${F}$ is a ${(O(tr),\epsilon)}$ -secure pseudorandom function computable in time ${r}$ , then ${P}$ is a ${(t, 4\epsilon + t^2 \cdot 2^{-m} + t^2 \cdot 2^{-2m} )}$ secure pseudorandom permutation.

3. Analysis of the Luby-Rackoff Construction

Given four random functions ${\overline R = (R_1,\ldots,R_4)}$ , ${R_i: \{ 0,1 \}^m \rightarrow \{ 0,1 \}^m}$ , let ${P_{\overline R}}$ be the analog of Construction (2) using the random function ${R_i}$ instead of the pseudorandom functions ${F_{K_i}}$ ,

$\displaystyle P_{\overline{R}} (x) = D_{{R_4}} ( D_{{R_3}} ( D_{{R_2}} (D_{{R_1}} (x )))) \ \ \ \ \ (3)$

We prove Theorem 1 by showing that

${P_{\overline K}}$ is indistinguishable from ${P_{\overline R}}$ or else we can break the pseudorandom function
${P_{\overline R}}$ is indistinguishable from a random permutation

The first part is given by the following lemma, which we prove via a standard hybrid argument.

Lemma 2 If ${F}$ is a ${(O(tr),\epsilon)}$ -secure pseudorandom function computable in time ${r}$ , then for every algorithm ${A}$ of complexity ${\leq t}$ we have

$\displaystyle \left | \mathop{\mathbb P}_{\overline {K} } [ A^{P_{\overline{K}}, P^{-1} _{\overline{K}} } () =1 ] \right.$

$\displaystyle - \left. \mathop{\mathbb P}_{\overline {R} } [ A^{P_{\overline{R}}, P^{-1} _{\overline{R}} } () =1 ] \right| \leq 4\epsilon$

And the second part is given by the following lemma:

Lemma 3 For every algorithm ${A}$ of complexity ${\leq t}$ we have

$\displaystyle \left| \mathop{\mathbb P}_{\overline {R} } [ A^{P_{\overline{R}}, P^{-1} _{\overline{R}} } () =1 ] - \mathop{\mathbb P}_{\Pi} [ A^{\Pi, \Pi^{-1} } () = 1] \right| \leq \frac{t^2}{ 2^{2m}} + \frac {t^2}{ 2^{m}}$

where ${\Pi : \{ 0,1 \}^{2m} \rightarrow \{ 0,1 \}^{2m}}$ is a random permutation.

We say that an algorithm ${A}$ is non-repeating if it never makes an oracle query to which it knows the answer. (That is, if ${A}$ is interacting with oracles ${g,g^{-1}}$ for some permutation ${g}$ , then ${A}$ will not ask twice for ${g(x)}$ for the same ${x}$ , and it will not ask twice for ${g^{-1}(y)}$ for the same ${y}$ ; also, after getting the value ${y=g(x)}$ in an earlier query, it will not ask for ${g^{-1} (y)}$ later, and after getting ${w=g^{-1} (z)}$ it will not ask for ${g(w)}$ later. )

We shall prove Lemma 3 for non-repeating algorithms. The proof can be extended to arbitrary algorithms with some small changes. Alternatively, we can argue that an arbitrary algorithm can be simulated by a non-repeating algorithm of almost the same complexity in such a way that the algorithm and the simulation have the same output given any oracle permutation.

In order to prove Lemma 3 we introduce one more probabilistic experiment: we consider the probabilistic algorithm ${S(A)}$ that simulates ${A()}$ and simulates every oracle query by providing a random answer. (Note that the simulated answers in the computation of ${SA}$ may be incompatible with any permutation.)

We first prove the simple fact that ${S(A)}$ is close to simulating what really happen when ${A}$ interacts with a truly random permutation.

Lemma 4 Let ${A}$ be a non-repeating algorithm of complexity at most ${t}$ . Then

$\displaystyle \left| \mathop{\mathbb P} [ S(A) =1 ] - \mathop{\mathbb P}_{\Pi} [ A^{\Pi, \Pi^{-1} } () = 1] \right| \leq \frac{t^2}{ 2 \cdot 2^{2m}}$

where ${\Pi : \{ 0,1 \}^{2m} \rightarrow \{ 0,1 \}^{2m}}$ is a random permutation.

Finally, it remains to prove:

Lemma 5 For every non-repating algorithm ${A}$ of complexity ${\leq t}$ we have

$\displaystyle \left| \mathop{\mathbb P}_{\overline {R} } [ A^{P_{\overline{R}}, P^{-1} _{\overline{R}} } () =1 ] - \mathop{\mathbb P} [ S(A) = 1] \right| \leq \frac{t^2}{ 2\cdot 2^{2m}} + \frac {t^2}{ 2^{m}}$

We shall prove Lemma 5 next time.

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

CS276 Lecture 15 (draft)

Leave a Reply

Share this:

Like this:

Related

Leave a Reply