Efficient Decoding of Twisted GRS Codes and Roth-Lempel Codes

Technische Samenvatting: Efficiënte Decoding van Geknikte GRS-codes en Roth–Lempel-codes

Probleemstelling
Maximum Distance Separable (MDS)-codes zijn fundamenteel voor betrouwbare communicatie, gedistribueerde opslag en geheimendeling. Hoewel Generalized Reed–Solomon (GRS)-codes de meerderheid van de bekende MDS-codes vormen en profiteren van goed begrepen algebraïsche structuren en efficiënte decoding-algoritmen, bezitten ze sterke algebraïsche structuren die schadelijk kunnen zijn in cryptografie op basis van codes (bijvoorbeeld vatbaar voor de Sidelnikov–Shestakov- en Wieschebrink-aanvallen). Bijgevolg zijn niet-GRS MDS-codes van aanzienlijk theoretisch en praktisch belang. Twee prominente families van dergelijke codes zijn Geknikte Generalized Reed–Solomon (TGRS)-codes en Roth–Lempel-codes.

Ondanks uitgebreid onderzoek naar de constructie en structurele eigenschappen van deze niet-GRS-codes, zijn hun decoding-algoritmen achtergebleven. Bestaande decoding-methoden voor TGRS-codes zijn grotendeels beperkt tot gevallen met één knik met een kwadratische tijdscomplexiteit ($O(n^2)$), en er zijn geen efficiënte decoding-algoritmen gerapporteerd voor Roth–Lempel-codes. Bovendien zijn huidige benaderingen beperkt tot unieke decoding binnen de klassieke straal van $\lfloor(n-k)/2\rfloor$, waardoor het potentieel voor lijstdecoding buiten deze straal voor deze families grotendeels onontgonnen blijft.

Methodologie
De auteurs stellen een unificerend raamwerk voor het decoderen van TGRS- en Roth–Lempel-codes voor, gebaseerd op het Guruswami–Sudan (GS)-lijstdecoding-algoritme. De kernstrategie omvat het benutten van de structurele relatie tussen deze niet-GRS-codes en standaard GRS-codes:

1. Geknikte GRS (TGRS)-codes: De auteurs observeren dat elke TGRS-code met pseudo-dimensie $k'$ een subcode is van een GRS-code met lengte $n$ en dimensie $k'$. Zij stellen een twee-traps decoding-proces voor:

   • Lijstgeneratie: Pas het bijna-lineaire Guruswami–Sudan-algoritme toe op de bevattende GRS-code $C_{GRS}(\alpha, v, k')$ om een lijst van kandidaat-polynomen te genereren.
   • Filtering: Filter deze lijst door te controleren of de kandidaat-polynomen voldoen aan de specifieke "knik"-beperkingen (d.w.z. of ze behoren tot de geknikte polynoomruimte $P_{TGRS}(k, T)$). Deze filterstap is efficiënt en vereist slechts coëfficiëntvergelijkingen.

2. Roth–Lempel-codes: De auteurs maken gebruik van de observatie dat het puncturen van een Roth–Lempel-code op de laatste coördinaat een standaard GRS-code oplevert. De decoding-procedure omvat:

   • Puncturing: Verwijder de laatste coördinaat van het ontvangen woord.
   • Lijstgeneratie: Pas het Guruswami–Sudan-algoritme toe op de gepuncteerde GRS-code.
   • Her-encoding en verificatie: Her-encodeer elke kandidaat-polynoom tot een volledig Roth–Lempel-codewoord en behoud alleen die kandidaten waarvan de Hamming-afstand tot het originele ontvangen woord binnen de decodingstraal ligt.

3. AMD-ondersteunde decoding: Om ambiguïteit op te lossen wanneer de lijstgrootte groter is dan één (d.w.z. buiten de straal voor unieke decoding), integreren de auteurs Algebraic Manipulation Detection (AMD)-codes. Berichten worden vooraf gecodeerd met een systematisch AMD-label voordat ze worden gecodeerd met TGRS of Roth–Lempel. Tijdens decoding worden kandidaten in de outputlijst geverifieerd tegen het AMD-label, waardoor het juiste bericht met hoge waarschijnlijkheid kan worden geïdentificeerd.

Belangrijkste bijdragen en resultaten

• Decoding met bijna-lineaire tijd: Het artikel presenteert de eerste expliciete decoding-algoritmen voor Roth–Lempel-codes en verbetert aanzienlijk bestaande TGRS-decoders. Onder geschikte parametercondities (specifiek voor codes met vaste snelheid) bereiken zowel lijst- als unieke decoding-algoritmen een looptijd van $O(n \log^2 n \log \log n)$, wat een verbetering is ten opzichte van de eerder bestbekende complexiteit van $O(n^2)$.
• Uitgebreide knikcapaciteit voor TGRS: De voorgestelde TGRS-decoder ondersteunt een aantal knikken $\ell$ tot $O(n \log^2 n \log \log n)$ (en tot $O(n^2)$ voor codes met vaste snelheid onder specifieke beperkingen), een aanzienlijke verbetering ten opzichte van eerdere werken die beperkt waren tot het geval met één knik ($\ell=1$).
• Buiten de straal voor unieke decoding: De algoritmen fungeren als lijstdecoders die in staat zijn fouten te corrigeren buiten de klassieke straal voor unieke decoding van $\lfloor(n-k)/2\rfloor$.
  • Voor TGRS-codes is de lijstdecodingstraal $\tau < n - \sqrt{n(k'-1)}$, waarbij $k'$ de pseudo-dimensie is.
  • Voor Roth–Lempel-codes is de straal $\tau < (n-1) - \sqrt{(n-1)(k-1)}$.
• Voorwaarden voor unieke decoding: De auteurs leiden voorwaarden af waaronder de lijstdecoder een unieke oplossing oplevert, waardoor efficiënte unieke decoders worden geboden voor MDS TGRS- en Roth–Lempel-codes. Voor TGRS is unieke decoding gegarandeerd wanneer $k' < \frac{(n+k)^2}{4n} + 1$.
• AMD-integratie: Het artikel biedt een expliciete afweging tussen redundantie en foutkans voor het AMD-ondersteunde raamwerk. Door een klein aantal redundantiesymbolen toe te voegen (bijvoorbeeld vier symbolen), kan de kans dat het unieke verzonden bericht niet uit de lijst wordt geïdentificeerd, worden gereduceerd tot $O(1/q)$.

Betekenis
Het artikel beweert kritieke gaten in de decoding-theorie van niet-GRS MDS-codes aan te vullen. Door aan te tonen dat TGRS- en Roth–Lempel-codes kunnen worden gedecodeerd met bijna-lineaire complexiteit, verwijdert dit werk een belangrijke barrière voor hun praktische implementatie. Het vermogen om een super-constant aantal knikken in TGRS-codes te verwerken is bijzonder significant voor cryptografische toepassingen, aangezien recente cryptanalytische resultaten suggereren dat schema's die slechts een constant aantal knikken gebruiken, kwetsbaar zijn. Bovendien opent het leveren van de eerste efficiënte decoders voor Roth–Lempel-codes de deur tot het gebruik van deze codefamilie in scenario's die hoge foutcorrectie vereisen of specifieke structurele eigenschappen die verschillen van GRS-codes. De integratie van AMD-codes biedt een praktisch mechanisme om unieke berichten te herstellen uit lijstoutput, waardoor de kloof tussen theoretische lijstdecoding-mogelijkheden en praktische eisen voor unieke decoding wordt overbrugd.