# Canal-U

Mon compte

## 2.3. McEliece Assumptions

Copier le code pour partager la vidéo :
<div style="position:relative;padding-bottom:56.25%;padding-top:10px;height:0;overflow:hidden;"><iframe src="https://www.canal-u.tv/video/inria/embed.1/2_3_mceliece_assumptions.32829?width=100%&amp;height=100%" style="position:absolute;top:0;left:0;width:100%;height: 100%;" width="550" height="306" frameborder="0" allowfullscreen scrolling="no"></iframe></div> Si vous souhaitez partager une séquence, indiquez le début de celle-ci , et copiez le code : h m s
Contacter la chaine
J’aime
Imprimer
partager

### 2.3. McEliece Assumptions

In this session, we will talk about McEliece assumptions. The security of the McEliece scheme is based on two assumptions as we have already seen: the hardness of decoding a random linear code and the problem of distinguishing a code with a prescribed structure from a random one. In this sequence, we will study in detail these two assumptions. The first assumption claims that decoding a random linear code is difficult.  First, notice that the general decoding problem is basically a re-writing of the Syndrome Decoding problem. And both are equivalent to the problem of finding codewords of minimal weight. The Syndrome Decoding in the binary case is state as follows. Given a binary matrix, a syndrome S and a non-negative integer W, the weight. The decision problem faces the following question. There exists an error pattern of weight at most w with syndrome S? while the computational problem is to find such a vector. The decoding problem was proved to be NP-complete in 1978 by Berlekamp, McEliece and van Tilborg in this article. For the q-ary case, see the article of Barg. Take notice that this proof took place at the same time that the McEliece cryptosystem was introduced. Thus, the worst case of the computational problem is known to be difficult in general. Of course, depending on the input, some instances can be solved in polynomial time as we have already seen in the first week. Actually, the instance of Syndrome Decoding involved in breaking code-based systems are in particularly a subclass of Syndrome Decoding where the weight w is bounded by half the minimum distance. This problem is not NP, however it is conjectured to be NP-Hard. But even more in the McEliece cryptosystem, the chosen code is not completely random. Even if the matrix is not distinguishable from a random binary matrix of the same size, the decoding problem uses parameters of those of a Goppa code. This means that the code has length 2^m and the dimension is n mt, where t is the correction capacity.

•
Label UNT : UNIT
•
Date de réalisation : 5 Mai 2015
Durée du programme : 4 min
Classification Dewey : Analyse numérique, Théorie de l'information, données dans les systèmes informatiques, cryptographie, Mathématiques
•
Catégorie : Vidéocours
Niveau : niveau Master (LMD), niveau Doctorat (LMD), Recherche
Disciplines : Mathématiques, Informatique, Informatique, Mathématiques et informatique
Collections : 2: McEliece Cryptosystem
ficheLom : Voir la fiche LOM
•
Auteur(s) : MARQUEZ-CORBELLA Irene, SENDRIER Nicolas, FINIASZ Matthieu
•
Langue : Anglais
Mots-clés : algèbre linéaire, chiffrement à clé publique, cryptage des données, cryptographie, McEliece, LDPC, MDPC
Conditions d’utilisation / Copyright : 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.

## commentaires

Ajouter un commentaire Lire les commentaires
*Les champs suivis d’un astérisque sont obligatoires.
Aucun commentaire sur cette vidéo pour le moment (les commentaires font l’objet d’une modération)