Paper 2015/874

Indifferentiability of 10-Round Feistel Networks

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
block ciphersFeistel network
Contact author(s)
jpsteinb @ gmail com
History
2015-12-17: last of 2 revisions
2015-09-13: received
See all versions
Short URL
https://ia.cr/2015/874
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/874,
      author = {Yuanxi Dai and John Steinberger},
      title = {Indifferentiability of 10-Round Feistel Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2015/874},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/874}},
      url = {https://eprint.iacr.org/2015/874}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.