Luby-Rackoff Ciphers from Weak Round Functions?

The Feistel-network is a popular structure underlying many block-ciphers where the cipher is constructed from many simpler rounds, each defined by some function which is derived from the secret key.

Luby and Rackoff showed that the three-round Feistel-network – each round instantiated with a pseudorandom function secure against adaptive chosen plaintext attacks (

CPA

) – is a

CPA

secure pseudorandom permutation, thus giving some confidence in the soundness of using a Feistel-network to design block-ciphers.

But the round functions used in actual block-ciphers are – for efficiency reasons – far from being pseudorandom. We investigate the security of the Feistel-network against

CPA

distinguishers when the only security guarantee we have for the round functions is that they are secure against non-adaptive chosen plaintext attacks (

nCPA

). We show that in the information-theoretic setting, four rounds with

nCPA

secure round functions are sufficient (and necessary) to get a

CPA

secure permutation. Unfortunately, this result does not translate into the more interesting pseudorandom setting. In fact, under the so-called Inverse Decisional Diffie-Hellman assumption the Feistel-network with four rounds, each instantiated with a

nCPA

secure pseudorandom function, is in general not a

CPA

secure pseudorandom permutation.