A Characterization of Semi-Involutory MDS Matrices

Basic Information

• Paper ID: 2406.12842
• Title: A Characterization of Semi-Involutory MDS Matrices
• Authors: Tapas Chatterjee (Indian Institute of Technology Ropar), Ayantika Laha (Indian Institute of Technology Ropar)
• Classification: cs.CR (Cryptography and Security)
• Publication Date: January 1, 2025 (v2 version)
• Paper Link: https://arxiv.org/abs/2406.12842

Abstract

In symmetric cryptography, Maximum Distance Separable (MDS) matrices with computationally simple inverse matrices have widespread applications. Many block ciphers such as AES, SQUARE, SHARK, and hash functions such as PHOTON employ MDS matrices in their diffusion layers. This paper first characterizes all 3×3 irreducible semi-involutory matrices over finite fields of characteristic 2. Based on this matrix characterization, we provide necessary and sufficient conditions for constructing MDS semi-involutory matrices using only diagonal elements and associated diagonal matrix elements. Finally, we compute the number of 3×3 semi-involutory MDS matrices over arbitrary finite fields of characteristic 2.

Research Background and Motivation

Problem Background

1. Importance of Diffusion Layers: In symmetric cryptography, Shannon's concept of "confusion and diffusion" forms the foundation of cipher design. The diffusion layer conceals the relationship between ciphertext and plaintext, and MDS matrices provide perfect diffusion due to their maximum branch number.
2. Computational Efficiency Requirements: In lightweight cryptography applications, MDS matrices must not only provide security but also enable efficient implementation of their inverse matrices. Involutory matrices (A² = I) have received considerable attention because their inverse matrices are themselves.
3. Limitations of Existing Methods:
   • The search space for involutory MDS matrices is relatively limited
   • Involutory circulant matrices do not exist for certain dimensions
   • A broader class of matrices is needed to expand design choices

Research Motivation

This paper introduces semi-involutory matrices as a generalization of involutory matrices, defined as matrices for which there exist nonsingular diagonal matrices D₁ and D₂ such that M⁻¹ = D₁MD₂. This generalization significantly expands the class of matrices available for cryptographic design.

Core Contributions

1. Theoretical Characterization: Complete characterization of the structure of all 3×3 irreducible semi-involutory matrices over finite fields of characteristic 2
2. Construction Method: Provision of necessary and sufficient conditions for constructing 3×3 semi-involutory MDS matrices using only 6 parameters (3 diagonal elements + 3 associated diagonal matrix elements)
3. Counting Results: Precise computation of the number of 3×3 semi-involutory MDS matrices over F₂ᵐ as (2ᵐ-1)⁵(2ᵐ-2)(2ᵐ-4)
4. Generalization of Existing Results: Extension of Güzel et al.'s results on involutory MDS matrices to the larger class of semi-involutory matrices

Methodology Details

Problem Formulation

Investigation of 3×3 matrices A over finite fields F₂ᵐ of characteristic 2, requiring:

• Semi-Involutory Property: There exists a nonsingular diagonal matrix D such that ADA is diagonal
• MDS Property: All square submatrices of A are nonsingular
• Irreducibility: A cannot be reduced to a reduced form through permutation similarity

Core Theorems

Theorem 4.1 (Structural Characterization)

Let A be a 3×3 irreducible semi-involutory matrix with associated diagonal matrix D = diag(d₁,d₂,d₃). Then the off-diagonal elements can be expressed as:

• a₁₂ = (a₁₁d₁ + a₃₃d₃)d₂⁻¹x
• a₁₃ = (a₁₁d₁ + a₂₂d₂)d₃⁻¹xy
• a₂₁ = (a₂₂d₂ + a₃₃d₃)d₁⁻¹x⁻¹
• a₂₃ = (a₂₂d₂ + a₁₁d₁)d₃⁻¹y
• a₃₁ = (a₃₃d₃ + a₂₂d₂)d₁⁻¹(xy)⁻¹
• a₃₂ = (a₃₃d₃ + a₁₁d₁)d₂⁻¹y⁻¹

where x,y ∈ F₂ᵐ* are nonzero elements.

Theorem 4.5 (Necessary and Sufficient Conditions for MDS Property)

The matrix A with the above structure is a semi-involutory MDS matrix if and only if:

• a₁₁d₁ + a₂₂d₂ ≠ 0
• a₁₁d₁ + a₃₃d₃ ≠ 0
• a₂₂d₂ + a₃₃d₃ ≠ 0
• a₁₁d₁ + a₂₂d₂ + a₃₃d₃ ≠ 0

Technical Innovations

1. Unified Framework: Involutory matrices are treated as special cases of semi-involutory matrices, providing a unified analytical framework
2. Parametric Construction: Complete characterization of 3×3 semi-involutory MDS matrices through 8 parameters, significantly simplifying the search space
3. Counting Techniques: Application of the inclusion-exclusion principle to precisely compute the number of parameter combinations satisfying the conditions

Experimental Setup

Theoretical Verification

The paper is primarily theoretical work, with verification through concrete examples:

Example 4.6: Construction of semi-involutory MDS matrices over F₂₄

• Generating polynomial: x⁴ + x³ + 1
• Parameter selection: a₁₁=1, a₂₂=α, a₃₃=α², d₁=α, d₂=α, d₃=α³+1, x=1, y=α
• Verification that all MDS conditions are satisfied

Counting Verification

Verification of the counting formula through concrete calculations:

• F₂₂: 0 semi-involutory MDS matrices
• F₂₃: 403,368 semi-involutory MDS matrices
• F₂₄: 127,575,000 semi-involutory MDS matrices

Experimental Results

Main Results

1. Structural Completeness: Successful characterization of the structure of all 3×3 semi-involutory matrices, demonstrating that they can be completely determined by 8 parameters
2. MDS Determination: Provision of concise conditions for determining when semi-involutory matrices possess the MDS property
3. Quantity Growth: Significant increase in the number of semi-involutory MDS matrices compared to involutory MDS matrices:
   • Involutory MDS matrices over F₂₃: 1,176
   • Semi-involutory MDS matrices over F₂₃: 403,368 (approximately 343-fold increase)

Theoretical Findings

1. Generalization: The semi-involutory property genuinely generalizes the involutory property, with semi-involutory but non-involutory MDS matrices existing
2. Computational Advantages: The inverse matrices of semi-involutory MDS matrices can still be obtained through simple diagonal matrix multiplication, maintaining computational efficiency
3. Existence: No semi-involutory MDS matrices satisfying the conditions exist over F₂₂, but numerous such matrices exist over F₂ᵐ (m≥3)

Related Work

Historical Development

1. Involutory Matrix Research: Youssef et al. (2007) first introduced involutory linear transformations in cryptography
2. MDS Construction Methods: Gupta and Ray (2013) provided multiple MDS matrix construction methods
3. Circulant Matrix Limitations: Gupta et al. proved the non-existence of involutory circulant matrices
4. Semi-Involutory Concept: Cheon et al. (2021) introduced the concept of semi-involutory matrices

Contributions of This Paper

Compared to existing work, this paper:

• First applies the semi-involutory concept to MDS matrix construction
• Provides a larger design space than involutory matrices
• Furnishes precise counting results

Conclusions and Discussion

Main Conclusions

1. Complete characterization of the algebraic structure of 3×3 semi-involutory matrices
2. Establishment of connections between semi-involutory property and MDS property
3. Demonstration of the practical value of semi-involutory MDS matrices in cryptographic design

Limitations

1. Dimension Restriction: Current results apply only to 3×3 matrices
2. Characteristic Restriction: Theory primarily addresses finite fields of characteristic 2
3. Irreducibility Requirement: Matrices must possess the irreducibility property

Future Directions

1. Generalization to higher-dimensional matrices (particularly even-order or powers of 2)
2. Investigation of cases over finite fields of other characteristics
3. Exploration of applications of semi-involutory matrices in practical cryptographic systems

In-Depth Evaluation

Strengths

1. Theoretical Completeness: Provides complete characterization of 3×3 semi-involutory MDS matrices with rigorous theoretical results
2. Practical Value: Furnishes new tools for cryptographic design and expands the design space
3. Computational Efficiency: Maintains simplicity of inverse matrix computation, suitable for lightweight applications
4. Precise Counting: Provides exact counts of existing matrices, facilitating random selection

Weaknesses

1. Dimension Limitation: Considers only 3×3 cases; generalization to higher dimensions remains an open problem
2. Construction Complexity: Although parametric forms are provided, actual construction still requires satisfying multiple constraints
3. Application Verification: Lacks security analysis in practical cryptographic systems

Impact

1. Theoretical Contribution: Provides new insights into matrix theory over finite fields
2. Cryptographic Applications: Offers new candidate matrices for lightweight cipher design
3. Methodological Innovation: Counting methods are generalizable to similar problems

Applicable Scenarios

1. Lightweight Cryptography: Suitable for block cipher design in resource-constrained environments
2. Hash Functions: Can be used in hash function construction requiring efficient diffusion layers
3. Theoretical Research: Provides foundation for further investigation of higher-dimensional cases

References

The paper cites 25 related references, primarily including:

• Shannon's foundational work in cryptographic theory
• Classical cryptographic algorithms such as AES
• Important theoretical results in MDS matrix construction
• Recent research advances in semi-involutory matrices

This work achieves substantial progress on existing theoretical foundations, establishing a solid basis for both theory and applications of semi-involutory MDS matrices.