Theoretical Foundations of Applied Discrete Mathematics

Invariant subspaces of matrices with a nontrivial automorphism group

D. A. Burov, S. V. Kostarev


Abstract: Define the action of $S_n \times S_n$ on the set of square matrices of order $n$ over $\mathbb{F}_{2^r}$ as follows: $A^{(g_1,g_2)} = \left(a_{g_1(i), g_2(j)}\right)$ for $A \in \left(\mathbb{F}_{2^r}\right)_{n,n}$ and $(g_1,g_2) \in S_n \times S_n$. The automorphism group $\mathrm{Aut}(A)$ of a matrix $A$ is the set of all $(g_1,g_2) \in S_n \times S_n$ such that ${A^{(g_1,g_2)} = A}$. It is known that if $A$ is a Maximum Distance Separable (MDS-) matrix, then $\mathrm{Aut}(A) = (G,\sigma) = \{(g,\sigma(g)): g\in G\}$, where $G < S_n$ and $\sigma$ is a conjugation in $S_n$. For a partition $\{1,\ldots,n\} = \Gamma_1\cup \ldots \cup \Gamma_k$, define the vectors $e_{\Gamma_i} = \sum\limits_{s \in \Gamma_i}e_s$, $i=1,\ldots,k$, where $e_j = (0,\ldots,0,1_j,0,\ldots,0) \in \mathbb{F}_{2^r}^n$ for $j=1,\ldots,n$. If $\{1,\ldots,n\} = \Gamma_1\cup\ldots\cup\Gamma_k$ is a partition into orbits of a subgroup $H < S_n$, the subspaces $W_H = \langle e_{\Gamma_1},\ldots,e_{\Gamma_k}\rangle < \mathbb{F}_{2^r}^n$ are called $H$-orbital. It has been proven that any $H$-orbital subspace is invariant under a matrix with automorphism group $(G,1)$ if $H < G < S_n$. $H$-orbital subspaces can be used in invariant subspace attack for block ciphers, as they remain invariant under the parallel action of identical s-boxes, which is used in several block ciphers. This paper describes subspaces of $\mathbb{F}^6_{2^r}$ that are invariant under both MDS circulat matrix of order $6$ over $\mathbb{F}^6_{2^r}$ and the parallel action of identical $s$-boxes.

Keywords: invariant subspace attack, automorphism group, MDS-matrices.

UDC: 519.7

DOI: 10.17223/2226308X/18/3