Algebraic Preconditioning for Involutory MDS Matrix Search: A Filter-Cascade Approach with Evolutionary Solvers

Abstract

Maximum distance separable (MDS) matrices are central to the diffusion layers of symmetric-key primitives, and involutory MDS matrices are especially useful because the same circuit handles both encryption and decryption. Earlier work by the present authors and others identified involutory MDS matrices through row/column permutations of an existing MDS matrix using evolutionary algorithms (genetic algorithm and particle swarm optimisation). Such heuristics, however, give no guarantee of existence and produce no infeasibility certificate when the search fails. In this paper we propose an algebraic preconditioner that runs before any metaheuristic solver. The preconditioner is a cascade of four necessary conditions derived from the involutory equation over a binary extension field: a determinant filter on the matrix and three permutation-level filters based on the trace, rank, and characteristic polynomial of the permuted matrix. The cascade either certifies infeasibility, returns a solution directly, or hands a strictly smaller search space to the metaheuristic. We integrate the cascade with three metaheuristic solvers (genetic algorithm, particle swarm optimisation, and simulated annealing) and study their behaviour on three worked examples: a $4\times 4$ MDS matrix over the field with sixteen elements that the cascade certifies infeasible, a $4\times 4$ feasible instance, and a $6\times 6$ feasible instance over the field with 256 elements. Empirical results show that approximately 90 percent of randomly sampled MDS matrices are rejected by the matrix-level stage instantly with a mathematical certificate of infeasibility, which a stand-alone metaheuristic solver cannot provide. We further evaluate the cascade on a larger feasible instance ($8\times 8$ over the field with 256 elements, search space of size 40320), where it prunes the space to eight candidates in under a second; on this instance particle swarm optimisation and simulated annealing fail to reach a solution within their default budgets while the cascade-restricted search succeeds immediately, showing that the pruning is already decisive at a scale where the raw heuristic is not. We show that the high Filter-1 rejection rate is not specific to Cauchy matrices but holds across Vandermonde-derived and random MDS families and intensifies with field size; we quantify the false-positive rate of the necessary conditions on the tested instances; and we release the full implementation and experiment scripts for reproducibility. Consistent with these findings, we present the algebraic cascade and its infeasibility certificate as the primary contribution and the metaheuristic coupling as a straightforward, honestly-scoped component.