On a Method of Derivation of Lower Bounds for the Nonlinearity of Boolean Functions
Matematičeskie zametki, Tome 93 (2013) no. 5, pp. 741-745
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{MZM_2013_93_5_a8,
author = {M. S. Lobanov},
title = {On a {Method} of {Derivation} of {Lower} {Bounds} for the {Nonlinearity} of {Boolean} {Functions}},
journal = {Matemati\v{c}eskie zametki},
pages = {741--745},
publisher = {mathdoc},
volume = {93},
number = {5},
year = {2013},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/MZM_2013_93_5_a8/}
}
M. S. Lobanov. On a Method of Derivation of Lower Bounds for the Nonlinearity of Boolean Functions. Matematičeskie zametki, Tome 93 (2013) no. 5, pp. 741-745. http://geodesic.mathdoc.fr/item/MZM_2013_93_5_a8/