Paper 2015/903

A Note on the Indifferentiability of the 10-Round Feistel Construction

Yannick Seurin

Abstract

Holenstein et al. (STOC 2011) have shown that the Feistel construction with fourteen rounds and public random round functions is indifferentiable from a random permutation. In the same paper, they pointed out that a previous proof for the 10-round Feistel construction by Seurin (PhD thesis) was flawed. However, they left open the question of whether the proof could be patched (leaving hope that the simulator described by Seurin could still be used to prove indifferentiability of the 10-round Feistel construction). In this note, we show that the proof cannot be patched (and hence that the simulator described by Seurin cannot be used to prove the indifferentiability of the 10-round Feistel construction) by describing a distinguishing attack that succeeds with probability close to one against this simulator. We stress that this does not imply that the 10-round Feistel construction is not indifferentiable from a random permutation (since our attack does not exclude the existence of a different simulator that would work).

Note: This paper dates back to March 2011 and was never published except on my personal webpage. Since there is some renewed interest in proving the indifferentiability of the 10-round Feistel construction (ePrint reports 2015/874 and 2015/876), I decided to upload it here.