Vidéo pédagogique
Notice
Sous-titrage
Anglais
Langue :
Anglais
Crédits
Irene Marquez-Corbella (Intervention), Nicolas Sendrier (Intervention), Matthieu Finiasz (Intervention)
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
DOI : 10.60527/zctf-dm62
Citer cette ressource :
Irene Marquez-Corbella, Nicolas Sendrier, Matthieu Finiasz. Inria. (2015, 5 mai). 3.1. From Generic Decoding to Syndrome Decoding , in 3: Message Attacks (ISD). [Vidéo]. Canal-U. https://doi.org/10.60527/zctf-dm62. (Consultée le 13 juillet 2025)
logo Inria
Inria - Institut national de recherche en sciences et technologies du numérique
S'abonner
Contacter

3.1. From Generic Decoding to Syndrome Decoding

Réalisation : 5 mai 2015 - Mise en ligne : 20 février 2017
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

Welcome to the third week of the MOOC oncode-based cryptography. This week, we willlearn about message attacks. Among the ten sessions ofthis week, the first six will present the most essentialpart of generic decoding and the last four will bedevoted to more advanced matters. The first session isabout generic decoding; a   presentation of what a messageattack and what generic decoding is about. A cryptogram in the McElieceencryption scheme has the following form. A cryptogram is composedby multiplying a message by a public key andadding a random error. The adversary knows thecryptogram and the public key and wish to recover the messageor, equivalently, the error. Without any additionalinformation on the public key, solving that problem iscalled generic decoding. Generic decoding, incontrast with the usual situation where the code is known inadvance, takes as argument a q-ary linear code. It can be either agenerator matrix, or a parity check matrix.
In the first case, we speakof generic decoding; it takes as argument a vector,presumably noisy, and a generator matrix and will return a message. The desirable feature ofa generic decoder is to succeed in removing anerror "e" as long as this error is small enough. Bysmall, I mean small hamming weight. A generic syndromedecoder will take as argument a syndrome and a parity check matrix. It will succeed if itmanages to correct an error whenever the weight ofthe error is small enough. Those two kind of decodersare equivalent and so, in the sequel of this course, we wouldonly consider syndrome decoding. Syndrome decoding isan NP complete problem. It takes as argument amatrix, parity check matrix H, a syndrome s and an integerw, and try to return an error pattern that willcorrespond to this syndrome. In fact, we are trying tofind w column in the matrix H such that their sum isequal to the target syndrome s. In other terms, we arelooking for w indices, j1 to jw such that thecorresponding column has a sum equal to s. The syndromedecoding problem may have one or several solutions. We will denote CSD(H,s,w)the set of all solutions to the above problem. Where a CSD standsfor computational syndrome decoding.


Intervention
Thème
Disciplines :
Documentation
Support de présentation au format PDF

Dans la même collection

Voir tout

Avec les mêmes intervenants et intervenantes

Sur le même thème