Vidéo pédagogique

3.1. From Generic Decoding to Syndrome Decoding

Réalisation : 5 mai 2015 Mise en ligne : 5 mai 2015
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3

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.

Langue :
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.
Citer cette ressource:
Inria. (2015, 5 mai). 3.1. From Generic Decoding to Syndrome Decoding. [Vidéo]. Canal-U. (Consultée le 23 mai 2022)

Dans la même collection

Avec les mêmes intervenants

Sur le même thème