Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:1, 162–175
Volume 27, No 1, 2020, P. 88-109
UDC 519.16
V. K. Leontiev and E. N. Gordeev
On the annihilators of Boolean polynomials
Abstract:
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.
Keywords: Boolean polynomial, symmetric polynomial, annihilator, linear operator, cryptosystem.
DOI: 10.33048/daio.2020.27.646
Vladimir K. Leontiev 1,2
Eduard N. Gordeev 2
1. Dorodnitsyn Computing Center,
42 Vavilov Street, 119991 Moscow, Russia
2. Bauman Moscow State Technical University,
5 Vtoraya Baumanskaya Street, 105005 Moscow, Russia
e-mail: vkleontiev@yandex.ru, werhorn@yandex.ru
Received January 24, 2019
Revised September 10, 2019
Accepted September 25, 2019
References
[1] I. A. Pankratova, Boolean Functions in Cryptography (Tomsk. Gos. Univ., Tomsk, 2014).[2] N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in Advances in Cryptology – EUROCRYPT 2003 (Proc. Int. Conf. Theory and Applications of Cryptography Techniques, Warsaw, Poland, May 4–8, 2003) (Springer, Heidelberg, 2003), pp. 345–359.
[3] F. Didier, A new upper bound of the block error probability after decoding over the erasure channel, IEEE Trans. Inform. Theory. 52 (10), 4496–4503 (2006).
[4] K. Feng, Q. Liao, and J. Yang, Maximal values of generalized algebraic immunity, Des. Codes Cryptogr. 50, 243–252 (2009).
[5] C. Carlet and B. Merabet, Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions, Adv. Math. Commun. 7 (2), 197–217 (2013).
[6] M. S. Lobanov, Exact ratios between nonlinearity and algebraic immunity, Diskretn. Anal. Issled. Oper. 15 (6), 34–47 (2008).
[7] M. S. Lobanov, About a method for obtaining some lower estimates of nonlinearity of a Boolean function, Mat. Zametki 93 (5), 741–745 (2013).
[8] M. S. Lobanov, An exact ratio between nonlinearity and algebraic immunity, Diskretn. Mat. 18 (3), 152–159 (2006).
[9] V. K. Leont’ev, Boolean polynomials and linear transformations, Dokl. Ross. Akad. Nauk 425 (3), 320–322 (2009).
[10] M. E. Tuzhilin, Algebraic immunity of Boolean functions, Prikl. Diskretn. Mat., No. 2, 18–22 (2008).
[11] P. Rizomiliotis, Improving the high order nonlinearity of Boolean functions with prescribed algebraic immunity, Discrete Appl. Math. 158 (18), 2049–2055 (2010).
[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), 3656–3662 (2008).
[13] S. Mesnager and G. Gohen, Fast algebraic immunity of Boolean functions, Adv. Math. Commun. 11 (2), 373–377 (2017).
[14] Q. Wang and T. Johansson, On equivalence classes of Boolean functions, in Information Security and Cryptology (Rev. Sel. Pap. 13th Int. Conf., Seoul, Korea, Dec. 1–3, 2010) (Springer, Heidelberg, 2011),
[15] J. Peng and 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), 1056–1064 (2012).
[16] L. Sun and F.-W. Fu, Constructions of balanced odd-variable rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity, Theor. Comput. Sci. 738, 13–24 (2018).
[17] L. Sun and F.-W. Fu, Constructions of even-variable RSBFs with Optimal algebraic immunity and high nonlinearity, J. Appl. Math. Comput. 56 (1–2), 593–610 (2018).
[18] F. U. Shaojing, D. U. Jiao, Q. U. Longjiang, and 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), 853–855 (2016).
[19] Q. Wang, C. H. Tan, and P. Stanica, Concatenations of the hidden weighted bit function and their cryptographic properties, Adv. Math. Com?mun. 8 (2), 153–165 (2014).
[20] V. K. Leont’ev, Symmetrical Boolean polynomials, Zh. Vychisl. Mat. Mat. Fiz. 50 (8), 1520–1531 (2010).
[21] C. Carlet, G. Gao, and W. Liu, A secondary construction and a transformation on rotation symmetric functions, and their action on bent and semi-bent functions, J. Comb. Theory, Ser. A, 127, 161–175 (2014).
[22] S. Su and X. Tang, Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity, Des. Codes Cryptogr. 71, 1567–1580 (2014).
[23] V. K. Leont’ev, Combinatorics and Information, Vol. 1: Combinatorial Analysis (MFTI, Moscow, 2015).
[24] V. K. Leont’ev and O. Moreno, About zeros of Boolean polynomials, Zh. Vychisl. Mat. Mat. Fiz. 38 (9), 1608–1615 (1998).
[25] V. K. Leont’ev and E. N. Gordeev, On number of zeros of Boolean polynomials, Zh. Vychisl. Mat. Mat. Fiz. 68 (7), 1235–1245 (2018).
[26] E. N. Gordeev, V. K. Leont’ev, and N. V. Medvedev, On properties of Boolean polynomials important for cryptosystems, Vopr. Kiberbezopasnosti, No. 3, 63–69 (2017).
