On primitivity of mixing digraphs associated with 2-feedbacks shift registers | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2017. № 37. DOI: 10.17223/20710410/37/3

Analysis of mixing properties of round transformations is an important issue in the theory of symmetric iterative block ciphers. For researching this subject, a matrix-digraph approach is widely used in cryptography. This approach allows to characterize the required properties in terms of primitivity and exponent of a matrix (or a digraph) related to the transformations concerned. This paper is devoted to such a characterization of mixing properties of transformations fulfilled by 2-feedback shift registers. For naturals n, m, and r, let n > 1, r > 1,0 ^ m ^ n - 2, Vr = (GF(2)]^r; fm : V_rⁿ ^ Vr and f,_n-1 : V_rⁿ ^ Vr are some feedback functions; ц : V_r ^ V_r and g : V_r ^ V_r are some permutations over V_r used to modify feedbacks f_m and f_n-1 respectively; x$₀, x^ ,...,xs_p are all essential variables of the function f_m(x₀, x₁,..., x_n-1), £₀ = m + 1, 0 < < ... < 5_p < n, p > 0; x_do, x_dl,..., x_dq are all essential variables of the function f_n-1(x₀, x₁,..., x_n-1), d0 = 0, d1 < ... < dq < n, q > 0; ^ : V_rⁿ ^ V_rⁿ, <£⁹^(x0, x1,..., xn-1) = = (x1,... ,xm-1,^(/m(x0,.. .,Жп-1 )),x_m+1,..., xn-2, g(/n-1 (x0,... ,xn-1))). In fact, is the transition function of a shift register of the length n over V_r with two feedback functions ^(/_m(x)) and g(/_n-1(x)), x = x₀x₁... x_n-1. Let M= M be a Boolean matrix (m_ij) (called the mixing matrix of the map ^>^9,M), where m_ij = 1 iff the j-th coordinate function of the map essentially depends on the variable x_i (i,j Е {0,1,...,n - 1}). The matrix M is said to be primitive if there is a power M^e = (mj^ of its mixing matrix M such that mj > 0 for all i and j; in this case, the least power e is called an exponent of M and is denoted by exp M. The conceptions of the primitiveness and exponent of the matrix Mexpend to the digraph Г(^^9,м) with the adjacency matrix M - the mixing graph associated with The main results of the paper are the following: 1) it is proved that the strongly connected digraph Г(^^9,м) is primitive iff > m and the numbers in the set L' = {n - d_i, n + m + 1 - dj - : i = 0,..., q, j = 0,..., t, k = 1,..., p} are relatively prime or ^ m and the numbers in the set L = {n - d_i, n + m + 1 - dj - , m + 1 - ^ : i = 0,...,q, j = 0,... ,t,k = т + 1,... ,p, l = 1,..., т} are relatively prime, where t and т are determined by the conditions: d_t and are the largest numbers in D = {d₀,..., d_q} and A = {£₀,..., £_p} with the properties d_t ^ m and ^ m respectively; 2) for expr(^>⁹^), some attainable upper bounds depending on m and other parameters in D and A are obtained, improving all the known exponent estimates for the same digraphs. Particularly, if (n - 1) Е D and m Е A, then expr(^^9,M) ^ min{p(D) + e, p(A) + e'}, where p(D) = max{n - d_q,d_q - d_q-1, ..., d1 - d0}, p(A) = max{^1 + n - £p, £p - 5p-_b..., fo - ^r,..., £2 - M, e = = max{2n - m - 2 - d_q, n + m - max{£₀, £_p}}, and e' = max{2m + 1 - , n - 1 - d_t}. These results can be successfully used in construction of iterative cryptographic algorithms based on with the rapid input data mixing.