Geodesic
Tight bounds between algebraic immunity and high-order nonlinearities
Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 6, pp. 34-47

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: stream cipher, nonlinear filter, algebraic attack, Boolean function, algebraic immunity, algebraic degree, nonlinearity, high-order nonlinearity, annihilator. 
@article{DA_2008_15_6_a3,
     author = {M. S. Lobanov},
     title = {Tight bounds between algebraic immunity and high-order nonlinearities},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {34--47},
     publisher = {mathdoc},
     volume = {15},
     number = {6},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2008_15_6_a3/}
}
TY  - JOUR
AU  - M. S. Lobanov
TI  - Tight bounds between algebraic immunity and high-order nonlinearities
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2008
SP  - 34
EP  - 47
VL  - 15
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2008_15_6_a3/
LA  - ru
ID  - DA_2008_15_6_a3
ER  - 
%0 Journal Article
%A M. S. Lobanov
%T Tight bounds between algebraic immunity and high-order nonlinearities
%J Diskretnyj analiz i issledovanie operacij
%D 2008
%P 34-47
%V 15
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2008_15_6_a3/
%G ru
%F DA_2008_15_6_a3
M. S. Lobanov. Tight bounds between algebraic immunity and high-order nonlinearities. Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 6, pp. 34-47. http://geodesic.mathdoc.fr/item/DA_2008_15_6_a3/