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 $𝔾𝔽(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\le t\le \frac{2^m-1}{m}$. Voor $m=11$ is bijvoorbeeld $t=32,t=70$ of $t=100$.
• Zoek een irreducibele monische polynoom $g\in 𝔾𝔽(2^m)[x]$ van graad $t$.
• Laat $h=\prod _i(x-a_i)\in 𝔾𝔽(n)[x]$.

In dit geval geldt dat $h=x^n-x\in 𝔾𝔽(2^m)[x]$.

Definitie

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

$\mathrm{\Gamma }=\mathrm{\Gamma }(a_1,a_2,\dots ,a_n,g)=\{c\in 𝔾𝔽(2^m):\sum _i{c}_i\frac{h}{x-a_i}modg=0\}$

De polynomen $\frac{h}{x-a_1}modg,\frac{h}{x-a_2}modg,\dots ,\frac{h}{x-a_n}modg$, kunnen gezien worden als vectoren over $𝔾𝔽(2)$.

Ze vormen een pariteitscontrole-matrix voor de code $\mathrm{\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 $\varphi \in 𝔾𝔽(2^m)[x]$ geldt dat de norm $|\varphi |=2^{\mathrm{deg}(\varphi )}$, met $\mathrm{deg}(\varphi )$ de graad van $\varphi$.

Bij rationale functies geldt $|\frac{\varphi }{\psi }|=\frac{|\varphi |}{|\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 $\mathrm{\Gamma }$. We starten met een woord $w\in {𝔾𝔽}^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 $𝔾𝔽(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 $𝔾𝔽(2^m)[x]/(g)$.
• Noem deze berekende wortel $s$ en bekijk deze in het lichaam $s\in 𝔾𝔽(2^m)[x]$. De graad van $s$ is kleiner dan $t$.
• De vectoren $(s,1)$ en $(g,0)$ genereren een rooster $L\subseteq 𝔾𝔽(2^m)[x{]}^2$.

De norm $|(\alpha ,\beta )|$ van een vector $(\alpha ,\beta )\in 𝔾𝔽(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 $ϵ={\alpha }_0^2+x{\beta }_0^2$
• Deel door de coëfficiënt van de hoogste macht van x, zodat $ϵ$ monisch wordt.
• Ontbindt $ϵ$ 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 $ϵ(a_i)=0$.

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