New Insights into Involutory and Orthogonal MDS Matrices

Résumé technique : Nouvelles perspectives sur les matrices MDS involutoires et orthogonales

Énoncé du problème
Les matrices de distance maximale séparable (MDS) sont fondamentales pour les couches de diffusion des chiffrements par blocs et des fonctions de hachage en raison de leurs nombres de branchement optimaux. Bien qu'une littérature importante existe sur la construction de candidats MDS efficaces, des propriétés structurelles spécifiques — à savoir involutoires (auto-inverses) et orthogonales (transposée-inverse) — sont hautement désirables pour réduire les coûts de mise en œuvre en permettant l'utilisation de circuits identiques ou presque identiques pour le chiffrement et le déchiffrement. Récemment, ces concepts ont été généralisés en matrices « semi-involutoires » et « semi-orthogonales ». Cependant, les recherches existantes se sont largement concentrées sur la proposition de nouvelles constructions ou sur l'optimisation des métriques de mise en œuvre. Il existe un manque de compréhension systématique concernant les interconnexions structurelles entre ces variantes généralisées (semi-involutoires/semi-orthogonales) et leurs homologues conventionnels (involutoires/orthogonales), particulièrement en ce qui concerne leur énumération sur les corps finis $\mathbb{F}_{2^m}$.

Méthodologie
Les auteurs adoptent une approche d'analyse structurelle plutôt que de proposer de nouvelles constructions de matrices. La méthodologie centrale repose sur la décomposition unique des matrices non singulières sur $\mathbb{F}_{2^m}^*$ sous la forme $M = D_1 M_1 D_2$, où $D_1$ et $D_2$ sont des matrices diagonales non singulières et $M_1$ est une « matrice représentative » avec une forme canonique spécifique (la première ligne et la première colonne composées de uns).

Les étapes méthodologiques clés incluent :

1. Établir les interconnexions : Le document prouve que les propriétés d'être involutoire, semi-involutoire, orthogonale ou semi-orthogonale sont préservées ou transformées de manière prévisible lors de l'application de la mise à l'échelle diagonale $D_1 M_1 D_2$.
2. Dériver les relations de comptage : En analysant les contraintes sur $D_1$ et $D_2$ requises pour qu'une matrice $M$ satisfasse des propriétés spécifiques, les auteurs dérivent des relations bidirectionnelles entre les comptes des matrices généralisées et de leurs homologues conventionnels.
3. Caractérisation structurelle : Les auteurs dérivent la structure algébrique générale des matrices orthogonales d'ordre $n$ arbitraire sur $\mathbb{F}_{2^m}$ et spécialisent cela pour $n=3$ et $n=4$.
4. Énumération : En utilisant les résultats d'énumération connus pour les matrices MDS involutoires et les relations structurelles dérivées, les auteurs calculent le nombre exact de matrices MDS semi-involutoires et semi-orthogonales pour des ordres et des tailles de corps spécifiques.

Contributions clés et résultats

• Interconnexions structurelles : Le document établit des relations non triviales entre les matrices semi-involutoires et involutoires, et entre les matrices semi-orthogonales et orthogonales. Plus précisément, il est démontré que le nombre de matrices MDS involutoires $n \times n$ est égal à $(2^m - 1)^{n-1}$ fois le nombre de matrices MDS semi-involutoires de la forme $M_1$. Une correspondance similaire est prouvée pour les matrices semi-orthogonales et orthogonales.
• Énumération des matrices 3×3 :
  • MDS orthogonales : Les auteurs dérivent une formule explicite pour le nombre de matrices MDS orthogonales $3 \times 3$ sur $\mathbb{F}_{2^m}$ comme étant $(2^m - 2)(2^m - 3)(2^m - 4)$.
  • MDS semi-orthogonales : En exploitant le lien structurel, ils dérivent le compte des matrices MDS semi-orthogonales $3 \times 3$ comme étant $(2^m - 1)^5(2^m - 2)(2^m - 3)(2^m - 4)$.
  • MDS semi-involutoires : Le document fournit une dérivation directe pour le compte des matrices MDS semi-involutoires $3 \times 3$, confirmant la formule $(2^m - 1)^5(2^m - 2)(2^m - 4)$. Cela sert d'alternative aux preuves précédentes trouvées dans la littérature.
• Intersection des propriétés : Les auteurs caractérisent les matrices qui sont à la fois semi-involutoires et semi-orthogonales. Ils prouvent que pour les matrices $3 \times 3$, toute matrice semi-involutoire de la forme $M_1$ est nécessairement symétrique, impliquant que le compte des matrices possédant les deux propriétés est identique au compte des matrices semi-involutoires.
• Énumération des matrices 4×4 : L'étude s'étend aux matrices $4 \times 4$. Les auteurs calculent le nombre de matrices MDS semi-involutoires pour $m = 3, \dots, 8$ et les matrices orthogonales/semi-orthogonales pour $m=3, 4$. Ils identifient également des matrices MDS orthogonales légères d'ordre 4 basées sur les comptes de portes d-XOR, trouvant des comptes optimaux de 64 sur $\mathbb{F}_{2^3}$ et 72 sur $\mathbb{F}_{2^4}$.
• Structure générale : Une forme générale pour les matrices orthogonales $n \times n$ sur $\mathbb{F}_{2^m}$ est dérivée, exprimant la dernière ligne et la dernière colonne en fonction des éléments de la sous-matrice restante et de contraintes de sommation spécifiques.

Signification et affirmations
Le document affirme fournir un cadre unifié pour comprendre l'énumération des matrices MDS avec des contraintes structurelles spécifiques. En déplaçant l'accent de la construction vers les relations structurelles, les auteurs démontrent que les comptes des variantes généralisées (semi-involutoires/semi-orthogonales) peuvent être directement dérivés des comptes de leurs homologues conventionnels.

Les auteurs déclarent que leur travail offre :

1. Des dérivations alternatives : Une dérivation plus directe et concise des formules de comptage pour les matrices MDS semi-involutoires et semi-orthogonales $3 \times 3$ par rapport aux preuves exhaustives existantes.
2. De nouvelles données d'énumération : Des comptes explicites pour les matrices MDS orthogonales $3 \times 3$ (précédemment non établis dans la littérature) et des comptes étendus pour les matrices $4 \times 4$ sur des corps finis plus larges.
3. Un aperçu théorique : Une preuve que pour les matrices $3 \times 3$, l'intersection des propriétés semi-involutoires et semi-orthogonales coïncide avec l'ensemble des matrices semi-involutoires, une propriété qui ne se vérifie pas nécessairement pour des ordres plus élevés (par exemple, $n \ge 4$).

Le document conclut que ces interconnexions fournissent une méthode systématique pour déterminer le nombre de matrices MDS satisfaisant des contraintes structurelles supplémentaires, consolidant les formules d'énumération explicites pour plusieurs classes de matrices MDS $3 \times 3$ et $4 \times 4$ algébriquement contraintes.