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 rth order extended non-linearity for S-boxes over GF(2)ⁿ is less than O((n : r)2^n-r), (r > 1). Moreover, a theoretical upper bound for the rth 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.