Efficient Search for Optimal Permutations of Refined Type-II Generalized Feistel Structures

Type-II Generalized Feistel Structures are widely used to design block ciphers benefit from their simplicity and high parallelism. However, there is a trade-off between efficiency (i.e. the number of rounds) and compactness (i.e. the partition number). Hence, Suzaki et al. (in FSE2010), Cauchois et al. (in FSE2019) and Derbez et al. (in FSE2019) studied how to find optimal permutations for Type-II Generalized Feistel Structures to improve the diffusion property. In this paper, we further investigate how to find the optimal permutations for Refined Type-II Generalized Feistel Structures (RGFS) using k blocks and a permutation of size sk. First, we propose pair-equivalent relations and permutational equivalent relations and combine these two strategies to exhaustively search permutations that achieve optimal diffusion rounds. Then, to reduce the search space, we focus on the even-odd permutations. Based on even-odd permutations, we reveal the relations between the block size k, the permutation size s and the optimal full diffusion rounds and show Type-II GFS needs at least 4 rounds to achieve full diffusion. Besides, we also give the conditions that the block size k and the sub-block size s need to satisfy to achieve full diffusion after 4 rounds. Moreover, using pair-equivalent relations on even-odd permutations, we give the upper bound on the number of such equivalent classes. And then, using the search strategies we give some optimal permutations in different sizes of Type-II RGFS. Finally, we conduct a security analysis of our results with respect to impossible differentials and integral attacks.