On the approximation of S‐boxes via Maiorana–McFarland functions

Substitution boxes (S‐boxes) are the key components of conventional cryptographic systems. To quantify the confusion property of S‐boxes, different non‐linearity criteria are proposed such as usual non‐linearity ( N F ), unrestricted non‐linearity (UN F ), generalised non‐linearity (GN F ), higher order non‐linearity (HN F ) and so on. Although these different criteria come from the idea of linear (or non‐linear) approximation of S‐boxes, the algebraic structures of Boolean functions that are used to approximate to S‐boxes have not been considered yet. In this study, the concept of the extended non‐linearity of S‐boxes (denoted by EN F ) is introduced by measuring the distance of a given function to a subset of Maiorana–McFarland functions. This approximation appears to be appealing because of a particular structure of this class of functions, namely their representation as a concatenation of affine functions. The complexity of computing the r th order extended non‐linearity for S‐boxes over GF (2) n is less than O (( n r )2 n − r ), ( r > 1). Moreover, a theoretical upper bound for the r th order extended non‐linearity is proved, which is much lower than previous generalised non‐linearity which might give a rise to more efficient attacks that combine a generalised correlation approach with guess and determine techniques. Furthermore, the relationship between the r ‐order extended non‐linearity and the generalised non‐linearity is derived.