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

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

Definitie

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

${\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 ${\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 $\mathbb {GF} (2)$.

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

Algoritme van Patterson

In 1975 heeft Patterson een algoritme ontwikkeld om in polynomiale tijd $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 $\phi \in \mathbb {GF} (2^{m})[x]$ geldt dat de norm $|\phi |=2^{\deg(\phi )}$, met $\deg(\phi )$ de graad van $\phi$.

Bij rationale functies geldt $|{\frac {\phi }{\psi }}|={\frac {|\phi |}{|\psi |}}$. Bijvoorbeeld $|{\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 $t$ fouten te verbeteren uit eengoppa-code $\Gamma$. We starten met een woord $w\in \mathbb {GF} ^{n}(2)$, met maximaal $t$ fouten. Dat betekent dat er een coodewoord $c\approx w$ is zodat er in het codewoord hoogstens $t$ maal een 1 met een 0 verwisseld is, of andersom.

• Bereken ${\sum _{i}{\frac {w_{i}}{x-a_{i}}}}$ over het lichaam $\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 $w$.
• Bereken de wortel van ${\frac {1}{\sum _{i}{\frac {w_{i}}{x-a_{i}}}}}-x$ over het lichaam $\mathbb {GF} (2^{m})[x]/(g)$.
• Noem deze berekende wortel $s$ en bekijk deze in het lichaam $s\in \mathbb {GF} (2^{m})[x]$. De graad van $s$ is kleiner dan $t$.
• De vectoren $(s,1)$ en $(g,0)$ genereren een rooster $L\subseteq \mathbb {GF} (2^{m})[x]^{2}$.

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

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

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

Voor een uitgebreid voorbeeld van dit algoritme wordt verwezen naar het artikel van Bernstein.

Referenties