On the differential and linear efficiency of balanced Feistel networks

Andrey Bogdanov

Research output: Contribution to journalJournal articleResearchpeer-review


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.
Original languageEnglish
JournalInformation Processing Letters
Issue number20
Pages (from-to)861-866
Publication statusPublished - 2010
Externally publishedYes


Dive into the research topics of 'On the differential and linear efficiency of balanced Feistel networks'. Together they form a unique fingerprint.

Cite this