Generalized Feistel networks revisited

Andrey Bogdanov, Kyoji Shibutani

Research output: Contribution to journalJournal articleResearchpeer-review


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.
Original languageEnglish
JournalDesigns, Codes and Cryptography
Issue number3-3
Pages (from-to)75-97
Publication statusPublished - 2013
Externally publishedYes


Dive into the research topics of 'Generalized Feistel networks revisited'. Together they form a unique fingerprint.

Cite this