# Canal-U

Mon compte

## 2.8. Reducing the Key Size - MDPC codes

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_8_reducing_the_key_size_mdpc_codes.32849?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.8. Reducing the Key Size - MDPC codes

This is the last session where we will talk about reducing the key size. Here we will introduce the MDPC codes.
In 2012, the MDPC codes were proposed for the McEliece schemes. An MDPC code is a code that admits a binary
moderate density-parity check matrix. Typically, the Hamming weight of each row is of the order the square of the length. In this sequence, I will describe this scheme of quasi-cyclic MDPC McEliece for a binary code of rate one half. So, we use circulant matrices of blocks of size p to define the codes. The length will be 2p and the dimension p. Other parameters are the weight of the parity check equations and the number of correctable errors. So, let us explain the McEliece schemes using quasi-cyclic MDPC code. First of all, we pick randomly two vectors of weight p,
such that the concatenated vector has a weight smaller than w. We will repeat until the corresponding polynomial h0 is invertible. In particular, we ask the weight to be odd. Then, the secret key and the public key will be the corresponding matrices. To encrypt a message, we apply the following function, that is, we encode the message and we add random errors of weight smaller than t. But we will describe them in terms of polynomial. To decrypt, we use an MDPC-like iterative decoding algorithm as the Gallager's Bit-Flipping algorithm, already explained in the previous session. The quasi-cyclic MDPC proposal is secure under two assumptions. First of all, the problem of distinguishing a public key from a random quasi-cyclic matrix or equivalently the problem of finding codewords of weight w in the dual of an MDCP code; and the hardness of decoding random quasi-cyclic codes. The security reduction can be translated in terms of polynomials as follows.

•
Label UNT : UNIT
•
Date de réalisation : 5 Mai 2015
Durée du programme : 5 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)