Canal-U

Mon compte
Inria

3.8. Becker, Joux, May, and Meurer Algorithm


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/3_8_becker_joux_may_and_meurer_algorithm.32899?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 le contributeur
J’aime
Imprimer
partager facebook twitter

3.8. Becker, Joux, May, and Meurer Algorithm

Now in session 8, we will present yet another evolution of information set decoding. Before presenting this improvement, we will first improve the Birthday Decoding algorithm what I call a Further Improvement of Birthday Decoding. I will consider the two following lists. The difference between those two lists and those we had before is the + ɛ that you can find in the weight of the errors e1 and e2. Those lists depend on another parameter ɛ. What is the meaning of that parameter? Well, the idea is the following: if you add two words of weight w/2 and length n, you expect that you obtain a sum of weight w-(w²/2n). That is, in fact, that you expect that those two words have w²/4n non-zero positions in common. Now, if we shift things a little bit and if we choose ɛ such that ɛ = (w/2+ɛ)²/n, then two words of weight (w/2) + ɛ and length n are expected to have ɛ non-zero positions in common and a sum of weight w which is the target weight of our syndrome decoding problem. Note that in addition to the above property with a non-zero value of ɛ, (w,w/2)*(n-w,ɛ) different ways to write a word of weight w, a word e, as a sum of two error patterns e1 and e2 of weight (w/2)+ɛ, that is, the number of representation will increase. All of this together allows us to give that claim. If we choose 2^r and ɛ as described here, then any solution e to our problem is represented in the intersection of the two sets above with the probability 1/2. And if we do that and implement the Birthday Decoding with those two lists, the workfactor will simplify, if I may say, into the following formula which is true up to a polynomial factor. And, I'm not going to explain why it is a polynomial factor now and rather than a constant factor. Improving Birthday Decoding has an impact on the May, Meurer and Thomae algorithm we have just seen. Instead of the formula we have here, in green, that is true up to a constant factor, by using the Further Improved Birthday Decoding, we could obtain this formula which is better for any value of the parameter, which is true up to a polynomial factor. This idea and this improvement is the embryo of the next improvement of information set decoding. This improvement is due to Becker, Joux, May and Meurer. And the idea is to let ɛ, that is the increase in the weight of the half error patterns. We let ɛ grow beyond the optimal value that is much beyond w²/4n. If we do that and the workfactor of the Birthday Decoding becomes this formula with L equal to the list size and 2^r is the number of representative which is given by the formula here. We may also write the formula in the following form introducing the value μ which is the probability that is described on the slide.


  •  
    Label UNT : UNIT
  •  
    Date de réalisation : 5 Mai 2015
    Durée du programme : 9 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 : 3: Message Attacks (ISD)
    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, algorithmes
    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