Two Families of Linear Codes Containing Non-GRS MDS Codes

1. Il Problema

Il lavoro si inserisce nel campo della teoria dei codici correttori, focalizzandosi sui codici MDS (Maximum Distance Separable), che raggiungono il limite di Singleton ($d = n - k + 1$). Sebbene i codici di Reed-Solomon generalizzati (GRS) siano la famiglia più nota e studiata di codici MDS, la loro struttura algebrica li rende vulnerabili ad attacchi crittografici specifici (come gli attacchi di Sidelnikov-Shestakov e Wieschebrink).

Il problema centrale è la classificazione e la costruzione di codici MDS che non siano equivalenti ai codici GRS (non-GRS). La congettura MDS suggerisce che, per certi parametri, tutti gli archi di dimensione massima nello spazio proiettivo finito siano curve razionali normali (equivalenti a codici GRS). Trovare codici MDS "non-GRS" è quindi cruciale sia per la teoria degli archi proiettivi che per la sicurezza crittografica, poiché offrono una resistenza superiore a tali attacchi. Inoltre, esiste un interesse crescente nella costruzione di codici auto-ortogonali e auto-duali (fondamentali per la teoria dei codici quantistici) all'interno di queste famiglie non-GRS.

2. Metodologia

Gli autori adottano un approccio costruttivo basato sulla modifica delle matrici generatrici dei codici GRS. La metodologia si articola nei seguenti punti:

• Costruzione delle Matrici Generatrici:
  • Famiglia $C_{i,j}$: Si ottiene rimuovendo due righe specifiche (la $(i+1)$-esima e la $(j+1)$-esima) dalla matrice generatrice di un codice Reed-Solomon di dimensione $k+2$.
  • Famiglia $C_{h,k}$: Si ottiene modificando la matrice generatrice di un codice GRS sostituendo la riga di grado $k-1$ con una riga di grado $h$ (dove $h \ge k$), creando una matrice di tipo Vandermonde generalizzata.
• Strumenti Matematici:
  • Funzioni Simmetriche: Utilizzo intensivo delle funzioni simmetriche elementari ($\sigma_t$) e complete ($S_t$) per analizzare i determinanti delle sottomatrici.
  • Prodotto di Schur (Hadamard): Utilizzo del prodotto di Schur ($C \star C$) e del suo rango dimensionale come criterio per distinguere i codici GRS da quelli non-GRS. Un codice MDS è GRS se e solo se $\dim(C \star C) = 2\dim(C) - 1$ (sotto certe condizioni di dimensione).
  • Matrici di Controllo di Parità: Derivazione esplicita delle matrici di controllo di parità ($H$) per verificare le proprietà di distanza minima.
  • Condizioni di Auto-ortogonalità: Analisi delle condizioni necessarie e sufficienti affinché $GG^T = 0$, utilizzando polinomi definiti sui punti di valutazione.

3. Contributi Chiave

A. Costruzione di Due Nuove Famiglie di Codici

Gli autori introducono due famiglie di codici lineari, $C_{i,j}$ e $C_{h,k}$, e ne determinano i parametri $[n, k, d]$.

• Per $C_{i,j}$, dimostrano che il codice è MDS se e solo se una specifica combinazione di funzioni simmetriche elementari sui punti di valutazione è non nulla.
• Per $C_{h,k}$, stabiliscono che la condizione MDS dipende dalla non nullità di una funzione simmetrica completa $S_{h-k+1}$ su sottoinsiemi di punti.

B. Caratterizzazione Non-GRS

Utilizzando il metodo del quadrato di Schur, gli autori provano che, sotto determinati vincoli sui parametri ($n, k, q$), queste famiglie contengono codici MDS che non sono equivalenti ai codici GRS.

• Dimostrano che per $C_{i,j}$ e $C_{h,k}$, la dimensione del quadrato di Schur è spesso $\ge 2k$, violando la condizione necessaria per essere un codice GRS (che richiederebbe $2k-1$).
• Questo risultato estende le famiglie note di codici non-GRS, fornendo esempi che non sono equivalenti a quelli costruiti in lavori precedenti (es. codici "twisted" o "generalized twisted").

C. Matrici di Controllo di Parità Esplicite

Una parte significativa del lavoro è dedicata alla derivazione esplicita delle matrici di controllo di parità per entrambe le famiglie. Queste matrici sono fondamentali per la decodifica e per l'analisi delle proprietà duali.

D. Codici Auto-ortogonali e Auto-duali

Gli autori investigano le condizioni per cui i codici modificati (con moltiplicatori scalari $v$) diventano auto-ortogonali o auto-duali:

• Derivano condizioni necessarie e sufficienti in termini della presenza di un polinomio $f(x)$ tale che $v_m^2 = u_m f(\alpha_m)$, dove $u_m$ sono coefficienti legati ai determinanti di Vandermonde.
• Forniscono condizioni specifiche per l'esistenza di codici auto-duali (dove $n=2k$), specialmente nel caso di campi con caratteristica pari.

4. Risultati Principali

1. Teoremi di Esistenza MDS: Sono stati stabiliti criteri necessari e sufficienti basati su funzioni simmetriche per garantire che le famiglie $C_{i,j}$ e $C_{h,k}$ siano codici MDS.
2. Nuovi Codici Non-GRS: È stata dimostrata l'esistenza di codici MDS non-GRS con lunghezze che possono raggiungere fino a $(q/p)^{1/4}$ (per $C_{i,j}$) e $(q/p)^{1/2}$ (per $C_{h,k}$), dove $q=p^m$.
3. Costruzioni Esplicite: Vengono forniti esempi numerici concreti (es. su campi $\mathbb{F}_{17}, \mathbb{F}_{25}, \mathbb{F}_{37}$) che mostrano la costruzione di codici con parametri specifici, inclusi codici auto-duali e auto-ortogonali.
4. Classificazione: Si dimostra che la famiglia $C_{h,k}$ contiene codici non equivalenti a quelli costruiti in lavori recenti (come [25, 23]), arricchendo la classificazione dei codici MDS nello spazio proiettivo.
5. Limiti di Lunghezza: Gli esempi mostrano che è possibile costruire codici non-GRS MDS di lunghezza $q+2$ (in casi specifici con $q$ pari) e $(q-1)/2$ (per $q$ dispari).

5. Significato e Implicazioni

• Sicurezza Crittografica: La disponibilità di nuove famiglie di codici MDS non-GRS offre alternative robuste per sistemi di crittografia basati sui codici (come il sistema McEliece), rendendoli resistenti agli attacchi strutturali che funzionano bene contro i codici GRS standard.
• Teoria dei Codici Quantistici: La caratterizzazione dei codici auto-ortogonali e auto-duali è essenziale per la costruzione di codici quantistici stabilizer (codici CSS), ampliando l'insieme di parametri disponibili per la correzione degli errori quantistici.
• Geometria Finita: Dal punto di vista teorico, questi risultati contribuiscono alla comprensione della struttura degli archi nello spazio proiettivo $PG(k-1, q)$, fornendo controesempi o nuove classi di archi che non sono curve razionali normali.
• Direzioni Future: Il lavoro apre la strada allo studio di codici ottenuti rimuovendo un numero arbitrario di righe dalla matrice di Vandermonde (generalizzazione di $C_{i,j}$), sebbene gli autori notino che questo comporta una complessità tecnica significativamente maggiore.

In sintesi, il paper fornisce un contributo sostanziale alla costruzione e classificazione dei codici MDS, offrendo strumenti matematici rigorosi per generare nuove famiglie di codici con proprietà ottimali di distanza e strutture algebriche non banali, con applicazioni dirette nella crittografia e nelle comunicazioni quantistiche.