International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks

Authors:
Patrick Derbez , Université de Rennes 1, CNRS, IRISA, Rennes, France
Pierre-Alain Fouque , Université de Rennes 1, CNRS, IRISA, Rennes, France
Baptiste Lambin , Université de Rennes 1, CNRS, IRISA, Rennes, France
Victor Mollimard , Université de Rennes 1, CNRS, IRISA, Rennes, France
Download:
DOI: 10.13154/tosc.v2019.i2.218-240
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8321
Search ePrint
Search Google
Abstract: The Feistel construction is one of the most studied ways of building block ciphers. Several generalizations were then proposed in the literature, leading to the Generalized Feistel Network, where the round function first applies a classical Feistel operation in parallel on an even number of blocks, and then a permutation is applied to this set of blocks. In 2010 at FSE, Suzaki and Minematsu studied the diffusion of such construction, raising the question of how many rounds are required so that each block of the ciphertext depends on all blocks of the plaintext. They thus gave some optimal permutations, with respect to this diffusion criteria, for a Generalized Feistel Network consisting of 2 to 16 blocks, as well as giving a good candidate for 32 blocks. Later at FSE’19, Cauchois et al. went further and were able to propose optimal even-odd permutations for up to 26 blocks.In this paper, we complete the literature by building optimal even-odd permutations for 28, 30, 32, 36 blocks which to the best of our knowledge were unknown until now. The main idea behind our constructions and impossibility proof is a new characterization of the total diffusion of a permutation after a given number of rounds. In fact, we propose an efficient algorithm based on this new characterization which constructs all optimal even-odd permutations for the 28, 30, 32, 36 blocks cases and proves a better lower bound for the 34, 38, 40 and 42 blocks cases. In particular, we improve the 32 blocks case by exhibiting optimal even-odd permutations with diffusion round of 9. The existence of such a permutation was an open problem for almost 10 years and the best known permutation in the literature had a diffusion round of 10. Moreover, our characterization can be implemented very efficiently and allows us to easily re-find all optimal even-odd permutations for up to 26 blocks with a basic exhaustive search
BibTeX
@article{tosc-2019-29517,
  title={Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2019, Issue 2},
  pages={218-240},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8321},
  doi={10.13154/tosc.v2019.i2.218-240},
  author={Patrick Derbez and Pierre-Alain Fouque and Baptiste Lambin and Victor Mollimard},
  year=2019
}