On the correlations between a combining function and functions of fewer variables

The Hamming distance of a Boolean function to the functions having many linear structures is an important cryptographic parameter. Most notably, the accuracy of the approximation of the combining function by a function of fewer variables is a major issue in most attacks against combination generators. Here, we show that the distance of a function to the functions having a k-dimensional linear space is highly related to its nonlinearity. In particular, we prove that there is no accurate approximation of any highly nonlinear function by a function depending on a small subset of its input variables.