Invariant Subspace of the P-SPN Structure with a Class of Linear Layers Matrix

Emerging applications in cloud computing, big data, and the Internet of Things have driven the advancement and implementation of security protocols, including secure multi-party computation, fully homomorphic encryption, and zero-knowledge proofs, to meet heightened security demands. Designing cryptographic permutations and block ciphers using a partial substitution permutation network (P-SPN) approach where the nonlinear part does not cover the entire state has recently gained attention due to favorable implementation characteristics in various scenarios. For the word-oriented P-SPN schemes with a fixed linear layer, the choice of the MDS matrix significantly affects the security level provided by P-SPN designs. If the MDS matrix is chosen weak, it will allow for extremely maximum invariant subspace that pass the entire rounds without activating any non-linear operation. Firstly, we investigate the properties of a special block matrix with circulant block, specifically utilized within the linear layer matrix of P-SPN structure schemes. Subsequently, our investigation extends to present the annihilating polynomial of low degree for these specific type of matrices, as well as to put forward the range of determining their minimal polynomial degree. Finally, this study articulates a lower bound estimated for the dimension of the maximum invariant subspace within the P-SPN structure schemes when integrated with the aforementioned matrix type. In scenarios where the S-box number s=1 in the P-SPN structure schemes, we achieve a precise determination of the dimension of maximum invariant subspace. Conversely, for cases with s>1, with some certain specific conditions, our research establishes more compact lower bound for the dimension of the maximum invariant subspace. The research results of this paper offer valuable design guidance for the development of matrices within the linear layer of P-SPN architecture schemes.