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 \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 𝔾 𝔽 (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 $Γ$ , is nu

Γ = Γ (a_{1}, a_{2}, \dots, a_{n}, g) = {c \in 𝔾 𝔽 (2^{m}) : \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, \dots, \frac{h}{x - a_{n}} mod g$ , kunnen gezien worden als vectoren over $𝔾 𝔽 (2)$ .

Ze vormen een pariteitscontrole-matrix voor de code $Γ$ .

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 $ϕ \in 𝔾 𝔽 (2^{m}) [x]$ geldt dat de norm $| ϕ | = 2^{\deg (ϕ)}$ , met $\deg (ϕ)$ de graad van $ϕ$ .

Bij rationale functies geldt $| \frac{ϕ}{ψ} | = \frac{| ϕ |}{| ψ |}$ . 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 $Γ$ . 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

| (α, β) |

van een vector

(α, β) \in 𝔾 𝔽 (2^{m}) [x]^{2}

is per definitie gelijk aan de norm van de polynoom

α^{2} + x β^{2}

.

Zo is de lengte van de vector

(g, 0)

gelijk aan

| (g, 0) | = | g^{2} | = 2^{2 t}

.

Vind met behulp van basisreductie een basis $(α_{0}, β_{0})$ van minimale lengte. Deze zal kleiner of gelijk zijn aan $2^{t}$ .
Bereken $ϵ = α_{0}^{2} + x β_{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.

Referenties

↑ Bernstein, Daniel J (2008). List decoding for binary Goppa codes, University of Illinois, Chicago.

[Bernstein-1] Bernstein, Daniel J (2008). List decoding for binary Goppa codes, University of Illinois, Chicago.