Geodesic
Estimating nonlinearity characteristics for~iterative transformations of~a~vector space
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 4, pp. 131-151.

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

We present theoretical foundations for the matrix-graphic approach (MGA) to the estimation of characteristics of the sets of essential and nonlinear variables of the composition of transformations of an $n$-dimensional vector space over a field. The ternary nonlinearity matrix corresponds to a transformation, where the $i$th row and the $j$th column of the matrix contain $0$, $1$, or $2$ if and only if the $j$th coordinate function of the transformation depends on the $i$th variable fictitiously, or linearly, or nonlinearly, $0\leq i,j n$. MGA is based on the inequality according to which the nonlinearity matrix of the product of transformations is at most (the inequality is elementwise) the product of the nonlinearity matrices of the transformations. We define the multiplication for ternary matrices. The properties are studied of the multiplicative monoid of all ternary matrices of order $n$ without zero rows and columns and of the monoid $\mathbb{\Gamma}_n$ bijectively corresponding to it of all $n$-vertex digraphs with edges labeled with $0$, $1$, and $2$, where each vertex has nonzero indegree and outdegree. The iteration depth (number of multipliers) for transformations is estimated with the use of MGA in which the four types of the nonlinearity of transformations can be achieved, where each or some of the coordinate functions of the product of transformations can depend nonlinearly on all or at least some variables. We present the results of research on the nonlinearity of iterations of round substitution of the block ciphers DES and “Magma.” Bibliogr. 18.
Keywords: nonlinearity matrix (digraph) of a transformation, $\langle\alpha\rangle$-exponent of a matrix (of a digraph), perfective transformation.
Mots-clés : $\langle\alpha\rangle$-primitive matrix (digraph) 
@article{DA_2020_27_4_a5,
     author = {V. M. Fomichev},
     title = {Estimating nonlinearity characteristics for~iterative transformations of~a~vector space},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {131--151},
     publisher = {mathdoc},
     volume = {27},
     number = {4},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_4_a5/}
}
TY  - JOUR
AU  - V. M. Fomichev
TI  - Estimating nonlinearity characteristics for~iterative transformations of~a~vector space
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 131
EP  - 151
VL  - 27
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_4_a5/
LA  - ru
ID  - DA_2020_27_4_a5
ER  - 
%0 Journal Article
%A V. M. Fomichev
%T Estimating nonlinearity characteristics for~iterative transformations of~a~vector space
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 131-151
%V 27
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_4_a5/
%G ru
%F DA_2020_27_4_a5
V. M. Fomichev. Estimating nonlinearity characteristics for~iterative transformations of~a~vector space. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 4, pp. 131-151. http://geodesic.mathdoc.fr/item/DA_2020_27_4_a5/

[1] V. N. Sachkov, V. E. Tarakanov, Combinatorics of Nonnegative Matrices, AMS, Providence, 2002 | MR | MR | Zbl

[2] V. M. Fomichev, Methods of Discrete Mathematics in Cryptology, DialogMIFI, 2010 (Russian)

[3] V. M. Fomichev, D. A. Melnikov, Cryptographic Methods of Information Security, YURAYT, 2016 (Russian)

[4] 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 (2018), 453–469 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

[13] K. Nyberg, “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

[14] T. Suzaki, K. Minematsu, “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] T. Berger, J. Francq, M. Minier, G. Thomas, “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] T. Berger, M. Minier, G. Thomas, “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] V. M. Fomichev, A. M. Koreneva, A. R. Miftakhutdinova, D. I. Zadorozhny, “Evaluation of the maximum performance of block encryption algorithms”, Mat. Vopr. Kriptogr., 10 (2019), 181–190 | MR

[18] V. M. Fomichev, A. M. Koreneva, “Encryption performance and security of certain wide block ciphers”, J. Comput. Virol. Hack. Tech., 2020 (accessed June 5, 2020) | DOI