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

  1. {P_{\overline K}} is indistinguishable from {P_{\overline R}} or else we can break the pseudorandom function

  2. {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.

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s