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/

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

[2] Lobanov M. S., “Otsenka nelineinosti vysokikh poryadkov bulevoi funktsii cherez znachenie eë algebraicheskoi immunnosti”, Materialy VI molodezhnoi nauchnoi shkoly po diskretnoi matematike i eë prilozheniyam, Chast 2 (Moskva, aprel 2007), In-t prikladnoi matematiki RAN, M., 2007, 11–16

[3] Canteaut A., “Open problems related to algebraic attacks on stream ciphers”, International workshop on coding and cryptography (WCC 2005) (Bergen, March 2005), Lect. Notes in Comp. Sci., 3969, Springer, Berlin, 2006, 1–11 | MR

[4] Carlet C., “On the higher order nonlinearities of algebraic immune functions”, Advances in cryptology – CRYPTO 2006, Lect. Notes in Comp. Sci., 4117, Springer, Berlin–Heidelberg, 2006, 584–601 | MR | Zbl

[5] Courtois N., Meier W., “Algebraic attacks on stream ciphers with linear feedback”, Advances in cryptology – EUROCRYPT 2003, Lect. Notes in Comp. Sci., 2656, Springer, Berlin–Heidelberg, 2003, 345–359 | MR | Zbl

[6] Dalai D. K., Gupta K. C., Maitra S., “Results on algebraic immunity for cryptographically significant Boolean functions”, Progress in cryptology – Indocrypt 2004 (Chennai, India, December 20–22, 2004), Lect. Notes in Comp. Sci., 3348, Springer, Berlin–Heidelberg, 2004, 92–106 | MR | Zbl

[7] Meier W., Pasalic E., Carlet C., “Algebraic attacks and decomposition of Boolean functions”, Advances in Cryptology – EUROCRYPT 2004, Lect. Notes in Comp. Sci., 3027, Springer, Berlin–Heidelberg, 2004, 474–491 | MR | Zbl

[8] Mesnager S., Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity, Cryptology ePrint archive: Report 2007/117, http:// eprint.iacr.org/2007/117 | MR

[9] McWilliams F. J., Sloane N. J. A., The theory of error correcring codes, North-Holland, New York, 1977, 760 pp.