🔢 mathematics

Function-Based Minimal Linear Codes over Galois Rings $\mathrm{GR}(p^{n}, \ell)$ : Minimality Criteria and Infinite Constructions

Diese Arbeit erweitert die Theorie minimaler linearer Codes von endlichen Körpern auf Galois-Ringe, indem sie notwendige und hinreichende Kriterien für die Minimalität herleitet, neue Schranken für die Codelänge etabliert und auf dieser Grundlage mehrere unendliche Familien solcher Codes konstruiert.

Ursprüngliche Autoren: Biplab Chatterjee, Sihem Mesnager, Ratnesh Kumar Mishra, Makhan Maji, Kalyan Hansda

Veröffentlicht 2026-03-30

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Biplab Chatterjee, Sihem Mesnager, Ratnesh Kumar Mishra, Makhan Maji, Kalyan Hansda

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Architekt, der unsichtbare Mauern baut, um Geheimnisse zu schützen. In der Welt der Kryptographie und der sicheren Datenübertragung sind diese Mauern sogenannte lineare Codes. Sie sind wie ein komplexes Raster aus Zahlen, das Nachrichten verschlüsselt und sicherstellt, dass nur berechtigte Personen den Inhalt lesen können.

Dieser wissenschaftliche Artikel beschäftigt sich mit einer speziellen Art von Mauern: den minimalen linearen Codes. Aber statt auf dem gewohnten, einfachen Boden (den endlichen Körpern oder „Feldern") bauen die Autoren diese Mauern auf einem viel komplexeren Untergrund: den Galois-Ringen.

Hier ist die Erklärung des Papers in einfacher Sprache, mit ein paar kreativen Vergleichen:

1. Das Problem: Der Unterschied zwischen Feld und Ring

Stellen Sie sich endliche Felder (die alte Methode) wie ein perfekt geordnetes Dorf vor. Jeder Bürger (jede Zahl) hat eine klare Identität. Wenn Sie jemanden treffen, wissen Sie sofort, wer er ist. Es gibt keine „Zwischenzustände".

Galois-Ringe (die neue Methode in diesem Papier) sind wie eine viel dichtere, verworrenere Stadt. Hier gibt es nicht nur normale Bürger, sondern auch Nullteiler (Zero Divisors).

Die Analogie: Ein Nullteiler ist wie ein Bürger, der zwar existiert, aber wenn er mit einer anderen Person interagiert, verschwindet das Ergebnis im Nichts (es wird zu Null), obwohl beide Personen da waren.
Die Herausforderung: In dieser verworrenen Stadt ist es viel schwieriger, eine stabile Mauer zu bauen. Die Autoren sagen: „Wir müssen herausfinden, wie wir in dieser chaotischen Stadt die gleichen stabilen, minimalen Mauern bauen können wie im einfachen Dorf."

2. Was ist ein „minimaler Code"?

Ein minimaler Code ist wie ein Schlüsselbund, bei dem jeder Schlüssel genau so viel Information enthält, wie nötig ist, um ein Schloss zu öffnen, aber nichts mehr.

Wenn Sie einen Schlüssel haben, der eine bestimmte Tür öffnet, und ein anderer Schlüssel öffnet nur eine Teilmenge dieser Tür, dann ist der zweite Schlüssel eigentlich überflüssig oder eine „verschwendete" Version des ersten.
In einem minimalen Code gibt es keine solchen Verschwendungen. Jeder Code-Wort (jeder Schlüssel) ist einzigartig und unverzichtbar. Das ist extrem wichtig für Geheimhaltungspläne (Secret Sharing), bei denen eine Gruppe von Leuten zusammenarbeiten muss, um ein Geheimnis zu entschlüsseln. Man will sicherstellen, dass keine Teilgruppe das Geheimnis stehlen kann, indem sie nur einen Teil des Codes nutzt.

3. Die Lösung: Der „Funktionen-Baustoff"

Die Autoren nutzen eine clevere Methode, die sie von früheren Forschern übernommen und erweitert haben: Sie bauen ihre Codes aus Funktionen.

Die Metapher: Stellen Sie sich vor, Sie haben eine Maschine (eine Funktion), die Zahlen in andere Zahlen verwandelt. Die Autoren fragen sich: „Welche Art von Maschine müssen wir bauen, damit die resultierenden Codes immer minimal sind?"
Im einfachen Dorf (Feld) war die Antwort bekannt. Aber in der verworrenen Stadt (Galois-Ring) mit ihren Nullteilern war die Antwort unbekannt. Die Autoren haben nun die Baupläne für diese Maschinen gefunden.

4. Die große Entdeckung: Die fünf Typen von „Wächtern"

Das Herzstück des Papers ist die Erkenntnis, dass man nicht jeden einzelnen Code-Wort einzeln prüfen muss. Das wäre wie das Überprüfen jedes einzelnen Ziegelsteins in einer riesigen Mauer.
Stattdessen haben die Autoren gezeigt, dass man sich nur auf eine spezielle Gruppe konzentrieren muss: die Wurzeln-Wörter (Root Words).

Die Analogie: In dieser Stadt gibt es Bürger, die „fest im Boden stehen" (Root Words) und solche, die „wackelig" sind (Nullteiler). Die Autoren haben bewiesen: Wenn Sie sicherstellen, dass alle „festen Bürger" (Root Words) ihre Aufgabe perfekt erfüllen, dann funktioniert die ganze Mauer automatisch. Die „wackeligen" Bürger stören das System nicht so sehr, wie man dachte.
Sie haben diese Wächter in fünf verschiedene Kategorien eingeteilt und für jede Kategorie eine Regel gefunden, wie die Funktion (die Maschine) aussehen muss, damit alles stabil bleibt.

5. Das Ergebnis: Unendliche neue Familien von Codes

Das Paper liefert nicht nur die Theorie, sondern auch konkrete Baupläne.

Die Autoren zeigen, wie man unendlich viele verschiedene Arten von minimalen Codes konstruieren kann, die in diesen komplexen Galois-Ringen funktionieren.
Warum ist das toll? Bisher kannte man diese Codes nur für einfache Felder. Jetzt können Ingenieure und Kryptographen diese Codes in viel komplexeren Umgebungen einsetzen, zum Beispiel in der Post-Quanten-Kryptographie (Sicherheit gegen zukünftige Computer) oder in dezentralen Systemen wie Blockchain.

Zusammenfassung in einem Satz

Die Autoren haben die Baupläne für die sichersten, effizientesten Daten-„Schutzmauern" (minimale Codes) von einfachen, geraden Straßen auf komplexe, verwinkelte Gassen (Galois-Ringe) übertragen und dabei bewiesen, dass man durch das Verstehen weniger Schlüssel-Elemente (der Root Words) das gesamte System stabil halten kann.

Warum sollten wir das interessieren?
Weil unsere digitale Welt immer komplexer wird. Je komplexer die Mathematik hinter unseren Verschlüsselungen ist, desto schwerer ist es für Hacker, sie zu knacken. Dieses Papier gibt uns neue, stärkere Werkzeuge, um unsere Daten in einer unsicheren Zukunft zu schützen.

Titel:

Funktionsbasierte minimale lineare Codes über Galois-Ringen GR(pⁿ, ℓ): Minimalkriterien und unendliche Konstruktionen

1. Problemstellung und Motivation

Minimale lineare Codes sind ein fundamentaler Baustein in der Kryptographie, insbesondere für Secret-Sharing-Schemata, Multi-Party-Computation (MPC) und verifizierbares Secret-Sharing. Ein Code ist minimal, wenn jeder nicht-triviale Codewort nur von seinen skalaren Vielfachen „überdeckt" wird (d.h., das Trägermengen-Verhältnis impliziert Skalierung).

Während minimale Codes über endlichen Körpern (Feldern) intensiv erforscht wurden, stellt die Verallgemeinerung auf endliche Ringe, insbesondere Galois-Ringe $GR(p^n, \ell)$ , erhebliche algebraische Herausforderungen dar. Im Gegensatz zu Körpern enthalten Ringe Nullteiler und besitzen eine reichhaltigere Modulstruktur. Die Existenz von Nullteilern führt zu Torsionselementen, die die Struktur der orthogonalen Module verändern und die klassischen Minimalkriterien aus dem Feldfall ungültig machen.

Das Ziel dieser Arbeit ist es, notwendige und hinreichende Bedingungen für die Minimalität von Codes über $GR(p^n, \ell)$ zu etablieren und darauf aufbauend neue, unendliche Familien solcher Codes zu konstruieren.

2. Methodik und theoretischer Rahmen

Die Autoren nutzen eine Kombination aus Modultheorie, Frobenius-Dualität und der spezifischen Struktur von Galois-Ringen (Kettenringe).

Algebraische Struktur von $GR(p^n, \ell)$ :
- Der Ring ist ein endlicher lokaler Kettenring mit maximalem Ideal $\langle p \rangle$ und Restklassenkörper $\mathbb{F}_q$ ( $q=p^\ell$ ).
- Elemente besitzen eine $p$ -adische Entwicklung.
- Wichtige Unterscheidung zwischen Einheiten (Einheiten in $GR$) und Nullteilern (Elemente in $\langle p \rangle$ ).
- Der Ring ist ein Frobenius-Ring, was die Eigenschaft $(C^\perp)^\perp = C$ für lineare Codes $C$ garantiert.
Konzept der „Root Words" (Wurzelwörter):
Ein Vektor $v \in GR(p^n, \ell)^m$ wird als Root Word bezeichnet, wenn mindestens eine seiner Komponenten eine Einheit ist (äquivalent: $v \not\in p \cdot GR(p^n, \ell)^m$ ). Root Words verhalten sich analog zu nicht-trivialen Vektoren in Vektorräumen; ihre orthogonalen Module sind freie Module vom Rang $m-1$ . Vektoren, die keine Root Words sind (d.h. alle Komponenten sind Nullteiler), erzeugen orthogonale Module mit Torsion, die nicht frei sind.
McCoy-Rang:
Um lineare Unabhängigkeit über Ringen zu prüfen, wird der McCoy-Rang verwendet. Ein Matrix hat Rang $t$ über dem Ring genau dann, wenn ihre Reduktion modulo $p$ Rang $t$ über dem Restklassenkörper $\mathbb{F}_q$ hat.
Reduktionsprinzip:
Ein zentrales Ergebnis ist, dass für Codes der Dimension $m \ge 2$ die Minimalität des gesamten Codes vollständig durch die Minimalität der Root Words bestimmt wird. Torsionselemente (Nullteiler-Multiplikatoren) erzeugen keine neuen Hindernisse für die Minimalität, solange die Root Words die Kriterien erfüllen.

3. Hauptbeiträge und Ergebnisse

A. Charakterisierung der Minimalität

Die Autoren leiten notwendige und hinreichende Bedingungen her, unter denen ein linearer Code über $GR(p^n, \ell)$ minimal ist:

Satz 17: Ein $m$ -dimensionaler Code ( $m \ge 2$ ) ist genau dann minimal, wenn alle seine Root Words minimal sind.
Strukturelle Kriterien: Die Minimalität eines Codeworts $c(v)$ $c (v)$ wird auf die Existenz einer Basis $\{\beta_1, \dots, \beta_m\}$ ${β_{1}, \dots, β_{m}}$ zurückgeführt, die bestimmte Orthogonalitäts- und Synchronisationsbedingungen erfüllt.
- Für Einheits-Koeffizienten: $f(\beta_i) = w \cdot \beta_i$ .
- Für Nullteiler-Koeffizienten ( $d = p^r u$ ): $p^r f(\beta_i) = w \cdot \beta_i$ .

B. Funktionsbasierte Konstruktion

Basierend auf dem Framework von Wu et al. (für Felder) verallgemeinern die Autoren die Konstruktion auf Galois-Ringe. Ein Code $C_f$ wird durch die Auswertung einer Funktion $f: GR(p^n, \ell)^m \to GR(p^n, \ell)$ definiert.

Theorem 40 & 43: Es werden Kriterien für die Funktion $f$ formuliert, die garantieren, dass der resultierende Code minimal ist. Diese Kriterien hängen vom Hamming-Gewicht der Eingabevektoren und der Anzahl der Einheitskomponenten ab.
Theorem 45 (Polynome): Eine konkrete Klasse minimaler Codes wird durch multivariate Polynome konstruiert, deren Monome disjunkte Trägermengen haben und bestimmte Exponentenbedingungen erfüllen.

C. Parameter und Schranken

Längenschranken: Es werden explizite untere Schranken für die Länge $k$ eines minimalen Codes der Dimension $m$ über $GR(p^n, \ell)$ hergeleitet (z.B. $k > (m-1)q^n + q^{n-m}$ für $m \ge 3$ ).
Konstruktion: Es wird eine explizite Familie minimaler Codes mit Länge $k = \frac{m(m-1)}{2}(q^n + q^{n-1} - 2) + m$ vorgestellt, die die theoretischen Schranken bestätigt.
Spezialfall $n=1$ : Für $n=1$ reduziert sich der Ring auf den endlichen Körper $\mathbb{F}_q$ , und die Ergebnisse stimmen mit bekannten Resultaten überein, was die Korrektheit der Verallgemeinerung beweist.

4. Signifikanz und Implikationen

Verallgemeinerung der Theorie: Die Arbeit schließt die Lücke zwischen der Theorie minimaler Codes über Körpern und über Ringen. Sie zeigt, dass die komplexen Torsionsphänomene von Galois-Ringen durch die Analyse von Root Words und deren orthogonalen Modulen beherrschbar sind.
Neue Code-Familien: Durch die Konstruktion unendlicher Familien minimaler Codes über $GR(p^n, \ell)$ (und speziell über $\mathbb{Z}_{p^n}$ ) erweitert sich das Spektrum verfügbarer Codes für kryptographische Anwendungen.
Anwendungsbezug: Da minimale Codes direkt mit den Zugriffstrukturen von Secret-Sharing-Schemata korrelieren, ermöglicht diese Arbeit die Entwicklung effizienterer und sichererer Secret-Sharing-Protokolle, die auf Ring-basierten Kryptosystemen (z.B. Gitter-basierte Kryptographie oder Post-Quantum-Schemata) aufbauen.
Methodischer Fortschritt: Die Einführung der Synchronisationsbedingungen ( $p^r f(\beta) = w \cdot \beta$ ) für Nullteiler-Koeffizienten ist ein entscheidender technischer Durchschritt, der die algebraische Geometrie von Galois-Ringen in die Codetheorie integriert.

5. Fazit

Das Paper liefert einen umfassenden theoretischen Rahmen für minimale lineare Codes über Galois-Ringen. Es beweist, dass die Minimalitätseigenschaft trotz der Existenz von Nullteilern strukturell stabil bleibt, sofern die Root Words korrekt behandelt werden. Die vorgestellten Konstruktionen bieten eine systematische Methode zur Erzeugung neuer minimaler Codes mit anpassbaren Parametern, was für zukünftige Entwicklungen in der post-quanten Kryptographie und dezentralen Systemen (Blockchain) von hoher Relevanz ist.

Offene Probleme: Die Autoren identifizieren weitere Forschungsrichtungen, wie die Bestimmung der Gewichtsverteilung dieser Codes, die Konstruktion von Few-Weight-Codes und die Erweiterung der Kriterien auf allgemeine endliche Frobenius-Ringe.