Geodesic
Exact relation between nonlinearity and algebraic immunity
Diskretnaya Matematika, Tome 18 (2006) no. 3, pp. 152-159 
M. S. Lobanov. Exact relation between nonlinearity and algebraic immunity. Diskretnaya Matematika, Tome 18 (2006) no. 3, pp. 152-159. http://geodesic.mathdoc.fr/item/DM_2006_18_3_a11/
@article{DM_2006_18_3_a11,
     author = {M. S. Lobanov},
     title = {Exact relation between nonlinearity and algebraic immunity},
     journal = {Diskretnaya Matematika},
     pages = {152--159},
     year = {2006},
     volume = {18},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2006_18_3_a11/}
}
TY  - JOUR
AU  - M. S. Lobanov
TI  - Exact relation between nonlinearity and algebraic immunity
JO  - Diskretnaya Matematika
PY  - 2006
SP  - 152
EP  - 159
VL  - 18
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2006_18_3_a11/
LA  - ru
ID  - DM_2006_18_3_a11
ER  - 
%0 Journal Article
%A M. S. Lobanov
%T Exact relation between nonlinearity and algebraic immunity
%J Diskretnaya Matematika
%D 2006
%P 152-159
%V 18
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2006_18_3_a11/
%G ru
%F DM_2006_18_3_a11

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

Boolean functions have found a widespread use in cryptography. In connection with the advent of the ‘algebraic’ attack on stream ciphers, the Boolean functions, which are used in these ciphers as nonlinear filters, have to possess, among other properties, high algebraic immunity. One more cryptographically significant property of Boolean functions, especially of those utilised in stream ciphers, is nonlinearity. In this connection, the question arises about relations between the nonlinearity of a Boolean function and its algebraic immunity. In this research we obtain a lower bound for nonlinearity in terms of algebraic immunity and present functions at which this bound is attained for any admissible values of the parameters.

[1] Courtois N., Meier W., “Algebraic attacks on stream ciphers with linear feedback”, Lecture Notes Computer Sci., 2656, 2003, 345–359 | MR | Zbl

[2] Dalai D. K., Gupta K. C., Maitra S., “Results on algebraic immunity for cryptographically significant Boolean functions”, Lecture Notes Computer Sci., 3348, 2004, 92–106 | MR | Zbl

[3] Dalai D. K., Gupta K. C., Maitra S., “Cryptographically significant Boolean functions: construction and analysis in terms of algebraic immunity”, Lecture Notes Computer Sci., 3557, 2005, 98–111 | Zbl

[4] Dalai D. K., Maitra S., Sarkar S., “Basic theory in construction of Boolean functions with maximum possible annihilator immunity”, Design, Codes and Cryptography, 40 (2006), 41–58 | DOI | MR | Zbl

[5] Meier W., Pasalic E., Carlet C., “Algebraic attacks and decomposition of Boolean functions”, Lecture Notes Computer Sci., 3027, 2004, 474–491 | MR | Zbl