Tight bounds between algebraic immunity and high-order nonlinearities

Among cryptographically significant characteristics of Boolean functions used in symmetric ciphers, the algebraic immunity and the high-order nonlinearities play an important role. Some bounds on the high-order nonlinearities of a Boolean function via its algebraic immunity were obtained in recent papers. In this paper these results are improved and new tight bounds are obtained. We prove a new universal tight lower bound that reduces the problem of estimation of high-order nonlinearities to the problem of finding dimensions of some linear spaces of Boolean functions. As simple consequences we obtain all previously known bounds in this field. For polynomials with disjoint terms, we reduce finding the dimensions of linear spaces of Boolean functions mentioned above to simple combinatorial analysis. Finally, for a Boolean function a tight lower bound on the second-order nonlinearity via its algebraic immunity is proved. Tabl. 1, bibl. 9.