Code binaire Goppa

En mathématiques et en informatique , le code binaire Goppa est un code correcteur d'erreurs qui appartient à la classe des codes Goppa généraux décrits à l'origine par Valerii Denisovich Goppa , mais la structure binaire lui confère plusieurs avantages mathématiques par rapport aux variantes non binaires, offrant également une meilleure adéquation à une utilisation courante en informatique et en télécommunication. Les codes binaires Goppa ont des propriétés intéressantes adaptées à la cryptographie dans les cryptosystèmes de type McEliece et des configurations similaires.

Un code Goppa binaire irréductible est défini par un polynôme de degré sur un corps fini sans racines répétées, et une séquence d' éléments distincts de qui ne sont pas des racines de .

Les mots de code appartiennent au noyau de la fonction syndrome, formant un sous-espace de :

Le code défini par un tuple a une dimension d'au moins et une distance d'au moins , il peut donc encoder des messages d'une longueur d'au moins en utilisant des mots de code de taille tout en corrigeant les erreurs d'au moins . Il possède une matrice de contrôle de parité pratique sous la forme

Il faut noter que cette forme de matrice de contrôle de parité, composée d'une matrice de Vandermonde et d'une matrice diagonale , partage la forme avec les matrices de contrôle des codes alternatifs , ainsi des décodeurs alternatifs peuvent être utilisés sur cette forme. De tels décodeurs n'offrent généralement qu'une capacité de correction d'erreur limitée (dans la plupart des cas ).

À des fins pratiques, la matrice de contrôle de parité d'un code Goppa binaire est généralement convertie en une forme binaire plus conviviale pour l'ordinateur par une construction de trace, qui convertit la matrice -by- en une matrice binaire -by- en écrivant les coefficients polynomiaux des éléments sur des lignes successives.

Le décodage des codes binaires Goppa est traditionnellement effectué par l'algorithme de Patterson, qui offre une bonne capacité de correction d'erreurs (il corrige toutes les erreurs de conception) et est également assez simple à mettre en œuvre.

L'algorithme de Patterson convertit un syndrome en un vecteur d'erreurs. Le syndrome d'un mot binaire devrait prendre une forme

Une forme alternative d'une matrice de contrôle de parité basée sur la formule peut être utilisée pour produire un tel syndrome avec une simple multiplication de matrice.

L'algorithme calcule ensuite . Cela échoue lorsque , mais c'est le cas lorsque le mot d'entrée est un mot de code, donc aucune correction d'erreur n'est nécessaire.

Enfin, le polynôme localisateur d'erreur est calculé comme . Notez que dans le cas binaire, la localisation des erreurs suffit à les corriger, car il n'y a qu'une seule autre valeur possible. Dans les cas non binaires, un polynôme de correction d'erreur distinct doit également être calculé.

Si le mot de code d'origine était décodable et que c'était le vecteur d'erreur binaire, alors

La factorisation ou l’évaluation de toutes les racines de donne donc suffisamment d’informations pour récupérer le vecteur d’erreur et corriger les erreurs.

Les codes Goppa binaires considérés comme un cas particulier de codes Goppa ont la propriété intéressante de corriger toutes les erreurs, alors que seules les erreurs dans les cas ternaires et dans tous les autres cas sont corrigées. Asymptotiquement, cette capacité de correction d'erreurs répond à la célèbre limite de Gilbert–Varshamov .

En raison de la capacité de correction d'erreur élevée par rapport au taux de code et à la forme de la matrice de contrôle de parité (qui est généralement difficilement distinguable d'une matrice binaire aléatoire de rang complet), les codes binaires Goppa sont utilisés dans plusieurs cryptosystèmes post-quantiques , notamment le cryptosystème McEliece et le cryptosystème Niederreiter .

• Elwyn R. Berlekamp, ​​Goppa Codes, IEEE Transactions on information theory, vol. IT-19, n° 5, septembre 1973, https://web.archive.org/web/20170829142555/http://infosec.seu.edu.cn/space/kangwei/senior_thesis/Goppa.pdf
• Daniela Engelbert, Raphael Overbeck, Arthur Schmidt. « Résumé des cryptosystèmes de type McEliece et de leur sécurité ». Journal of Mathematical Cryptology 1, 151–199. MR 2345114. Version précédente : http://eprint.iacr.org/2006/162/
• Daniel J. Bernstein. « Décodage de liste pour les codes binaires Goppa. » http://cr.yp.to/codes/goppalist-20110303.pdf