We consider the cryptographic problem of constructing an invertible random
permutation from a public random function (i.e., which can be accessed by the
adversary). This goal is formalized by the notion of indifferentiability of
Maurer et al. (TCC 2004). This is the natural extension to the public setting
of the well-studied problem of building random permutations from random
functions, which was first solved by Luby and Rackoff (Siam J. Comput., '88)
using the so-called Feistel construction.

The most important implication of such a construction is the equivalence of
the random oracle model (Bellare and Rogaway, CCS '93) and the ideal cipher
model, which is typically used in the analysis of several constructions in
symmetric cryptography.

Coron et al. (CRYPTO 2008) gave a rather involved proof that the six-round
Feistel construction with independent random round functions is
indifferentiable from an invertible random permutation. Also, it is known that
fewer than six rounds do not suffice for indifferentiability. The first
contribution (and starting point) of our paper is a concrete distinguishing
attack which shows that the indifferentiability proof of Coron et al. is not
correct. In addition, we provide supporting evidence that an
indifferentiability proof for the six-round Feistel construction may be very
hard to find.

To overcome this gap, our main contribution is a proof that the Feistel
construction with eigthteen rounds is indifferentiable from an invertible
random permutation. The approach of our proof relies on assigning to each of
the rounds in the construction a unique and specific role needed in the proof.
This avoids many of the problems that appear in the six-round case.