Two Families of Linear Codes Containing Non-GRS MDS Codes

Titel: Twee families van lineaire codes die niet-GRS MDS-codes bevatten

1. Probleemstelling en Context

Het artikel richt zich op de theorie van Maximum Distance Separable (MDS) codes over een eindig veld $\mathbb{F}_q$. MDS-codes zijn van groot belang in cryptografie, opslagystemen en combinatoriek omdat ze de maximale foutoplossende capaciteit bieden voor een gegeven code-lengte $n$ en dimensie $k$ (volgens de Singleton-richtlijn $d = n - k + 1$).

Een bekende en veelbestudeerde familie van MDS-codes zijn de Veralgemeende Reed-Solomon (GRS) codes. Echter, in de cryptografie is het vaak wenselijk om MDS-codes te gebruiken die niet equivalent zijn aan GRS-codes (zogenoemde non-GRS MDS-codes). GRS-codes zijn kwetsbaar voor specifieke cryptografische aanvallen (zoals de Sidelnikov-Shestakov-aanval), terwijl non-GRS-codes hier beter bestand tegen zijn.

De uitdaging ligt in het construeren van nieuwe families van non-GRS MDS-codes met specifieke parameters en het bepalen van hun eigenschappen, zoals zelf-orthogonaliteit en zelf-dualiteit, wat essentieel is voor toepassing in kwantumcodering. Hoewel er al families zijn gevonden (zoals "twisted" Reed-Solomon codes), blijft de zoektocht naar nieuwe, niet-equivalente families relevant voor zowel theoretische classificatie als praktische veiligheid.

2. Methodologie

De auteurs construeren twee nieuwe families van lineaire codes door de generatormatrices van bestaande GRS-codes te modificeren. De kern van hun aanpak omvat:

• Constructie via rijverwijdering en -aanpassing:
  • Famili 1 ($C_{i,j}$): Deze code wordt gegenereerd door de $(i+1)$-de en $(j+1)$-de rijen te verwijderen uit de generatormatrix van een GRS-code met parameters $[n, k+2]$. Dit resulteert in een code met dimensie $k$.
  • Famili 2 ($C_{h,k}$): Deze code wordt gegenereerd door een matrix $G_{h,k}$ te gebruiken die bestaat uit de eerste $k-1$ rijen van een Vandermonde-matrix (krachten $0$ tot $k-2$) en één extra rij met de $h$-de machten ($\alpha^h$), waarbij $h \ge k-1$.
• Analyse van de MDS-eigenschap:
  • De auteurs gebruiken Lemma 2.2, dat stelt dat een code MDS is dan en slechts dan als elke $k \times k$ submatrix van de generatormatrix niet-singulier is.
  • Ze maken gebruik van symmetrische functies (elementaire symmetrische functies $\sigma_t$ en complete symmetrische functies $S_t$) om determinanten van deze aangepaste matrices te analyseren.
• Identificatie van Non-GRS-eigenschap:
  • Om te bewijzen dat de codes niet equivalent zijn aan GRS-codes, gebruiken ze de Schur-kwadraat-methode (Hadamard-product).
  • Volgens Lemma 2.1 is een MDS-code $C$ met dimensie $k \le n/2$ een GRS-code dan en slechts dan als de dimensie van het Schur-kwadraat $C \star C$ gelijk is aan $2k - 1$. Als $\dim(C \star C) \ge 2k$, is de code een non-GRS MDS-code.
• Zelf-orthogonaliteit en Zelf-dualiteit:
  • Ze onderzoeken onder welke voorwaarden de codes zelf-orthogonaal ($C \subseteq C^\perp$) of zelf-dual ($C = C^\perp$) zijn. Dit gebeurt door de voorwaarde $G G^T = 0$ te analyseren en oplossingen te zoeken voor specifieke systemen van lineaire vergelijkingen die verband houden met de elementen van het veld.

3. Belangrijkste Bijdragen en Resultaten

A. Constructie van twee nieuwe families

De auteurs introduceren de families $C_{i,j}$ (met $1 \le i < j \le k$) en $C_{h,k}$ (met $3 \le k \le h \le n-1$). Voor beide families hebben ze expliciete pariteitscheck-matrices afgeleid.

B. Voorwaarde voor MDS-eigenschap

• Voor $C_{i,j}$: De code is MDS dan en slechts dan als een specifieke combinatie van elementaire symmetrische functies van elke subset van $k$ punten uit de evaluatiepunten $\Lambda$ niet nul is.
  • Voorwaarde: $\sigma_{k-i}(\beta)\sigma_{k-j+1}(\beta) - \sigma_{k-i+1}(\beta)\sigma_{k-j}(\beta) \neq 0$.
• Voor $C_{h,k}$: De code is MDS dan en slechts dan als de complete symmetrische functie $S_{h-k+1}$ van elke subset van $k$ punten niet nul is.
  • Voorwaarde: $S_{h-k+1}(\beta_1, \dots, \beta_k) \neq 0$.

C. Bewijs van Non-GRS Eigenschap

De auteurs bewijzen dat voor specifieke bereiken van parameters (bijvoorbeeld $k \ge 5$ of specifieke relaties tussen $h$ en $k$), de dimensie van het Schur-kwadraat strikt groter is dan $2k-1$.

• Dit betekent dat deze codes niet equivalent zijn aan GRS-codes.
• Ze tonen aan dat deze families codes bevatten die niet equivalent zijn aan eerdere constructies uit de literatuur (zoals die in [25, 23]), wat de classificatie van MDS-codes uitbreidt.
• Ze geven expliciete constructies voor codes met lengte tot $O(q^{1/4})$ en $O(q^{1/2})$ afhankelijk van de familie.

D. Zelf-orthogonaliteit en Zelf-dualiteit

De auteurs geven noodzakelijke en voldoende voorwaarden voor het bestaan van zelf-orthogonale en zelf-dual versies van deze codes (door vermenigvuldiging met een vector $v$):

• Zelf-orthogonaliteit: Er moet een polynoom $f(x)$ bestaan zodanig dat $v_m^2 = u_m f(\alpha_m)$, waarbij $u_m$ gerelateerd is aan de inverse van de Vandermonde-determinant.
• Zelf-dualiteit: Voor $n=2k$ worden specifieke voorwaarden afgeleid. Bijvoorbeeld, voor de familie $C_{h,k}$ is een zelf-dual code mogelijk als $r=1$ (dus $h=k$) en de som van de evaluatiepunten $S_1 = 0$ is.
• Ze presenteren concrete voorbeelden van zelf-dual codes over velden met karakteristiek 2 en oneven karakteristiek.

4. Significatie en Toekomstperspectief

• Cryptografische Veiligheid: De geconstrueerde non-GRS MDS-codes bieden een alternatief voor GRS-codes in cryptografische systemen, waardoor ze resistent zijn tegen aanvallen die specifiek zijn ontworpen voor de algebraïsche structuur van GRS-codes.
• Theoretische Uitbreiding: Het werk verrijkt de classificatie van MDS-codes in eindige projectieve ruimten. Het bevestigt dat er meer dan alleen "normale rationale krommen" (GRS-codes) bestaan die de MDS-eigenschap bezitten, zelfs in gevallen waar de MDS-vermoeden (MDS conjecture) vaak wordt geanalyseerd.
• Kwantumcodering: De resultaten over zelf-orthogonale en zelf-dual codes zijn direct toepasbaar in de constructie van stabilisatorcodes voor kwantuminformatieprocessing.
• Toekomstig Werk: De auteurs identificeren de generalisatie naar codes $C_I$ (waarbij een willekeurig aantal rijen uit de Vandermonde-matrix wordt verwijderd) als een belangrijke, maar technisch zeer uitdagende richting voor toekomstig onderzoek. De voorwaarden voor MDS worden hierbij aanzienlijk complexer.

Conclusie

Dit artikel levert een significante bijdrage aan de coderingstheorie door twee nieuwe, expliciete families van lineaire codes te introduceren die MDS-eigenschappen bezitten en strikt non-GRS zijn. Door het gebruik van symmetrische functies en de Schur-kwadraat-methode, hebben de auteurs niet alleen de bestaande kennis over de classificatie van MDS-codes uitgebreid, maar ook praktische constructies geleverd voor zelf-orthogonale en zelf-dual codes met potentiële toepassingen in beveiligde communicatie en kwantumcomputing.