Block Tensor Rank of Sum-Rank Metric Codes

Technische Samenvatting: Blok-tensorrang van Sum-Rank-metrische Codes

Probleemstelling
Sum-rank-metrische codes generaliseren zowel Hamming-metrische als rank-metrische codes door codewoorden weer te geven als tupels van matrices die zijn gepartitioneerd in vaste blokken, waarbij het gewicht wordt gedefinieerd als de som van de rangen van deze blokken. Hoewel de tensorrang-invariant voor rank-metrische codes (het minimum aantal rank-één matrices dat een code genereert) goed bestudeerd is, is er nog geen systematisch ontwikkelde invariant die aangepast is aan de blokstructuur van sum-rank-codes. Het artikel behandelt de uitdaging om een "blok-tensorrang" te definiëren en te berekenen voor sum-rank-codes die de blokdecompositie respecteert, wat verschilt van ondersteunings-theoretische invarianten en bestaande tensor-benaderingen voor equivalentie-testen.

Methodologie en Definities
De auteurs introduceren het concept van blok-eenvoudige tensoren, gedefinieerd als rank-één matrices die volledig binnen één enkel blok van de sum-rank-tuple worden ondersteund. De blok-tensorrang van een sum-rank-code $C$, aangeduid als $btrk(C)$, wordt gedefinieerd als het kleinste aantal blok-eenvoudige tensoren waarvan de lineaire span de code $C$ bevat.

De kern van de methodologische aanpak omvat:

1. Genererende Tupels: Het associëren van elke code met een tupel van 3-tensoren (één per blok) die de code genereren via lineaire afbeeldingen.
2. Blokgewijze Decompositie: Het bewijzen dat de blok-tensorrang van de gehele code de som is van de tensorrangen van de individuele blokprojecties. Dit reduceert het globale probleem tot standaard tensorrang-problemen op rank-metrische codes.
3. Coördinaat-Code Argument: Het construeren van een lineaire blokcode over het basisveld $\mathbb{F}_q$ (de "coördinaat-code") door codewoorden te mappen naar hun coëfficiënten ten opzichte van een blok-eenvoudige basis. Dit maakt de overdracht van klassieke Hamming-metrische grenzen naar de blok-tensorrang-setting mogelijk.

Belangrijkste Bijdragen en Resultaten

• Structurele Decompositie-stelling: Het artikel stelt vast dat $btrk(C) = \sum_{i=1}^t trk(\pi_i(C))$, waarbij $\pi_i(C)$ de projectie van de code is op het $i$-de blok en $trk$ de standaard tensorrang aanduidt. Deze identiteit impliceert dat het berekenen van de blok-tensorrang opsplitst in onafhankelijke tensorrang-berekeningen voor elk blok.
• Ondergrenzen: Twee complementaire ondergrenzen worden afgeleid:
  • Projectie-gewijze Grens: Afgeleid direct van de decompositie-stelling, stellende dat $btrk(C) \ge \sum N_q(k_i, d_i)$, waarbij $k_i$ en $d_i$ de dimensie en de minimale rank-afstand zijn van de $i$-de projectie.
  • Coördinaat-Code Grens: Afgeleid van de globale parameters $(k, d)$ van de code, stellende dat $btrk(C) \ge N_q(k, d)$, waarbij $N_q(k, d)$ de minimale lengte is van een lineaire code met dimensie $k$ en Hamming-afstand $d$.
  • Singleton en Griesmer Verfijningen: Door klassieke Singleton en Griesmer grenzen toe te passen op $N_q(k, d)$, leiden de auteurs de Singleton coördinaat-code grens ($btrk(C) \ge k + d - 1$) en de Griesmer coördinaat-code grens ($btrk(C) \ge G_q(k, d)$) af.
• Extreemwaarden:
  • BTR Codes: Codes die de Singleton coördinaat-code grens bereiken ($btrk(C) = k + d - 1$).
  • Blok-Tensorrang-Extreemale Codes: Codes die de scherpere grens $btrk(C) = N_q(k, d)$ bereiken.
• Constructies:
  • Blok-Diagonaal Lifting: Een algemene methode wordt geïntroduceerd om sum-rank-codes te construeren door klassieke lineaire blokcodes (de "backbone") naar matrixblokken te tillen via diagonale afbeeldingen.
  • BTR-families: Expliciete constructies van BTR-codes worden geleverd met behulp van MDS-backbones (bijv. Reed–Solomon codes) onder specifieke parameterregimes (Fat-block, Uniform MDS-backbone, en Pooling regimes).
  • Griesmer-Optimale Families: Met behulp van Griesmer-optimale backbones (bijv. Simplex en MacDonald codes) construeren de auteurs codes die de Griesmer coördinaat-code grens bereiken, welke extreem zijn maar niet noodzakelijkerwijs BTR wanneer $G_q(k, d) > k + d - 1$.
• Vergelijking met MSRD Codes: Het artikel demonstreert dat BTR-optimaliteit en MSRD-optimaliteit verschillend zijn. Specifiek, in het uniform MDS-backbone lifting-regime, kunnen codes niet simultaan de BTR-drempel en de uniforme MSRD-dimensie bereiken. Verder passen de auteurs hun projectie-gap criterium toe op bestaande constructies (Chen [19] en Lao et al. [20]), waarbij zij aantonen dat hoewel sommige dicht bij de BTR-drempel liggen, anderen (zoals bepaalde MSRD-codes) grote hiaten vertonen door hoge tensorrangen in hun blokprojecties.

Betekenis en Claims
Het artikel claimt het eerste systematische kader te bieden voor de analyse van sum-rank-codes vanuit het perspectief van de blok-aangepaste tensorrang. De betekenis ligt in:

1. Unificatie: Het verbinden van sum-rank-coderingstheorie met tensordecompositie-theorie en klassieke Hamming-metrische grenzen.
2. Computationele Reductie: De blokgewijze decompositie-stelling vereenvoudigt de berekening van de blok-tensorrang tot bekende rank-metrische tensorrang-problemen.
3. Nieuwe Optimaliteitscriteria: Het introduceren van BTR en blok-tensorrang-extreemale codes als nieuwe klassen van optimale codes, die verschillen van MSRD-codes.
4. Structurele Inzicht: De auteurs suggereren dat de blok-tensorrang dient als een maatstaf voor de "algebraïsche economie" van een code. Zij postuleren dat deze invariant relevant zou kunnen zijn voor het onderscheiden van gestructureerde codefamilies van willekeurige families in post-quantum cryptografie, hoewel zij geen specifieke cryptografische schema's of aanvallen voorstellen.

Het werk concludeert door openstaande problemen te identificeren, waaronder de classificatie van parameterregimes voor de existentie van BTR buiten lifting-constructies en het potentiële gebruik van de blok-tensorrang als een structurele onderscheider in code-gebaseerde cryptografie.