Goppa Codes

Een binaire Goppa Code, doorgaans alleen Goppa Code genoemd, is een foutencorrigerende code. De code is vernoemd naar de Russische wiskundige Velerii Denisovich Goppa. In McEliece-cryptografie wordt bijvoorbeeld gebruikgemaakt van Binaire Goppa Codes. Een Binaire Goppa Code is iets anders dan 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{F}_{2^m}=\mathbb{F}_n$. Noem de rij afzonderlijke elementen uit dat lichaam, $a_1, a_2, \dots , a_n$ lexicografisch geordend.
• Voor het aantal fouten dat gecorrigeerd kan worden door de code, t, kiezen we $2\leq t \leq \frac{2^{m}-1}{m}$. Voor $m = 11$ zijn bijvoorbeeld t = 32, t = 70, of t = 100.
• Neem nu $g\in\mathbb{F}_{2^m}[x]$ als een irreducibel monisch polynoom van graad t.
• Laat $h = \Pi_i(x-a_i)\in\mathbb{F}_n[x]$.

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

Definitie

Een definitie van de Goppa Code $\Gamma$, is nu

${\Gamma}={\Gamma}(a_1, a_2, ..., a_n, g)=\{c\in\mathbb{F}_2^n:\sum_i c_i\frac{h}{x - a_i}\mod g = 0\}.$

De polynomen $\frac{h}{x - a_1}\mod g, \frac{h}{x - a_2}\mod g, ... ,\frac{h}{x-a_n}\mod g$ , kunnen gezien worden als vectoren over $\mathbb{F}_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{F}_{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 een Goppa Code $\Gamma$. We starten met een woord $w\in\mathbb{F}^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{F}_{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{F}_{2^m}[x]/g$.
• Noem deze berekende wortel s en bekijk deze in het lichaam $s\in\mathbb{F}_{2^m}[x]$. De graad van s is kleiner dan t.
• De vectoren $(s,1)$ en $(g,0)$ genereren een rooster $L \subseteq \mathbb{F}_{2^m}[x]^2$.

De norm $|(\alpha,\beta)|$ van een vector $(\alpha,\beta)\in\mathbb{F}_{2^m}[x]^2$ is per definitie gelijk aan de norm van het 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