New Insights into Involutory and Orthogonal MDS Matrices

Technical Summary: New Insights into Involutory and Orthogonal MDS Matrices

Problem Statement
Maximum Distance Separable (MDS) matrices are fundamental to the diffusion layers of block ciphers and hash functions due to their optimal branch numbers. While significant literature exists on constructing efficient MDS candidates, specific structural properties—namely involutory (self-inverse) and orthogonal (transpose-inverse)—are highly desirable for reducing implementation costs by allowing identical or nearly identical circuitry for encryption and decryption. Recently, these concepts have been generalized into "semi-involutory" and "semi-orthogonal" matrices. However, existing research has largely focused on proposing new constructions or optimizing implementation metrics. There is a lack of systematic understanding regarding the structural interconnections between these generalized variants (semi-involutory/semi-orthogonal) and their conventional counterparts (involutory/orthogonal), particularly concerning their enumeration over finite fields $\mathbb{F}_{2^m}$.

Methodology
The authors adopt a structural analysis approach rather than proposing new matrix constructions. The core methodology relies on the unique decomposition of non-singular matrices over $\mathbb{F}_{2^m}^*$ into the form $M = D_1 M_1 D_2$, where $D_1$ and $D_2$ are non-singular diagonal matrices and $M_1$ is a "representative matrix" with a specific canonical form (first row and column consisting of ones).

Key methodological steps include:

1. Establishing Interconnections: The paper proves that the properties of being involutory, semi-involutory, orthogonal, or semi-orthogonal are preserved or transformed in predictable ways when applying the diagonal scaling $D_1 M_1 D_2$.
2. Deriving Counting Relationships: By analyzing the constraints on $D_1$ and $D_2$ required for a matrix $M$ to satisfy specific properties, the authors derive bidirectional relationships between the counts of generalized matrices and their conventional counterparts.
3. Structural Characterization: The authors derive the general algebraic structure of orthogonal matrices of arbitrary order $n$ over $\mathbb{F}_{2^m}$ and specialize this to $n=3$ and $n=4$.
4. Enumeration: Using known enumeration results for involutory MDS matrices and the derived structural relationships, the authors calculate the exact number of semi-involutory and semi-orthogonal MDS matrices for specific orders and field sizes.

Key Contributions and Results

• Structural Interconnections: The paper establishes nontrivial relationships between semi-involutory and involutory matrices, and between semi-orthogonal and orthogonal matrices. Specifically, the number of $n \times n$ involutory MDS matrices is shown to be $(2^m - 1)^{n-1}$ times the number of semi-involutory MDS matrices of the form $M_1$. A similar correspondence is proven for semi-orthogonal and orthogonal matrices.
• Enumeration of 3×3 Matrices:
  • Orthogonal MDS: The authors derive an explicit formula for the number of $3 \times 3$ orthogonal MDS matrices over $\mathbb{F}_{2^m}$ as $(2^m - 2)(2^m - 3)(2^m - 4)$.
  • Semi-Orthogonal MDS: Leveraging the structural link, they derive the count for $3 \times 3$ semi-orthogonal MDS matrices as $(2^m - 1)^5(2^m - 2)(2^m - 3)(2^m - 4)$.
  • Semi-Involutory MDS: The paper provides a direct derivation for the count of $3 \times 3$ semi-involutory MDS matrices, confirming the formula $(2^m - 1)^5(2^m - 2)(2^m - 4)$. This serves as an alternative to previous proofs found in literature.
• Intersection of Properties: The authors characterize matrices that are both semi-involutory and semi-orthogonal. They prove that for $3 \times 3$ matrices, any semi-involutory matrix of the form $M_1$ is necessarily symmetric, implying that the count of matrices possessing both properties is identical to the count of semi-involutory matrices.
• 4×4 Matrix Enumeration: The study extends to $4 \times 4$ matrices. The authors compute the number of semi-involutory MDS matrices for $m = 3, \dots, 8$ and orthogonal/semi-orthogonal matrices for $m=3, 4$. They also identify lightweight orthogonal MDS matrices of order 4 based on d-XOR gate counts, finding optimal counts of 64 over $\mathbb{F}_{2^3}$ and 72 over $\mathbb{F}_{2^4}$.
• General Structure: A general form for $n \times n$ orthogonal matrices over $\mathbb{F}_{2^m}$ is derived, expressing the last row and column in terms of the remaining sub-matrix elements and specific summation constraints.

Significance and Claims
The paper claims to provide a unified framework for understanding the enumeration of MDS matrices with specific structural constraints. By shifting the focus from construction to structural relationships, the authors demonstrate that the counts of generalized variants (semi-involutory/semi-orthogonal) can be directly derived from the counts of their conventional counterparts.

The authors state that their work offers:

1. Alternative Derivations: A more direct and concise derivation for the counting formulas of $3 \times 3$ semi-involutory and semi-orthogonal MDS matrices compared to existing comprehensive proofs.
2. New Enumeration Data: Explicit counts for $3 \times 3$ orthogonal MDS matrices (previously unestablished in the literature) and extended counts for $4 \times 4$ matrices over larger finite fields.
3. Theoretical Insight: A proof that for $3 \times 3$ matrices, the intersection of semi-involutory and semi-orthogonal properties coincides with the set of semi-involutory matrices, a property that does not necessarily hold for higher orders (e.g., $n \ge 4$).

The paper concludes that these interconnections provide a systematic method for determining the number of MDS matrices satisfying additional structural constraints, consolidating explicit enumeration formulas for several algebraically constrained $3 \times 3$ and $4 \times 4$ MDS classes.