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

Technische Samenvatting: De Sluiting van LCD-naar-GI-Reducties via Generaliseerde Inproducten

1. Probleemstelling

Het Permutatie-equivalentieprobleem (PEP) voor lineaire codes vraagt of twee gegeven lineaire codes identiek zijn tot een coördinatenpermutatie. Dit probleem is fundamenteel voor zowel de classificatie van lineaire codes als de beveiligingsanalyse van code-gebaseerde cryptografie (bijvoorbeeld het LESS-handtekeningsschema en het SPECK-schema).

De complexiteit van PEP is nauw verbonden met het Graf-isomorfisme (GI)-probleem. Hoewel PEP over het algemeen als moeilijk wordt beschouwd, toonde een belangrijke doorbraak van Bardet et al. [3] aan dat PEP voor Linear Complementary Dual (LCD)-codes (codes met een triviale hull, d.w.z. $C \cap C^\perp = \{0\}$) in polynomiale tijd reduceert tot GI. Deze reductie beeldt een LCD-code af op een gewogen graaf via zijn orthogonale projector $\Pi_C = G^T(GG^T)^{-1}G$.

Deze methode is echter afhankelijk van het feit dat de Gram-matrix $GG^T$ niet-singulair is, wat de toepasbaarheid beperkt tot LCD-codes. Codes met niet-triviale hulls (waar $\dim(\text{Hull}(C)) \ge 1$) kunnen niet worden verwerkt door deze specifieke constructie. De centrale vraag die in dit artikel wordt behandeld is: Hoe ver kan de methode van de orthogonale projector worden uitgebreid? Specifiek: kan deze worden gegeneraliseerd tot codes met niet-triviale hulls door een andere bilineaire vorm te gebruiken, en zo ja, wat zijn dan de precieze structurele grenzen van een dergelijke reductie?

2. Methodologie

De auteurs generaliseren het standaard inproduct tot willekeurige niet-degenererende symmetrische bilineaire vormen die worden gerepresenteerd door een structuurmatrix $M$.

• Generaliseerde Projectoren: Zij definiëren een $M$-duale code $C^{\perp_M}$ en een $M$-hull $\text{Hull}_M(C)$. Voor een $M$-LCD-code (waar $\text{Hull}_M(C) = \{0\}$) construeren zij een generaliseerde orthogonale projector:
  $$\Pi_{C,M} = M G^T (G M G^T)^{-1} G$$
• Reductievoorwaarde: De kern van de reductie berust op de identiteit $\Pi_{CP, M} = P^T \Pi_{C,M} P$, waarbij $P$ een permutatiematrix is. Deze identiteit garandeert dat als twee codes permutatie-equivalent zijn, hun projectoren isomorf zijn als gewogen grafen.
• Karakterisering van $M$: De auteurs onderzoeken welke structuurmatrijzen $M$ voldoen aan de voorwaarde dat $P M P^T = M$ (of een scalair veelvoud daarvan) voor alle permutaties $P$. Dit is noodzakelijk om te waarborgen dat de projector zich correct gedraagt onder permutatie.
• Enumeratie en Algoritmen: Met behulp van karaktersommen over kwadratische vormen (specifiek de stelling van Weil) leiden de auteurs exacte enumeratieformules af voor het aantal reduceerbare codes. Zij construeren ook een algoritme in polynomiale tijd dat probeert een geschikte $M$ te vinden om een gegeven paar codes tot GI te reduceren.

3. Belangrijkste Bijdragen en Resultaten

A. Karakterisering van Geldige Structuurmatrijzen (Stelling 3.5)
Het artikel bewijst dat de methode van de orthogonale projector een geldige reductie oplevert ($C_1 \cong C_2 \iff \Pi_{C_1, M} \cong \Pi_{C_2, M}$) dan en slechts dan als de structuurmatrijs $M$ de volgende vorm heeft:
$$M = aI + bJ$$
waarbij $I$ de eenheidsmatrix is, $J$ de matrix met alleen enen is, en $a, b \in \mathbb{F}_q$ voldoen aan niet-degeneratievoorwaarden ($a \neq 0$ en $a + nb \neq 0$). Geen enkele andere niet-degenererende symmetrische bilineaire vorm staat deze reductie toe. Dit vestigt de sluiting van de aanpak met orthogonale projectoren: men kan de methode niet uitbreiden door willekeurige bilineaire vormen te kiezen; de vorm moet een lineaire combinatie zijn van de eenheidsmatrix en de matrix met alleen enen.

B. Volledige Karakterisering van Reduceerbare Codes (Stelling 4.5)
De auteurs bepalen precies welke codes een dergelijke reductie toelaten:

• Een code $C$ is GI-reduceerbaar via deze methode dan en slechts dan als:
  1. $C$ een LCD-code is (standaardgeval, $M=I$), OF
  2. $\dim(\text{Hull}(C)) = 1$ en de unieke hull-vector $x$ voldoet aan $(x, \mathbf{1}) \neq 0$ (waarbij $\mathbf{1}$ de vector met alleen enen is).
• Karakteristiek 2: In velden met karakteristiek 2 is de voorwaarde $(x, \mathbf{1}) \neq 0$ onmogelijk voor elke vector in de hull (aangezien $(x, x) = (x, \mathbf{1})^2 = 0$ impliceert dat $(x, \mathbf{1}) = 0$). Bijgevolg zijn alleen LCD-codes reduceerbaar in karakteristiek 2.
• Onmogelijkheid voor Hogere Hulls: Codes met $\dim(\text{Hull}(C)) \ge 2$ zijn bewezen niet reduceerbaar via de methode van de orthogonale projector, ongeacht de keuze van $M = aI + bJ$.

C. Enumeratieformules (Stelling 5.3)
Het artikel biedt exacte formules voor het tellen van het aantal GI-reduceerbare $[n, k]_q$-codes (voor oneven $q$). De telling is de som van:

1. Het aantal standaard LCD-codes, $L(n, k, q)$.
2. Het aantal codes met hull-dimensie 1 dat voldoet aan de voorwaarde voor coördinaten-som, afgeleid met behulp van de telling van isotrope vectoren met niet-nul coördinaten-sommen en de massavormules voor LCD-codes over quotiëntruimten met specifieke discriminanten.

D. Reductie-algoritme (Sectie 6)
Een algoritme in polynomiale tijd wordt gepresenteerd:

1. Controleer hull-dimensies. Als $\ge 2$, geef "niet GI-reduceerbaar" als output.
2. Als LCD, gebruik $M=I$.
3. Als hull-dimensie 1 is, zoek naar een scalair $b$ zodat $M = I + bJ$ beide codes $M$-LCD maakt.
4. Construeer de generaliseerde projectoren en los het resulterende Graf-isomorfisme-probleem op.

4. Betekenis en Claims

Het artikel claimt een volledige karakterisering te bieden van de mogelijkheden van de methode van de orthogonale projector.

• Sluiting: Het sluit definitief de deur voor het uitbreiden van de reductie van Bardet et al. tot codes met grote hulls ($\ge 2$) met behulp van deze specifieke techniek. Het bewijst dat de methode inherent beperkt is tot codes met hull-dimensie ten hoogste 1 (en alleen LCD-codes in karakteristiek 2).
• Structurele Grenzen: Het identificeert de specifieke algebraïsche structuur ($M = aI + bJ$) die vereist is voor de reductie om te werken, en toont aan dat geen enkele andere symmetrische bilineaire vorm deze afbeelding kan faciliteren.
• Cryptografische Implicaties: De resultaten bieden een criterium voor het selecteren van parameters in code-gebaseerde cryptografische schema's (zoals SPECK) om ervoor te zorgen dat zij hull-dimensies $\ge 2$ bezitten, waardoor ze buiten bereik komen van deze specifieke aanval via GI-reductie.

De auteurs sluiten af met een open vraag: of er andere reductiestrategieën (niet gebaseerd op orthogonale projectoren) bestaan die PEP voor codes met $\dim(\text{Hull}(C)) \ge 2$ kunnen afbeelden op GI, of dat dergelijke reducties bewezen onmogelijk zijn.