Generalized Feistel networks revisited

This work deals with the classification, security and efficiency of generalized Feistel networks (GFNs) with 4 lines. We propose a definition of a GFN, essentially limiting consideration to Feistel-type constructions with domain-preserving F-functions and rotation by one line between rounds. Under this definition, we demonstrate that there are only two non-contracting representatives in the class of 4-line GFNs up to equivalence, namely, the type-I and type-II GFNs that avoid obvious differential effects. We propose to instantiate the GFNs with SPS-functions (two substitution layers separated by a permutation layer) instead of single SP-functions (one substitution-permutation layer only). We prove tight lower bounds on the number of differentially and linearly active functions and S-boxes in such ciphers. We show that the instantiation with SPS-functions using MDS diffusion provides a proportion of differentially and linearly active S-boxes by up to 33 and 50 % higher than that with single SP-functions for type-I and type-II GFNs, respectively, if the same matrix is used in all rounds. Moreover, we present the upper bounds on the differential and the linear hull probability for the type-II GFNs with SPS-functions. This opens up the possibility of designing more efficient block ciphers based on GFN structure.