CS276 Lecture 16 (draft)

Today we finish the analysis of a construction of a pseudorandom permutation (block cipher) given a pseudorandom function.

Recall that if {F:\{ 0,1 \}^m \rightarrow \{ 0,1 \}^m} is a function, then 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)

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)

If {\overline F = F_1,F_2,F_3,F_4} are four functions, then {P_{\overline F}} is the same as the above construction but using the functions {F_i}:

\displaystyle   P_{\overline F} (x) := D_{F_{4}} ( D_{F_{3}} ( D_{F_{2}} (D_{F_{1}} (x ))))\ \ \ \ \ (3)

If {A} is an oracle algorithm, we define as {S(A)} the probabilistic process in which we run a simulation of {A} in which we reply to each query with a random answer.

The proof of the following result is what was missing from yesterday’s analysis.

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

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

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s