The nonlinearity of restrictions of direct sums of monomials and of threshold functions

Abstract We investigate the behavior of the nonlinearity for Boolean functions when their inputs are restricted to affine subspaces of the original domain. Functions which maintain a relatively high nonlinearity are of interest for cryptographic applications. To capture this behavior, we introduce the notion of k -restriction nonlinearity, as the minimal nonlinearity achieved when restricting to affine spaces of codimension at most k . We give some results that facilitate the computation of this parameter for direct sums of functions and for functions of relatively low nonlinearity. These results are then applied to two important classes of functions. Firstly, for direct sums of monomials, we provide an explicit formula and a characterization, showing that the k -restriction nonlinearity equals the nonlinearity of the direct sum of monomials obtained from the original function by removing any k non-linear monomials of lowest degree. In general, the nonlinearity decreases by only a small amount for such functions. Secondly, for threshold functions, we prove that under certain conditions on the parameters, the k -restriction nonlinearity equals the nonlinearity of a related threshold function in fewer variables, from which an explicit formula for the k -restriction nonlinearity is derived.