Shortest LCD embeddings of binary, ternary and quaternary linear codes

Probleemstelling
Lineaire codes met complementair dual (LCD-codes) vormen een belangrijk onderzoeksgebied binnen de coderingstheorie en cryptografie, met name vanwege hun weerstand tegen side-channel en fault injection aanvallen. Hoewel bekend is dat elke lineaire code over $\mathbb{F}_q$ ($q \ge 4$) equivalent is aan een LCD-code, en vergelijkbare resultaten bestaan voor $\mathbb{F}_{q^2}$, blijven de grenzen voor de minimale afstanden van LCD-codes over $\mathbb{F}_2$, $\mathbb{F}_3$ en Hermitische LCD-codes over $\mathbb{F}_4$ voor veel lengtes en dimensies onbekend. Een centrale uitdaging in de coderingstheorie is het bepalen van de grootste minimale afstand voor een gegeven lengte en dimensie. Dit artikel behandelt het specifieke probleem van het inbedden van willekeurige lineaire codes in LCD-codes, met als doel de "kortste" dergelijke inbedding te vinden (minimale toename van de lengte) en deze methode te gebruiken om nieuwe afstand-optimale LCD-codes te construeren.

Methodologie
De auteurs introduceren een systematische aanpak om een gegeven lineaire code $C$ in een LCD-code $\tilde{C}$ in te bedden door het minimum aantal kolommen aan de generatormatrix toe te voegen. De methodologie verloopt als volgt:

1. Theoretisch Fundament: Het artikel stelt vast dat het minimale aantal kolommen ($m$) dat vereist is om een $[n, k]$ code $C$ in een LCD-code in te bedden, exact gelijk is aan de dimensie $\ell$ van de hull van $C$ (waarbij $\text{Hull}(C) = C \cap C^\perp$). Bijgevolg is de lengte van de kortste LCD-inbedding $n + \ell$.
2. Structurele Karakterisering: De auteurs karakteriseren de generatormatrix van een kortste LCD-inbedding. Als $G$ een generatormatrix is van een code $C$, ontleed in een deel dat de hull genereert, $G(\text{Hull}(C))$, en een overblijvend deel $A$, dan wordt een kortste LCD-inbedding gegenereerd door een matrix van de vorm:
   $$\tilde{G} = \begin{bmatrix} G(\text{Hull}(C)) & D \\ A & C \end{bmatrix}$$
   waarbij $D$ een inverteerbare $\ell \times \ell$ matrix is en $C$ een willekeurige $(k-\ell) \times \ell$ matrix. Het artikel bewijst dat het aanhangen van een inverteerbare matrix aan de rijen die overeenkomen met de hull, en een willekeurige matrix aan de overige rijen, altijd een kortste LCD-inbedding oplevert.
3. Constructiestrategie: De auteurs passen deze inbeddingsmethode toe op bekende afstand-optimale lineaire codes (specifiek ternaire en quaternaire codes) die op zichzelf geen LCD-codes zijn. Door de hull-dimensie van deze bestaande codes te berekenen en de noodzakelijke kolommen volgens de afgeleide structuur toe te voegen, genereren zij nieuwe LCD-codes.

Belangrijkste Bijdragen en Resultaten
Het artikel biedt zowel theoretische grenzen als concrete constructies:

• Theoretische Resultaten:

  • Bewijst dat de lengte van de kortste LCD-inbedding van een $[n, k]$ code met hull-dimensie $\ell$ gelijk is aan $n + \ell$.
  • Karakteriseert alle mogelijke vormen van generatormatrices voor deze kortste inbeddingen, waarbij wordt aangetoond dat zij equivalent zijn aan het aanhangen van een inverteerbare matrix aan de hull-genererende rijen.
  • Demonstreert dat de lengte van de kortste LCD-inbedding van een code $C$ identiek is aan die van zijn hull, $\text{Hull}(C)$.

• Nieuwe Codeconstructies:
  Door de kortste LCD-inbeddingsmethode toe te passen op bestaande lineaire codes, hebben de auteurs verschillende nieuwe LCD-codes geconstrueerd met parameters die de bekende minimale afstanden verbeteren:

  • Ternaire LCD-codes:
    • $[23, 4, 14]$: Verbetert de bekende minimale afstand van 13 naar 14.
    • $[23, 5, 12]$: Verbetert de bekende minimale afstand van 11 naar 12.
    • $[24, 6, 12]$: Verbetert de bekende minimale afstand van 11 naar 12.
    • $[25, 5, 14]$: Verbetert de bekende minimale afstand van 13 naar 14.
  • Quaternaire Hermitische LCD-code:
    • $[21, 10, 8]$: Verbetert de bekende minimale afstand van 7 naar 8.

De auteurs merken op dat zij voor de nieuwe parameters $[23, 4, 14]$ en $[23, 5, 12]$ respectievelijk 226 en 38 inequente codes hebben gevonden. Deze codes zijn afstand-optimaal en inequent aan de reeds bekende codes in de BKLC (Best Known Linear Codes) database.

Significantie
Het artikel beweert dat de methode voor de kortste LCD-inbedding een nuttig instrument is voor het vinden van afstand-optimale LCD-codes over diverse velden. Door het precieze aantal kolommen te bepalen en hun structuur te karakteriseren, biedt de methode een constructieve weg om de minimale afstand van bekende lineaire codes te verbeteren wanneer deze worden omgezet naar LCD-codes. De resultaten tonen aan dat deze aanpak succesvol nieuwe codes oplevert met minimale afstanden die één groter zijn dan die van eerder bekende codes voor specifieke ternaire en quaternaire parameters.

Beperkingen en Toekomstige Richtingen
De auteurs erkennen een beperking in hun aanpak: aangezien de zoekruimte voor de aangehangen inverteerbare en willekeurige matrices excessief groot is, is het moeilijk om te garanderen dat de specifieke inbedding wordt gevonden die de absoluut grootste minimale afstand oplevert voor een gegeven code. Zij suggereren dat toekomstig onderzoek zich moet richten op het ontwikkelen van methoden om de aangehangen matrices strategischer te selecteren om de resulterende minimale afstand te maximaliseren, of om te bepalen of de aangehangen matrices tot op de equivalentie verder beperkt kunnen worden om de zoekruimte te verkleinen.