Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited

Details Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited

2010-11-04

arxiv.org/abs/1011.1264v2

Computer Science

Cryptography and Security

Reduced number of rounds from 18 to 14 as this is sufficient for the proof, improved presentation of several lemmas and introd

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-453024