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 Г with the set of vertices {1,..., n} is said to be (2)-primitive if, for some natural t for any i, j £ {1,..., 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 (2)-exponent of the digraph Г and is denoted by (2)-expT. A transformation g(x₁,... ,x_n) of the vector space V_n with coordinate functions g₁(x₁,..., x_n),..., g_n (x₁,..., x_n) corresponds to the n-vertex digraph Г©(g), in which an arc (i, j) is marked with the number 0, or 1, or 2 if gj (x₁,..., x_n) depends on x_i fictitiously, or linearly, or nonlinearly respectively, 1 ^ i, j ^ n. The transformation g(x₁,..., x_n) is called totally nonlinear if the label of each arc of the digraph is "2". The transformation g(x₁,... ,x_n) is called (2)-perfective if, for some natural t, all arcs of the digraph Г© (g*) are marked with the number 2. The smallest such t is called an total nonlinearity index of the transformation g(x₁,... ,x_n) and is denoted by (2)-n/g. It is proved that if in the labeled primitive digraph Г the label of each simple contour contains the number 2 and exp Г = n, then the digraph Г is (2)-primitive and (2)-expT = expT. An estimate of the (2)-exponent of the round function nonlinea-rity matrix M of order 2n of block algorithms based on the Feistel network is obtained using the (2)-exponent of the complication function nonlinearity matrix Ф of order n: (2)-exp M ^ (2)-expФ + 2. These results decrease the complexity of calculating the total nonlinearity index for some transformations g. Algorithms for recognition of the total non-linearity of the transformation g(x₁,... ,x_n) and estimates of (2)-n/g index are presented. For random transformations, the average complexity (number of elementary operations) does not exceed 2y(7 + 1)log8n where (2)-n/g = 7 and the elementary operation is the computation of any function on any input set. The algorithm was applied to obtain exact values of (2)-n/g of round substitutions g of the algorithms DES and Magma, the values 5 and 6, respectively, were obtained.

Keywords

Authors

References