On a Method of Derivation of Lower Bounds for the Nonlinearity of Boolean Functions

The calculation of the exact value of the $r$th order nonlinearity of a Boolean function (the power of the distance between the function and the set of functions is at most $r$) or the derivation of a lower bound for it is a complicated problem (especially for $r>1$). Lower bounds for nonlinearities of different orders in terms of the value of algebraic immunity were obtained in a number of papers. These estimates turn out to be sufficiently strong if the value of algebraic immunity is maximum or close to maximum. In the present paper, we prove a statement that allows us to obtain fairly strong lower bounds for nonlinearities of different orders and for many functions with low algebraic immunity.