Cryptology ePrint Archive: Report 2015/874

Feistel Networks: Indifferentiability at 10 Rounds

Yuanxi Dai and John Steinberger

Abstract: We prove that a (balanced) 10-round Feistel network is indifferentiable from a random permutation. In a previous seminal result, Holenstein et al. had established indifferentiability of Feistel at 14 rounds. Our simulator achieves security $O(q^8/2^n)$ and query complexity $O(q^4)$, where $n$ is half the block length, similarly to the 14-round simulator of Holenstein et al., so that our result is a strict (and also the first) improvement of that work.

Our simulator is very similar to a 10-round simulator of Seurin that was subsequently found to be flawed. Indeed, the main change of our simulator is to switch to "FIFO" path completion from "LIFO" path completion. This relatively minor change results in an overall significant paradigm shift, including a conceptually simpler proof.

Category / Keywords: secret-key cryptography / block ciphers, Feistel network

Date: received 8 Sep 2015

Contact author: jpsteinb at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150913:191639 (All versions of this report)

Short URL: ia.cr/2015/874

Discussion forum: Show discussion | Start new discussion