TY - JOUR
AU - Cauchois, Victor
AU - Gomez, Clément
AU - Thomas, Gaël
PY - 2019/03/08
Y2 - 2023/05/29
TI - General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes
JF - IACR Transactions on Symmetric Cryptology
JA - ToSC
VL - 2019
IS - 1
SE - Articles
DO - 10.13154/tosc.v2019.i1.264-301
UR - https://tosc.iacr.org/index.php/ToSC/article/view/7404
SP - 264-301
AB - <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>
ER -