Structural cryptanalysis and storage efficiency of Kronecker-product diffusion layers for lightweight block ciphers

Abstract

Matrix-based linear transformations are fundamental to the diffusion properties of modern block ciphers. This paper investigates the algebraic structure and security of the Dual-Matrix Affine Modular construction  \(C\equiv K_LMK_R+K_S\pmod p.\) Although it is structurally isomorphic to a constrained affine map on \(\mathbb{Z}_p^{n^2}\) via the Kronecker product \(K_R^T\otimes K_L\), this construction offers a significant efficiency advantage: it reduces the storage complexity from \(\mathcal{O}(n^4)\) (for a generic linear layer) to \(\mathcal{O}(n^2)\). We formally derive the effective key space and present a rigorous structural chosen-plaintext attack. We prove that by exploiting the tensor decomposition property, an equivalent key tuple can be recovered in \(\mathcal{O}(n^4)\) field operations, significantly bypassing the \(\mathcal{O}(n^6)\) complexity of generic affine cryptanalysis. Our results demonstrate that while insecure as a standalone primitive, this structure offers a favorable trade-off between large-state diffusion and implementation cost, making it a compelling candidate for the mixing layer in lightweight Substitution-Permutation Networks (SPNs).