Canal-U

Mon compte
Inria

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
Auteur(s) :
MARQUEZ-CORBELLA Irene
SENDRIER Nicolas
FINIASZ Matthieu

Producteur Canal-U :
Inria
Contacter la chaine
J’aime
Imprimer
partager facebook twitter

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)
 

Dans la même collection

FMSH
 
Facebook Twitter
Mon Compte