Indifferentiability of 10-Round Feistel Networks
Yuanxi Dai, John P. Steinberger · 2015
We prove that a (balanced) 10-round Feistel network is indifferentiable from a random permutation. In a previous seminal result, Holenstein et al. [17] had established indifferentiability of Feistel at 14 rounds. Our simulator achieves security O(q/2), runtime O(q) and query complexity O(q), to be compared with security O(q/2), runtime O(q) and query complexity O(q) for the 14-round simulator of Holenstein et al. Our simulator is very similar to a 10-round simulator of Seurin [29] that was subsequently found to be flawed [17, 30]. Indeed, our simulator is essentially obtained by switching from a “FIFO” path completion order to a “LIFO” path completion order in Seurin’s simulator. This apparently minor change results in a significant paradigm shift, including a conceptually simpler proof.