The Closure of LCD-to-GI Reductions via Generalized Inner Products

Sintesi Tecnica: La Chiusura delle Riduzioni da LCD a GI tramite Prodotti Interni Generalizzati

1. Enunciato del Problema

Il Problema dell'Equivalenza per Permutazione (PEP) per codici lineari chiede se due codici lineari dati siano identici a meno di una permutazione delle coordinate. Questo problema è fondamentale sia per la classificazione dei codici lineari sia per l'analisi della sicurezza della crittografia basata su codici (ad esempio, lo schema di firma LESS e lo schema SPECK).

La complessità del PEP è strettamente legata al problema dell'Isomorfismo di Grafi (GI). Sebbene il PEP sia generalmente considerato difficile, una svolta significativa di Bardet et al. [3] ha dimostrato che il PEP per codici Duali Complementari Lineari (LCD) (codici con un nucleo banale, ovvero $C \cap C^\perp = \{0\}$) si riduce a GI in tempo polinomiale. Questa riduzione mappa un codice LCD in un grafo pesato tramite il suo proiettore ortogonale $\Pi_C = G^T(GG^T)^{-1}G$.

Tuttavia, questo metodo si basa sul fatto che la matrice di Gram $GG^T$ sia non singolare, il che ne limita l'applicabilità ai soli codici LCD. I codici con nuclei non banali (dove $\dim(\text{Hull}(C)) \ge 1$) non possono essere elaborati da questa specifica costruzione. La domanda centrale affrontata in questo articolo è: fino a che punto può essere esteso il metodo del proiettore ortogonale? Nello specifico, può essere generalizzato ai codici con nuclei non banali utilizzando una forma bilineare diversa, e in tal caso, quali sono i limiti strutturali precisi di una tale riduzione?

2. Metodologia

Gli autori generalizzano il prodotto interno standard ad forme bilineari simmetriche non degeneri arbitrarie, rappresentate da una matrice strutturale $M$.

• Proiettori Generalizzati: Definisciono un codice $M$-duale $C^{\perp_M}$ e un $M$-nucleo $\text{Hull}_M(C)$. Per un codice $M$-LCD (dove $\text{Hull}_M(C) = \{0\}$), costruiscono un proiettore ortogonale generalizzato:
  $$\Pi_{C,M} = M G^T (G M G^T)^{-1} G$$
• Condizione di Riduzione: Il cuore della riduzione si basa sull'identità $\Pi_{CP, M} = P^T \Pi_{C,M} P$, dove $P$ è una matrice di permutazione. Questa identità garantisce che, se due codici sono equivalenti per permutazione, i loro proiettori siano isomorfi come grafi pesati.
• Caratterizzazione di $M$: Gli autori investigano quali matrici strutturali $M$ soddisfano la condizione per cui $P M P^T = M$ (o un suo multiplo scalare) per tutte le permutazioni $P$. Ciò è necessario per garantire che il proiettore si comporti correttamente sotto permutazione.
• Enumerazione e Algoritmi: Utilizzando somme di caratteri su forme quadratiche (in particolare il teorema di Weil), gli autori derivano formule di enumerazione esatte per il numero di codici riducibili. Costruiscono inoltre un algoritmo in tempo polinomiale che tenta di trovare una $M$ adatta per ridurre una data coppia di codici a GI.

3. Contributi e Risultati Chiave

A. Caratterizzazione delle Matrici Strutturali Valide (Teorema 3.5)
L'articolo dimostra che il metodo del proiettore ortogonale produce una riduzione valida ($C_1 \cong C_2 \iff \Pi_{C_1, M} \cong \Pi_{C_2, M}$) se e solo se la matrice strutturale $M$ ha la forma:
$$M = aI + bJ$$
dove $I$ è la matrice identità, $J$ è la matrice di tutti uni, e $a, b \in \mathbb{F}_q$ soddisfano condizioni di non degenerazione ($a \neq 0$ e $a + nb \neq 0$). Nessuna altra forma bilineare simmetrica non degenere permette questa riduzione. Ciò stabilisce la chiusura dell'approccio del proiettore ortogonale: non è possibile estendere il metodo scegliendo forme bilineari arbitrarie; la forma deve essere una combinazione lineare dell'identità e della matrice di tutti uni.

B. Caratterizzazione Completa dei Codici Riducibili (Teorema 4.5)
Gli autori determinano esattamente quali codici ammettono una tale riduzione:

• Un codice $C$ è riducibile a GI tramite questo metodo se e solo se:
  1. $C$ è un codice LCD (caso standard, $M=I$), OPPURE
  2. $\dim(\text{Hull}(C)) = 1$ e il vettore unico del nucleo $x$ soddisfa $(x, \mathbf{1}) \neq 0$ (dove $\mathbf{1}$ è il vettore di tutti uni).
• Caratteristica 2: Nei campi di caratteristica 2, la condizione $(x, \mathbf{1}) \neq 0$ è impossibile per qualsiasi vettore nel nucleo (poiché $(x, x) = (x, \mathbf{1})^2 = 0$ implica $(x, \mathbf{1}) = 0$). Di conseguenza, solo i codici LCD sono riducibili in caratteristica 2.
• Impossibilità per Nuclei Superiori: I codici con $\dim(\text{Hull}(C)) \ge 2$ sono dimostrabilmente non riducibili tramite il metodo del proiettore ortogonale, indipendentemente dalla scelta di $M = aI + bJ$.

C. Formule di Enumerazione (Teorema 5.3)
L'articolo fornisce formule esatte per contare il numero di codici $[n, k]_q$ riducibili a GI (per $q$ dispari). Il conteggio è la somma di:

1. Il numero di codici LCD standard, $L(n, k, q)$.
2. Il numero di codici con dimensione del nucleo 1 che soddisfano la condizione sulla somma delle coordinate, derivato utilizzando il conteggio dei vettori isotropi con somme delle coordinate non nulle e le formule di massa per i codici LCD su spazi quoziente con discriminanti specifici.

D. Algoritmo di Riduzione (Sezione 6)
Viene presentato un algoritmo in tempo polinomiale:

1. Controllare le dimensioni del nucleo. Se $\ge 2$, restituire "non riducibile a GI".
2. Se LCD, usare $M=I$.
3. Se la dimensione del nucleo è 1, cercare uno scalare $b$ tale che $M = I + bJ$ renda entrambi i codici $M$-LCD.
4. Costruire i proiettori generalizzati e risolvere il conseguente problema di Isomorfismo di Grafi.

4. Significato e Affermazioni

L'articolo afferma di fornire una caratterizzazione completa delle capacità del metodo del proiettore ortogonale.

• Chiusura: Chiude definitivamente la porta all'estensione della riduzione di Bardet et al. ai codici con nuclei grandi ($\ge 2$) utilizzando questa specifica tecnica. Dimostra che il metodo è intrinsecamente limitato ai codici con dimensione del nucleo al massimo 1 (e solo ai codici LCD in caratteristica 2).
• Limiti Strutturali: Identifica la specifica struttura algebrica ($M = aI + bJ$) richiesta affinché la riduzione funzioni, mostrando che nessuna altra forma bilineare simmetrica può facilitare questa mappatura.
• Implicazioni Crittografiche: I risultati offrono un criterio per la selezione dei parametri negli schemi crittografici basati su codici (come SPECK) per garantire che possiedano dimensioni del nucleo $\ge 2$, collocandoli così al di fuori della portata di questo specifico vettore di attacco basato sulla riduzione a GI.

Gli autori concludono ponendo una domanda aperta: se esistano altre strategie di riduzione (non basate su proiettori ortogonali) in grado di mappare il PEP per codici con $\dim(\text{Hull}(C)) \ge 2$ a GI, o se tali riduzioni siano dimostrabilmente impossibili.