On the differential and linear efficiency of balanced Feistel networks

Balanced Feistel networks (BFN) have been widely used for constructing efficient block ciphers. They are known to provide high efficiency with respect to differential and linear cryptanalysis, when instantiated with SL-type round functions (BFN–SL). This work suggests that BFNs attain higher efficiency when the round function is defined as a composition of two substitution layers connected by a linear diffusion layer (SLS-type round function).

The resulting structure is called BFN–SLS.Tight upper bounds on the differential and linear trail probabilities are proven for such constructions. When compared to BFN–SL with single-round diffusion, BFN–SLS exhibits an increase by almost 1/3 in the proportion of active S-boxes. When compared to BFN–SL with multiple-round diffusion, BFN–SLS provides the same proportion of active S-boxes, requiring, however, twice less linear operations and a single diffusion matrix for all rounds.It is argued that the cost of linear operations cannot be ignored when dealing with efficiency.

Different BFNs are compared under consideration of the relative complexity of linear and nonlinear finite field operations. As a result, since BFN–SLS minimizes the number of necessary linear operations, its efficiency is higher than that of the known BFN–SL constructions.