@article{Cauchois_Gomez_Thomas_2019, title={General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes}, volume={2019}, url={https://tosc.iacr.org/index.php/ToSC/article/view/7404}, DOI={10.13154/tosc.v2019.i1.264-301}, abstractNote={<p>Type-II Generalized Feistel Schemes are one of the most popular versions of Generalized Feistel Schemes. Their round function consists in applying a classical Feistel transformation to <em>p</em> sub-blocks of two consecutive words and then shifting the k = 2p words cyclically. The low implementation costs it offers are balanced by a low diffusion, limiting its efficiency. Diffusion of such structures may however be improved by replacing the cyclic shift with a different permutation without any additional implementation cost. In this paper, we study ways to determine permutations with the fastest diffusion called <em>optimal permutations</em>.<br>To do so, two ideas are used. First, we study the natural equivalence classes of permutations that preserve cryptographic properties; second, we use the representation of permutations as coloured trees.<br>For both heuristic and historical reasons, we focus first on <em>even-odd permutations</em>, that is, those permutations for which images of even numbers are odd. We derive from their structure an upper bound on the number of their equivalence classes together with a strategy to perform exhaustive searches on classes. We performed those exhaustive searches for sizes k ≤ 24, while previous exhaustive searches on all permutations were limited to <em>k</em> ≤ 16. For sizes beyond the reach of this method, we use tree representations to find permutations with good intermediate diffusion properties. This heuristic leads to an optimal even-odd permutation for <em>k</em> = 26 and best-known results for sizes <em>k</em> = 64 and <em>k</em> = 128.<br>Finally, we transpose these methods to all permutations. Using a new strategy to exhaust equivalence classes, we perform exhaustive searches on classes for sizes <em>k</em> ≤ 20 whose results confirmed the initial heuristic: there always exist optimal permutations that are even-odd and furthermore for <em>k</em> = 18 all optimal permutations are even-odd permutations.</p>}, number={1}, journal={IACR Transactions on Symmetric Cryptology}, author={Cauchois, Victor and Gomez, Clément and Thomas, Gaël}, year={2019}, month={Mar.}, pages={264–301} }