This article is cited in 1 paper

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

M. S. Lobanov

M. V. Lomonosov Moscow State University

Abstract: 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.

Keywords: Boolean function, $r$th order nonlinearity of a Boolean function, algebraic immunity, Zhegalkin polynomial.

UDC: 517

Received: 24.05.2012

DOI: 10.4213/mzm10233

 English version: Mathematical Notes, 2013, 93:5, 727–731

Bibliographic databases:

• 
• 
• 
• 
• 
•