Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 28, No 2, 2021, P. 74-91
UDC
V. M. Fomichev
On degree of nonlinearity of the coordinate polynomials for a product of transformations of a binary vector space
Abstract:
We construct a nonnegative integer matrix to evaluate the matrix of nonlinearity characteristics for the coordinate polynomials of a product of transformations of a binary vector space. The matrix of the characteristics of the transformation is defined by the degrees of nonlinearity of the derivatives of all coordinate functions with respect to each input variable. The entries of the evaluation matrix are expressed in terms of the characteristics of the coordinate polynomials of the multiplied transformations. Calculation of the evaluation matrix is easier than calculating the exact values of the characteristics. The estimation method is extended to an arbitrary number of multiplied transformations. Computational examples are given that in particular show the accuracy of the obtained estimates and the domain of their nontriviality.
Tab. 1, bibliogr. 18.
Keywords: coordinate polynomial of transformation, maximal mono?mial of a polynomial, degree of a polynomial.
DOI: 10.33048/daio.2021.28.700
Vladimir M. Fomichev 1,2,3
1. Financial University under the Government of the Russian Federation,
49 Leningradskii Avenue, 125993 Moscow, Russia
2. Security Code LLC,
10 Bld. 1 Pervyi Nagatinskii Driveway, 115230 Moscow, Russia
3. Institute of Informatics Problems of FRC CSC RAS,
44 Bld. 2 Vavilov Street, 119333 Moscow, Russia
e-mail: fomichev.2016@yandex.ru
Received September 28, 2020
Revised February 15, 2021
Accepted February 19, 2021
References
[1] V. M. Fomichev, Ya. Eh. Avezova, A. M. Koreneva, and S. N. Kyazhin, Primitivity and local primitivity of digraphs and nonnegative matrices, Diskretn. Anal. Issled. Oper. 25 (3), 95–125 (2018) [Russian] [J. Appl. Ind. Math. 12 (3), 453–469 (2018)].[2] V. M. Fomichev and A. M. Koreneva, Encryption performance and security of certain wide block ciphers, J. Comput. Virol. Hack. Tech. 16, 197–216 (2020).
[3] V. M. Fomichev and V. M. Bobrov, Estimation of local nonlinearity characteristics of vector space transformation iteration using matrix-graph approach, Prikl. Diskretn. Mat., Prilozh., No. 12, 32–35 (2019) [Russian].
[4] G. Frobenius, Über Matrizen aus nicht negativen Elementen, Berl. Ber., 456–477 (1912) [German].
[5] H. Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z. 52, 642–648 (1950) [German].
[6] P. Perkins, A theorem on regular graphs, Pac. J. Math. 2, 1529–1533 (1961).
[7] A. L. Dulmage and N. S. Mendelsohn, The exponent of a primitive matrix, Can. Math. Bull. 5 (3), 241–244 (1962).
[8] A. L. Dulmage and N. S. Mendelsohn, Gaps in the exponent set of primitive matrices, Ill. J. Math. 8 (4), 642–656 (1964).
[9] R. A. Brualdi and B. Liu, Generalized exponents of primitive directed graphs, J. Graph Theory. 14 (4), 483–499 (1990).
[10] S. W. Neufeld, A diameter bound on the exponent of a primitive directed graph, Lin. Algebra Appl. 245, 27–47 (1996).
[11] B. Liu, Generalized exponents of Boolean matrices, Lin. Algebra Appl. 373, 169–182 (2003).
[12] V. N. Sachkov and V. E. Tarakanov, Combinatorics of Nonnegative Matrices (AMS, Providence, RI, 2002) (Transl. Math. Monogr., Vol. 213).
[13] V. M. Fomichev and S. N. Kyazhin, Local primitivity of matrices and graphs, Diskretn. Anal. Issled. Oper. 24 (1), 97–119 (2017) [Russian] [J. Appl. Ind. Math. 11 (1), 26–39 (2017)].
[14] T. Suzaki and K. Minematsu, Improving the generalized Feistel, in Fast Software Encryption (Proc. 17th Int. Workshop, Seoul, Korea, Feb. 7–10, 2010) (Springer, Heidelberg, 2010), pp. 19–39 (Lect. Notes Comput. Sci., Vol. 6147).
[15] T. Berger, J. Francq, M. Minier, and G. Thomas, Extended generalized Feistel networks using matrix representation to propose a new lightweight block cipher: Lilliput, IEEE Trans. Comput. 65 (7), 2074–2089 (2016).
[16] T. Berger, M. Minier, and G. Thomas, Extended generalized Feistel networks using matrix representation, in Selected Areas in Cryptography — SAC 2013 (Proc. 20th Int. Conf., Burnaby, Canada, Aug. 14–16, 2013) (Springer, Heidelberg, 2014), pp. 289–305 (Lect. Notes Comput. Sci., Vol. 8282).
[17] K. Nyberg, Generalized Feistel networks, in Advances in Cryptology — ASIACRYPT’96 (Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur., Kyongju, Korea, Nov. 3–7, 1996) (Springer, Heidelberg, 1996),
[18] O. A. Logachyov, A. A. Salnikov, and V. V. Yashchenko, Boolean Functions in Coding Theory and Cryptology (MTsNMO, Moscow, 2004).
