Nonlinearity characteristics estimations for function compositions over vector spaces by the matrix-graph approach

We expand the matrix-graph approach developed by V. M. Fomichev to assessing the nonlinearity characteristics of vector space transformations using ternary matrices over the multiplicative semigroup $\{0,1,2\}$ or digraphs with arcs labeled with the numbers from the set $\{0,1,2\}$. A digraph $\Gamma$ with the set of vertices $\{1,\ldots ,n\}$ is said to be $\langle2\rangle$-primitive if, for some natural $t$ for any $i,j\in\{1,\ldots ,n\}$, there is a path from $i$ to $j$ of length $t$ that passes through the arc labeled "$2$". The smallest such $t$ is called the $\langle2\rangle$-exponent of the digraph $\Gamma$ and is denoted by $\langle2\rangle$-$\exp\Gamma$. A transformation $g(x_1,\ldots ,x_n)$ of the vector space $V_n$ with coordinate functions $g_1(x_1,\ldots ,x_n),\ldots ,g_n(x_1,\ldots ,x_n)$ corresponds to the $n$-vertex digraph $\Gamma_\Theta(g)$, in which an arc $(i,j)$ is marked with the number $0$, or $1$, or $2$ if $g_j(x_1,\ldots ,x_n)$ depends on $x_i$ fictitiously, or linearly, or nonlinearly respectively, $1\le i,j\le n$. The transformation $g(x_1,\ldots ,x_n)$ is called totally nonlinear if the label of each arc of the digraph is "$2$". The transformation $g(x_1,\ldots ,x_n)$ is called $\langle2\rangle$-perfective if, for some natural $t$, all arcs of the digraph $\Gamma_\Theta(g^t)$ are marked with the number $2$. The smallest such $t$ is called an total nonlinearity index of the transformation $g(x_1,\ldots ,x_n)$ and is denoted by $\langle2\rangle$-$nlg$. It is proved that if in the labeled primitive digraph $\Gamma$ the label of each simple contour contains the number $2$ and $\exp\Gamma=n$, then the digraph $\Gamma$ is $\langle2\rangle$-primitive and $\langle2\rangle$-$\exp\Gamma=\exp\Gamma$. An estimate of the $\langle2\rangle$-exponent of the round function nonlinearity matrix $M$ of order $2n$ of block algorithms based on the Feistel network is obtained using the $\langle2\rangle$-exponent of the complication function nonlinearity matrix $\Phi$ of order $n$: $\langle2\rangle$-$\exp M\le\langle2\rangle$-$\exp\Phi+2$. These results decrease the complexity of calculating the total nonlinearity index for some transformations $g$. Algorithms for recognition of the total nonlinearity of the transformation $g(x_1,\ldots ,x_n)$ and estimates of $\langle2\rangle$-$nlg$ index are presented. For random transformations, the average complexity (number of elementary operations) does not exceed $2\gamma(\gamma+1)\log8n$ where $\langle2\rangle$-$nlg=\gamma$ and the elementary operation is the computation of any function on any input set. The algorithm was applied to obtain exact values of $\langle2\rangle$-$nlg$ of round substitutions $g$ of the algorithms DES and Magma, the values $5$ and $6$, respectively, were obtained.