Geodesic
On~degree of~nonlinearity of~the~coordinate polynomials for~a~product of transformations of~a~binary vector space
Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 2, pp. 74-91.

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

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.
Mots-clés : coordinate polynomial of transformation, maximal monomial of a polynomial
Keywords: degree of a polynomial. 
@article{DA_2021_28_2_a3,
     author = {V. M. Fomichev},
     title = {On~degree of~nonlinearity of~the~coordinate polynomials for~a~product of transformations of~a~binary vector space},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {74--91},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2021_28_2_a3/}
}
TY  - JOUR
AU  - V. M. Fomichev
TI  - On~degree of~nonlinearity of~the~coordinate polynomials for~a~product of transformations of~a~binary vector space
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2021
SP  - 74
EP  - 91
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2021_28_2_a3/
LA  - ru
ID  - DA_2021_28_2_a3
ER  - 
%0 Journal Article
%A V. M. Fomichev
%T On~degree of~nonlinearity of~the~coordinate polynomials for~a~product of transformations of~a~binary vector space
%J Diskretnyj analiz i issledovanie operacij
%D 2021
%P 74-91
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2021_28_2_a3/
%G ru
%F DA_2021_28_2_a3
V. M. Fomichev. On~degree of~nonlinearity of~the~coordinate polynomials for~a~product of transformations of~a~binary vector space. Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 2, pp. 74-91. http://geodesic.mathdoc.fr/item/DA_2021_28_2_a3/

[1] V. M. Fomichev, Ya. Eh. Avezova, A. M. Koreneva, S. N. Kyazhin, “Primitivity and local primitivity of digraphs and nonnegative matrices”, J. Appl. Ind. Math., 12:3 (2018), 453–469 | DOI | MR | Zbl

[2] Fomichev V. M., Koreneva A. M., “Encryption performance and security of certain wide block ciphers”, J. Comput. Virol. Hack. Tech., 16 (2020), 197–216 | DOI

[3] V. M. Fomichev, V. M. Bobrov, “Estimation of local nonlinearity characteristics of vector space transformation iteration using matrix-graph approach”, Prikl. Diskretn. Mat., Prilozh., 2019, no. 12, 32–35 (Russian)

[4] Frobenius G., “Über Matrizen aus nicht negativen Elementen”, Berl. Ber., 1912, 456–477 (German) | Zbl

[5] Wielandt H., “Unzerlegbare, nicht negative Matrizen”, Math. Z., 52 (1950), 642–648 (German) | DOI | MR | Zbl

[6] P. Perkins, “A theorem on regular graphs”, Pac. J. Math., 2 (1961), 1529–1533 | DOI | MR

[7] Dulmage A. L., Mendelsohn N. S., “The exponent of a primitive matrix”, Can. Math. Bull., 5:3 (1962), 241–244 | DOI | MR | Zbl

[8] Dulmage A. L., Mendelsohn N. S., “Gaps in the exponent set of primitive matrices”, Ill. J. Math., 8:4 (1964), 642–656 | MR | Zbl

[9] Brualdi R. A., Liu B., “Generalized exponents of primitive directed graphs”, J. Graph Theory, 14:4 (1990), 483–499 | DOI | MR | Zbl

[10] Neufeld S. W., “A diameter bound on the exponent of a primitive directed graph”, Lin. Algebra Appl., 245 (1996), 27–47 | DOI | MR | Zbl

[11] Liu B., “Generalized exponents of Boolean matrices”, Lin. Algebra Appl., 373 (2003), 169–182 | DOI | MR | Zbl

[12] Sachkov V. N., Tarakanov V. E., Combinatorics of nonnegative matrices, Transl. Math. Monogr., 213, AMS, Providence, RI, 2002, 269 pp. | DOI | MR | Zbl

[13] V. M. Fomichev, S. N. Kyazhin, “Local primitivity of matrices and graphs”, J. Appl. Ind. Math., 11:1 (2017), 26–39 | DOI | MR | MR | Zbl

[14] Suzaki T., Minematsu K., “Improving the generalized Feistel”, Fast Software Encryption, Proc. 17th Int. Workshop (Seoul, Korea, Feb. 7–10, 2010), Lect. Notes Comput. Sci., 6147, Springer, Heidelberg, 2010, 19–39 | DOI | Zbl

[15] Berger T., Francq J., Minier M., Thomas G., “Extended generalized Feistel networks using matrix representation to propose a new lightweight block cipher: Lilliput”, IEEE Trans. Comput., 65:7 (2016), 2074–2089 | DOI | MR | Zbl

[16] Berger T., Minier M., Thomas G., “Extended generalized Feistel networks using matrix representation”, Selected Areas in Cryptography, SAC 2013, Proc. 20th Int. Conf. (Burnaby, Canada, Aug. 14–16, 2013), Lect. Notes Comput. Sci., 8282, Springer, Heidelberg, 2014, 289–305 | DOI | MR | Zbl

[17] Nyberg K., “Generalized Feistel networks”, Advances in Cryptology - ASIACRYPT'96, Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. (Kyongju, Korea, Nov. 3–7, 1996), Lect. Notes Comput. Sci., 1163, Springer, Heidelberg, 1996, 91–104 | DOI | MR | Zbl

[18] O. A. Logachyov, A. A. Salnikov, V. V. Yashchenko, Boolean Functions in Coding Theory and Cryptology, MTsNMO, M., 2004