Geodesic
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/}
}
TY  - JOUR
AU  - M. S. Lobanov
TI  - On a Method of Derivation of Lower Bounds for the Nonlinearity of Boolean Functions
JO  - Matematičeskie zametki
PY  - 2013
SP  - 741
EP  - 745
VL  - 93
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2013_93_5_a8/
LA  - ru
ID  - MZM_2013_93_5_a8
ER  - 
%0 Journal Article
%A M. S. Lobanov
%T On a Method of Derivation of Lower Bounds for the Nonlinearity of Boolean Functions
%J Matematičeskie zametki
%D 2013
%P 741-745
%V 93
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2013_93_5_a8/
%G ru
%F 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/

[1] N. T. Courtois, W. Meier, “Algebraic attacks on stream ciphers with linear feedback”, Advances in cryptology – EUROCRYPT 2003, Lecture Notes in Comput. Sci., 2656, Springer-Verlag, Heidelberg, 2003, 345–359 | DOI | MR | Zbl

[2] W. Meier, E. Pasalic, C. Carlet, “Algebraic attacks and decomposition of Boolean functions”, Advances in Cryptology – EUROCRYPT 2004, Lecture Notes in Comput. Sci., 3027, Springer-Verlag, Heidelberg, 2004, 474–491 | DOI | MR | Zbl

[3] M. S. Lobanov, “Tochnoe sootnoshenie mezhdu nelineinostyu i algebraicheskoi immunnostyu”, Diskret. matem., 18:3 (2006), 152–159 | DOI | MR | Zbl

[4] M. S. Lobanov, “Tochnye sootnosheniya mezhdu nelineinostyu i algebraicheskoi immunnostyu”, Diskretn. analiz i issled. oper., 15:6 (2008), 34–47 | MR

[5] S. Mesnager, “Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity”, IEEE Trans. Inform. Theory, 54:8 (2008), 3656–3662 | MR | Zbl

[6] P. Rizomiliotis, “Improving the high order nonlinearity lower bound for Boolean functions with given algebraic immunity”, Discrete Appl. Math., 158:18 (2010), 2049–2055 | DOI | MR | Zbl