Geodesic
On the annihilators of Boolean polynomials
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 1, pp. 88-109.

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

Boolean functions in general and Boolean polynomials (Zhegalkin polynomials or algebraic normal forms (ANF)) in particular are the subject of theoretical and applied studies in various fields of computer science. This article addresses the linear operators of the space of Boolean polynomials in $n$ variables, which leads to the results on the problem of finding the minimum annihilator degree for a given Boolean polynomial. This problem is topical in various analytical and algorithmic aspects of cryptography. Boolean polynomials and their combinatorial properties are under study in discrete analysis. The theoretical foundations of information security include the study of the properties of Boolean polynomials in connection with cryptography. In this article, we prove a theorem on the minimum annihilator degree. The class of Boolean polynomials is described for which the degree of an annihilator is at most $1$. We give a few combinatorial characteristics related to the properties of the space of Boolean polynomials. Some estimates of the minimum degree of an annihilator are given. We also consider the case of symmetric polynomials. Bibliogr. 26.
Mots-clés : Boolean polynomial
Keywords: symmetric polynomial, annihilator, linear operator, cryptosystem. 
@article{DA_2020_27_1_a4,
     author = {V. K. Leontiev and E. N. Gordeev},
     title = {On the annihilators of {Boolean} polynomials},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {88--109},
     publisher = {mathdoc},
     volume = {27},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_1_a4/}
}
TY  - JOUR
AU  - V. K. Leontiev
AU  - E. N. Gordeev
TI  - On the annihilators of Boolean polynomials
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 88
EP  - 109
VL  - 27
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_1_a4/
LA  - ru
ID  - DA_2020_27_1_a4
ER  - 
%0 Journal Article
%A V. K. Leontiev
%A E. N. Gordeev
%T On the annihilators of Boolean polynomials
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 88-109
%V 27
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_1_a4/
%G ru
%F DA_2020_27_1_a4
V. K. Leontiev; E. N. Gordeev. On the annihilators of Boolean polynomials. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 1, pp. 88-109. http://geodesic.mathdoc.fr/item/DA_2020_27_1_a4/

[1] I. A. Pankratova, Boolean Functions in Cryptography, Tomsk. Gos. Univ., Tomsk, 2014

[2] N. Courtois, W. Meier, “Algebraic attacks on stream ciphers with linear feedback”, Advances in Cryptology – EUROCRYPT 2003, Proc. Int. Conf. Theory Appl. Cryptogr. Tech. (Warsaw, Poland, May 4–8, 2003), Lect. Notes Comput. Sci., 2656, Springer, Heidelberg, 2003, 345–359 | DOI | MR | Zbl

[3] F. Didier, “A new upper bound of the block error probability after decoding over the erasure channel”, IEEE Trans. Inform. Theory, 52:10 (2006), 4496–4503 | DOI | MR | Zbl

[4] K. Feng, Q. Liao, J. Yang, “Maximal values of generalized algebraic immunity”, Des. Codes Cryptogr., 50 (2009), 243–252 | DOI | MR

[5] C. Carlet, B. Merabet, “Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions”, Adv. Math. Commun., 7:2 (2013), 197–217 | DOI | MR | Zbl

[6] M. S. Lobanov, “Exact ratios between nonlinearity and algebraic immunity”, Diskretn. Anal. Issled. Oper., 15 (2008), 34–47 | Zbl

[7] M. S. Lobanov, “About a method for obtaining some lower estimates of nonlinearity of a Boolean function”, Mat. Zametki, 93:5 (2013), 741–745 | DOI | Zbl

[8] M. S. Lobanov, “An exact ratio between nonlinearity and algebraic immunity”, Diskretn. Mat., 18:3 (2006), 152–159 | DOI | Zbl

[9] V. K. Leont'ev, “Boolean polynomials and linear transformations”, Dokl. Ross. Akad. Nauk, 425:3 (2009), 320–322 | Zbl

[10] M. E. Tuzhilin, “Algebraic immunity of Boolean functions”, Prikl. Diskretn. Mat., 2008, no. 2, 18–22

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

[12] 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 | DOI | MR | Zbl

[13] S. Mesnager, G. Gohen, “Fast algebraic immunity of Boolean functions”, Adv. Math. Commun., 11:2 (2017), 373–377 | DOI | MR | Zbl

[14] Q. Wang, T. Johansson, “On equivalence classes of Boolean functions”, Information Security and Cryptology, Rev. Sel. Pap. 13th Int. Conf. (Seoul, Korea, Dec. 1–3, 2010), Lect. Notes Comput. Sci., 6829, Springer, Heidelberg, 2011, 311–324 | DOI | MR | Zbl

[15] J. Peng, H. Kan, “Constructing rotation symmetric Boolean functions with maximum algebraic immunity on an odd number of variables”, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E95-A:6 (2012), 1056–1064 | DOI

[16] L. Sun, F. W. Fu, “Constructions of balanced odd-variable rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity”, Theor. Comput. Sci., 738 (2018), 13–24 | DOI | MR | Zbl

[17] L. Sun, F. W. Fu, “Constructions of even-variable RSBFs with optimal algebraic immunity and high nonlinearity”, J. Appl. Math. Comput., 56:1–2 (2018), 593–610 | DOI | MR | Zbl

[18] F. U. Shaojing, D. U. Jiao, Q. U. Longjiang, L. I. Chao, “Construction of odd-variable rotation symmetric Boolean functions with maximum algebraic immunity”, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E99-A:4 (2016), 853–855 | MR

[19] Q. Wang, C. H. Tan, P. Stanica, “Concatenations of the hidden weighted bit function and their cryptographic properties”, Adv. Math. Commun., 8:2 (2014), 153–165 | DOI | MR | Zbl

[20] V. K. Leont'ev, “Symmetrical Boolean polynomials”, Zh. Vychisl. Mat. Mat. Fiz., 50:8 (2010), 1520–1531 | MR | Zbl

[21] C. Carlet, G. Gao, W. Liu, “A secondary construction and a transformation on rotation symmetric functions, and their action on bent and semi-bent functions”, J. Comb. Theory, A, 127 (2014), 161–175 | DOI | MR | Zbl

[22] S. Su, X. Tang, “Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity”, Des. Codes Cryptogr., 71 (2014), 1567–1580 | MR

[23] V. K. Leont'ev, Combinatorics, Information, v. 1, Combinatorial Analysis, MFTI, M., 2015

[24] V. K. Leont'ev, O. Moreno, “About zeros of Boolean polynomials”, Zh. Vychisl. Mat. Mat. Fiz., 38:9 (1998), 1608–1615 | MR | Zbl

[25] V. K. Leont'ev, E. N. Gordeev, “On number of zeros of Boolean polynomials”, Zh. Vychisl. Mat. Mat. Fiz., 68:7 (2018), 1235–1245

[26] E. N. Gordeev, V. K. Leont'ev, N. V. Medvedev, “On properties of Boolean polynomials important for cryptosystems”, Vopr. Kiberbezopasnosti, 2017, no. 3, 63–69