The Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited
Speaker: Stefano Tessaro , UC San Diego
Date: December 9 2011
Time: 9:30AM to 11:00AM
Location: 32-G449 Patil/Kiva
Host: Shafi Goldwasser, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
We consider the cryptographic problem of constructing an
invertible random permutation from a public random function (i.e.,
which can be evaluated 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 using the Feistel construction.
The most important implication of such a construction is the
equivalence of the random oracle model and the ideal cipher model.
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 fourteen rounds is indifferentiable from an
invertible random permutation.
Joint work with Thomas Holenstein and Robin Kuenzler (STOC 2011).
See other events that are part of CIS Seminars 2011/2012
See other events happening in December 2011
