Luby-Rackoff construction

From CRYPTUTOR

The Luby-Rackoff construction is a construction of a (strong) pseudorandom permutation from any pseudorandom function. Its main component is a Feistel network.

[edit]

Construction

Given any pseudorandom function $F: \{0,1\}^k \times \{0,1\}^{\ell(k)} \to \{0,1\}^{\ell(k)}$ , the 3-layer Feistel network with round functions $F_{s_1}, F_{s_2}, F_{s_3}$ is a pseudorandom permutation. We view $(s_1, s_2, s_3)\,$ as the $3 k$ -bit seed of this pseudorandom permutation. It is important that the three PRF round functions have independently chosen seeds.

Additionally, if we extend the construction to a 4-layer Feistel network (with 4 independently chosen seeds for the round functions), the construction is a strong pseudorandom permutation. Surprisingly, 2 layers do not suffice to construct a standard pseudorandom permutation, and 3 layers do not suffice to construct a strong pseudorandom permutation.

[edit]