New Insights into Involutory and Orthogonal MDS Matrices

Technische Zusammenfassung: Neue Erkenntnisse über involutorische und orthogonale MDS-Matrizen

Problemstellung
Maximum Distance Separable (MDS)-Matrizen sind grundlegend für die Diffusionsschichten von Blockverschlüsselungen und Hash-Funktionen, da sie optimale Verzweigungszahlen (Branch Numbers) aufweisen. Während eine umfangreiche Literatur zur Konstruktion effizienter MDS-Kandidaten existiert, sind spezifische strukturelle Eigenschaften – nämlich involutorisch (selbstinvers) und orthogonal (transponiert-invers) – äußerst wünschenswert, um Implementierungskosten zu senken, indem identische oder nahezu identische Schaltungen für Verschlüsselung und Entschlüsselung ermöglicht werden. Kürzlich wurden diese Konzepte zu „semi-involutorischen“ und „semi-orthogonalen“ Matrizen verallgemeinert. Die bestehende Forschung hat sich jedoch weitgehend auf das Vorschlagen neuer Konstruktionen oder die Optimierung von Implementierungsmetriken konzentriert. Es mangelt an einem systematischen Verständnis der strukturellen Verbindungen zwischen diesen verallgemeinerten Varianten (semi-involutorisch/semi-orthogonal) und ihren konventionellen Gegenstücken (involutorisch/orthogonal), insbesondere im Hinblick auf deren Enumeration über endliche Körper $\mathbb{F}_{2^m}$.

Methodik
Die Autoren verfolgen einen strukturellen Analyseansatz anstelle des Vorschlags neuer Matrizkonstruktionen. Die Kernmethodik stützt sich auf die eindeutige Zerlegung nicht-singulärer Matrizen über \mathbb{F}_{2^m}^*} in die Form $M = D_1 M_1 D_2$, wobei $D_1$ und $D_2$ nicht-singuläre Diagonalmatrizen sind und $M_1$ eine „Repräsentativmatrix“ mit einer spezifischen kanonischen Form (erste Zeile und Spalte bestehen aus Einsen) ist.

Wesentliche methodische Schritte umfassen:

1. Herstellung von Verbindungen: Das Paper beweist, dass die Eigenschaften involutorisch, semi-involutorisch, orthogonal oder semi-orthogonal in vorhersagbarer Weise erhalten bleiben oder transformiert werden, wenn die diagonale Skalierung $D_1 M_1 D_2$ angewendet wird.
2. Ableitung von Zählbeziehungen: Durch die Analyse der Beschränkungen für $D_1$ und $D_2$, die erforderlich sind, damit eine Matrix $M$ bestimmte Eigenschaften erfüllt, leiten die Autoren bidirektionale Beziehungen zwischen den Zählungen der generalisierten Matrizen und ihrer konventionellen Gegenstücke ab.
3. Strukturelle Charakterisierung: Die Autoren leiten die allgemeine algebraische Struktur orthogonaler Matrizen beliebiger Ordnung $n$ über $\mathbb{F}_{2^m}$ her und spezialisieren dies auf $n=3$ und $n=4$.
4. Enumeration: Unter Verwendung bekannter Enumerationsergebnisse für involutorische MDS-Matrizen und der abgeleiteten strukturellen Beziehungen berechnen die Autoren die exakte Anzahl semi-involutorischer und semi-orthogonaler MDS-Matrizen für spezifische Ordnungen und Feldgrößen.

Wesentliche Beiträge und Ergebnisse

• Strukturelle Verbindungen: Das Paper stellt nicht-triviale Beziehungen zwischen semi-involutorischen und involutorischen Matrizen sowie zwischen semi-orthogonalen und orthogonalen Matrizen her. Insbesondere wird gezeigt, dass die Anzahl der $n \times n$ involutorischen MDS-Matrizen $(2^m - 1)^{n-1}$ mal die Anzahl der semi-involutorischen MDS-Matrizen der Form $M_1$ beträgt. Eine ähnliche Korrespondenz wird für semi-orthogonale und orthogonale Matrizen bewiesen.
• Enumeration von 3×3-Matrizen:
  • Orthogonale MDS: Die Autoren leiten eine explizite Formel für die Anzahl der $3 \times 3$ orthogonalen MDS-Matrizen über $\mathbb{F}_{2^m}$ als $(2^m - 2)(2^m - 3)(2^m - 4)$ her.
  • Semi-orthogonale MDS: Durch Nutzung der strukturellen Verbindung leiten sie die Anzahl der $3 \times 3$ semi-orthogonalen MDS-Matrizen als $(2^m - 1)^5(2^m - 2)(2^m - 3)(2^m - 4)$ her.
  • Semi-involutorische MDS: Das Paper liefert eine direkte Ableitung für die Anzahl der $3 \times 3$ semi-involutorischen MDS-Matrizen und bestätigt die Formel $(2^m - 1)^5(2^m - 2)(2^m - 4)$. Dies dient als Alternative zu früheren Beweisen in der Literatur.
• Schnittmenge der Eigenschaften: Die Autoren charakterisieren Matrizen, die sowohl semi-involutorisch als auch semi-orthogonal sind. Sie beweisen, dass für $3 \times 3$ Matrizen jede semi-involutorische Matrix der Form $M_1$ notwendigerweise symmetrisch ist, was impliziert, dass die Anzahl der Matrizen, die beide Eigenschaften besitzen, identisch mit der Anzahl der semi-involutorischen Matrizen ist.
• 4×4-Matrix-Enumeration: Die Studie wird auf $4 \times 4$ Matrizen ausgeweitet. Die Autoren berechnen die Anzahl der semi-involutorischen MDS-Matrizen für $m = 3, \dots, 8$ sowie die der orthogonalen/semi-orthogonalen Matrizen für $m = 3, 4$. Sie identifizieren zudem leichtgewichtige orthogonale MDS-Matrizen der Ordnung 4 basierend auf d-XOR-Gate-Zählungen und finden optimale Zählungen von 64 über $\mathbb{F}_{2^3}$ und 72 über $\mathbb{F}_{2^4}$.
• Allgemeine Struktur: Eine allgemeine Form für $n \times n$ orthogonale Matrizen über $\mathbb{F}_{2^m}$ wird abgeleitet, welche die letzte Zeile und Spalte in Abhängigkeit von den verbleibenden Submatrix-Elementen und spezifischen Summenbeschränkungen ausdrückt.

Bedeutung und Ansprüche
Das Paper beansprucht, einen einheitlichen Rahmen für das Verständnis der Enumeration von MDS-Matrizen mit spezifischen strukturellen Beschränkungen zu bieten. Durch die Verlagerung des Fokus von der Konstruktion auf strukturelle Beziehungen zeigen die Autoren, dass die Zählungen der generalisierten Varianten (semi-involutorisch/semi-orthogonal) direkt aus den Zählungen ihrer konventionellen Gegenstücke abgeleitet werden können.

Die Autoren geben an, dass ihre Arbeit Folgendes bietet:

1. Alternative Ableitungen: Eine direktere und prägnantere Ableitung der Zählformeln für $3 \times 3$ semi-involutorische und semi-orthogonale MDS-Matrizen im Vergleich zu bestehenden umfassenden Beweisen.
2. Neue Enumerationsdaten: Explizite Zählungen für $3 \times 3$ orthogonale MDS-Matrizen (zuvor in der Literatur nicht etabliert) und erweiterte Zählungen für $4 \times 4$ Matrizen über größeren endlichen Körpern.
3. Theoretische Einsicht: Ein Beweis, dass für $3 \times 3$ Matrizen die Schnittmenge der semi-involutorischen und semi-orthogonalen Eigenschaften mit der Menge der semi-involutorischen Matrizen zusammenfällt, eine Eigenschaft, die für höhere Ordnungen (z. B. $n \ge 4$) nicht notwendigerweise gilt.

Das Paper schließt mit dem Hinweis, dass diese Wechselwirkungen eine systematische Methode zur Bestimmung der Anzahl von MDS-Matrizen bieten, die zusätzlichen strukturellen Beschränkungen unterliegen, wodurch die expliziten Enumerationsformeln für mehrere algebraisch beschränkte $3 \times 3$ und $4 \times 4$ MDS-Klassen konsolidiert werden.