Goppa-code

Een binaire goppa-code, doorgaans alleen goppa-code genoemd, is een foutcorrigerende code. De code is genoemd naar de Russische wiskundige Velerii Denisovich Goppa. In McEliece-cryptografie wordt bijvoorbeeld gebruikgemaakt van binaire goppa-codes. Een binaire goppa-code is niet hetzelfde als een algebraïsche goppa-code.

Voorwaardes

Er zijn verschillende definities te geven voor een goppa-code. Hier wordt toegewerkt naar een polynomiale definitie. Voordat we dat kunnen doen zijn er enkele parameters nodig. De volgende gegevens zijn gebruikelijk voor een goppa-code:

• Kies ${\displaystyle n=2^{m}}$ met ${\displaystyle m\in \{10,11,12\}}$.
• De code is gedefinieerd over het lichaam ${\displaystyle \mathbb {GF} (n)}$. Noem de rij afzonderlijke elementen uit dat lichaam, ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$ lexicografisch geordend.
• Voor het aantal fouten ${\displaystyle t}$ die gecorrigeerd kunnen worden door de code, kiezen we ${\displaystyle 2\leq t\leq {\frac {2^{m}-1}{m}}}$. Voor ${\displaystyle m=11}$ is bijvoorbeeld ${\displaystyle t=32,t=70}$ of ${\displaystyle t=100}$.
• Zoek een irreducibele monische polynoom ${\displaystyle g\in \mathbb {GF} (2^{m})[x]}$ van graad ${\displaystyle t}$.
• Laat ${\displaystyle h=\prod _{i}(x-a_{i})\in \mathbb {GF} (n)[x]}$.

In dit geval geldt dat ${\displaystyle h=x^{n}-x\in \mathbb {GF} (2^{m})[x]}$.

Definitie

Een definitie van de goppa-code ${\displaystyle \Gamma }$, is nu

${\displaystyle {\Gamma }={\Gamma }(a_{1},a_{2},\ldots ,a_{n},g)=\{c\in \mathbb {GF} (2^{m}):\sum _{i}c_{i}{\frac {h}{x-a_{i}}}\mod g=0\}}$

De polynomen ${\displaystyle {\frac {h}{x-a_{1}}}{\bmod {g}},{\frac {h}{x-a_{2}}}{\bmod {g}},\ldots ,{\frac {h}{x-a_{n}}}{\bmod {g}}}$, kunnen gezien worden als vectoren over ${\displaystyle \mathbb {GF} (2)}$.

Ze vormen een pariteitscontrole-matrix voor de code ${\displaystyle \Gamma }$.

Algoritme van Patterson

In 1975 heeft Patterson een algoritme ontwikkeld om in polynomiale tijd ${\displaystyle t}$ fouten te kunnen corrigeren uit de goppa-code.

Voordat het algoritme weergegeven kan worden, is de definitie nodig van de norm van een polynoom.

Norm van een polynoom

Voor een polynoom ${\displaystyle \phi \in \mathbb {GF} (2^{m})[x]}$ geldt dat de norm ${\displaystyle |\phi |=2^{\deg(\phi )}}$, met ${\displaystyle \deg(\phi )}$ de graad van ${\displaystyle \phi }$.

Bij rationale functies geldt ${\displaystyle |{\frac {\phi }{\psi }}|={\frac {|\phi |}{|\psi |}}}$. Bijvoorbeeld ${\displaystyle |{\frac {x^{3}}{x^{5}-x}}|={\frac {|x^{3}|}{|x^{5}-x|}}={\frac {2^{3}}{2^{5}}}=2^{-2}}$.

Algoritme

Het doel is om maximaal ${\displaystyle t}$ fouten te verbeteren uit eengoppa-code ${\displaystyle \Gamma }$. We starten met een woord ${\displaystyle w\in \mathbb {GF} ^{n}(2)}$, met maximaal ${\displaystyle t}$ fouten. Dat betekent dat er een coodewoord ${\displaystyle c\approx w}$ is zodat er in het codewoord hoogstens ${\displaystyle t}$ maal een 1 met een 0 verwisseld is, of andersom.

• Bereken ${\displaystyle {\sum _{i}{\frac {w_{i}}{x-a_{i}}}}}$ over het lichaam ${\displaystyle \mathbb {GF} (2^{m})[x]/(g)}$. Als deze som nul is in het lichaam, dan zijn er blijkbaar geen fouten in de code. Het algoritme geeft dan output ${\displaystyle w}$.
• Bereken de wortel van ${\displaystyle {\frac {1}{\sum _{i}{\frac {w_{i}}{x-a_{i}}}}}-x}$ over het lichaam ${\displaystyle \mathbb {GF} (2^{m})[x]/(g)}$.
• Noem deze berekende wortel ${\displaystyle s}$ en bekijk deze in het lichaam ${\displaystyle s\in \mathbb {GF} (2^{m})[x]}$. De graad van ${\displaystyle s}$ is kleiner dan ${\displaystyle t}$.
• De vectoren ${\displaystyle (s,1)}$ en ${\displaystyle (g,0)}$ genereren een rooster ${\displaystyle L\subseteq \mathbb {GF} (2^{m})[x]^{2}}$.

De norm ${\displaystyle |(\alpha ,\beta )|}$ van een vector ${\displaystyle (\alpha ,\beta )\in \mathbb {GF} (2^{m})[x]^{2}}$ is per definitie gelijk aan de norm van de polynoom ${\displaystyle \alpha ^{2}+x\beta ^{2}}$.

Zo is de lengte van de vector ${\displaystyle (g,0)}$ gelijk aan ${\displaystyle |(g,0)|=|g^{2}|=2^{2t}}$.

• Vind met behulp van basisreductie een basis ${\displaystyle (\alpha _{0},\beta _{0})}$ van minimale lengte. Deze zal kleiner of gelijk zijn aan ${\displaystyle 2^{t}}$.
• Bereken ${\displaystyle \epsilon =\alpha _{0}^{2}+x\beta _{0}^{2}}$
• Deel door de coëfficiënt van de hoogste macht van x, zodat ${\displaystyle \epsilon }$ monisch wordt.
• Ontbindt ${\displaystyle \epsilon }$ in lineaire factoren van de vorm ${\displaystyle (x-a_{i})}$. Dit zullen ${\displaystyle t}$ factoren zijn.
• Output ${\displaystyle c}$, is de gecorrigeerd code ${\displaystyle w}$, met een correctie op de plaatsen ${\displaystyle i}$, waar ${\displaystyle \epsilon (a_{i})=0}$.

Voor een uitgebreid voorbeeld van dit algoritme wordt verwezen naar het artikel van Bernstein.^[1]