Two Families of Linear Codes Containing Non-GRS MDS Codes

Titel: Zwei Familien linearer Codes, die nicht-GRS-MDS-Codes enthalten

1. Problemstellung und Motivation

Das Papier adressiert das Problem der Konstruktion und Klassifizierung von Maximum Distance Separable (MDS)-Codes, die nicht äquivalent zu verallgemeinerten Reed-Solomon (GRS)-Codes sind.

• Hintergrund: MDS-Codes erreichen die Singleton-Schranke ($d = n - k + 1$) und sind für Anwendungen in der verteilten Datenspeicherung, Kryptographie und Quanteninformationsverarbeitung von zentraler Bedeutung.
• Lücke: Die meisten bekannten MDS-Codes sind GRS-Codes. In der Kryptographie sind jedoch nicht-GRS-MDS-Codes entscheidend, da sie Widerstandsfähigkeit gegen spezifische Angriffe (wie Sidelnikov-Shestakov und Wieschebrink) bieten, gegen die GRS-Codes anfällig sind.
• Ziel: Die Autoren konstruieren zwei neue Familien linearer Codes, die explizit nicht-GRS-MDS-Eigenschaften aufweisen, und untersuchen deren Parity-Check-Matrizen sowie selbst-orthogonale und selbst-duale Eigenschaften.

2. Methodik

Die Autoren entwickeln ihre Konstruktionen durch gezielte Modifikation der Erzeugermatrizen von GRS-Codes:

• Familie 1 ($C_{i,j}$):

  • Konstruktion: Die Erzeugermatrix wird durch Entfernen der $(i+1)$-ten und $(j+1)$-ten Zeile aus der Erzeugermatrix eines Reed-Solomon-Codes der Länge $n$ und Dimension $k+2$ gebildet.
  • Analyse: Es werden explizite Parity-Check-Matrizen hergeleitet, die auf elementaren symmetrischen Funktionen und vollständigen symmetrischen Polynomen basieren.
  • MDS-Bedingung: Die MDS-Eigenschaft wird durch die Nicht-Null-Eigenschaft einer spezifischen Determinante charakterisiert, die sich aus den symmetrischen Funktionen der Stützpunkte ergibt.

• Familie 2 ($C_{h,k}$):

  • Konstruktion: Die Erzeugermatrix besteht aus den ersten $k-1$ Zeilen einer Vandermonde-Matrix (Potenzen $0$ bis $k-2$) sowie einer zusätzlichen Zeile mit der Potenz $h$ (wobei $h \ge k-1$).
  • Analyse: Ähnlich wie bei der ersten Familie werden Parity-Check-Matrizen konstruiert, die Bedingungen an die Stützpunkte $\Lambda$ stellen.

• Nachweis der Nicht-GRS-Eigenschaft:

  • Die Autoren verwenden die Schur-Quadrat-Methode (Schur-Square).
  • Kriterium (Lemma 2.1): Ein MDS-Code $C$ ist genau dann ein GRS-Code, wenn die Dimension seines Schur-Quadrats $C \star C$ gleich $2\dim(C) - 1$ ist.
  • Strategie: Die Autoren zeigen, dass für ihre konstruierten Codes die Dimension des Schur-Quadrats $\dim(C \star C) \ge 2k$ beträgt. Da dies größer als $2k-1$ ist, sind diese Codes per Definition nicht-GRS.

• Selbst-Orthogonalität und Selbst-Dualität:

  • Es werden notwendige und hinreichende Bedingungen hergeleitet, unter denen die skalierten Codes $C_{i,j,v}$ bzw. $C_{h,k,v}$ selbst-orthogonal ($C \subseteq C^\perp$) oder selbst-dual ($C = C^\perp$) sind.
  • Dies geschieht durch die Analyse der Gleichung $G G^T = 0$, was auf die Existenz bestimmter Polynome $f(x)$ führt, die die Skalierungsfaktoren $v_i$ mit den Lagrange-Gewichten $u_i$ verknüpfen.

3. Wichtige Beiträge und Ergebnisse

1. Konstruktion neuer Familien:

   • Einführung der Familien $C_{i,j}$ (durch Entfernen von Zeilen) und $C_{h,k}$ (durch Hinzufügen einer hohen Potenzzeile).
   • Herleitung expliziter Parity-Check-Matrizen für beide Familien.

2. Charakterisierung der MDS-Eigenschaft:

   • Es wurden notwendige und hinreichende Bedingungen für die MDS-Eigenschaft aufgestellt, die auf der Nicht-Null-Eigenschaft von Ausdrücken basieren, die symmetrische Funktionen der Stützpunkte enthalten (z. B. $\sigma_{k-i}\sigma_{k-j+1} - \sigma_{k-i+1}\sigma_{k-j} \neq 0$).

3. Nachweis der Nicht-GRS-Eigenschaft:

   • Es wurde bewiesen, dass beide Familien unter bestimmten Parametern (z. B. $k \ge 3$ oder $k \ge 4$) nicht-GRS-MDS-Codes enthalten.
   • Die Dimension des Schur-Quadrats wurde für verschiedene Fälle berechnet und zeigte Werte $\ge 2k$, was die Nicht-Äquivalenz zu GRS-Codes bestätigt.
   • Die Autoren zeigen, dass diese Codes nicht äquivalent zu anderen bekannten nicht-GRS-Codes (wie in [25, 23] beschrieben) sind, da ihre Schur-Quadrate eine höhere Dimension aufweisen.

4. Explizite Konstruktionen und Beispiele:

   • Es werden konkrete Beispiele für nicht-GRS-MDS-Codes über endlichen Körpern $\mathbb{F}_q$ gegeben.
   • Die Länge der Codes kann Werte bis zu $(q/p)^{1/4}$ (bei Familie 1) oder $(q/p)^{1/2}$ (bei Familie 2) erreichen, wobei $q=p^m$.
   • Spezielle Fälle für selbst-duale Codes werden identifiziert, insbesondere für gerade Charakteristik und bestimmte Stützpunkt-Mengen (z. B. $\Lambda = \mathbb{F}_q$).

5. Selbst-Orthogonalität:

   • Vollständige Charakterisierung der Bedingungen für selbst-orthogonale und selbst-duale Varianten dieser Codes, einschließlich der Konstruktion von Generator-Matrizen für solche Fälle.

4. Bedeutung und Ausblick

• Theoretische Bedeutung: Die Arbeit erweitert die Klassifizierung von MDS-Codes in endlichen projektiven Räumen. Sie liefert neue Beispiele für Bögen (arcs) in $PG(k-1, q)$, die keine normalen rationalen Kurven (GRS-Codes) sind.
• Praktische Relevanz:
  • Kryptographie: Die neuen nicht-GRS-Codes bieten verbesserte Sicherheit gegen algebraische Angriffe, die auf der Struktur von GRS-Codes basieren.
  • Quanten-Codes: Die Untersuchung selbst-orthogonaler und selbst-dualer Codes ist direkt anwendbar für die Konstruktion von stabilisatorbasierten Quanten-Codes (CSS-Codes).
• Zukünftige Forschung: Die Autoren identifizieren die Verallgemeinerung auf das Löschen einer beliebigen Anzahl von Zeilen aus der Vandermonde-Matrix (Code $C_I$) als nächste Herausforderung. Dies wird als technisch sehr anspruchsvoll eingestuft, da die Bedingungen für die MDS-Eigenschaft in diesem allgemeinen Fall erheblich komplexer werden.

Fazit: Das Papier liefert einen signifikanten Beitrag zur Theorie der linearen Codes durch die systematische Konstruktion und Charakterisierung neuer Familien von nicht-GRS-MDS-Codes, die sowohl theoretisch interessant als auch für kryptographische und quantentechnische Anwendungen relevant sind.