Mon compte

3.7. May, Meurer, and Thomae 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=";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) :
FINIASZ Matthieu

Producteur Canal-U :
Contacter le contributeur
partager facebook twitter

3.7. May, Meurer, and Thomae Algorithm

So, with the session 7 we are entering the most advanced part of that course. The idea of what I called the  Improved Birthday Decoding is to use the so-called "representation technique" introduced by Howgrave-Graham and Joux in 2010 in which we will relax the way we construct the two lists in Birthday Decoding. So, if you remember, we could relax the size of the matrices H1 and H2 slightly to gain a polynomial factor on Birthday Decoding. But, we may push the idea further and increase the size of H1 and H2 until we reach the full size for both those matrices. If we do that, there is some redundancy in the search we will make. And in fact each solution of our problem will be represented (w,w/2) times as a sum of two error patterns of weight w/2. This means that the two sets L1 and L2 are bigger than necessary. We can try to decimate those two sets as long as we keep every solution at least one time in the intersection. So, we define the following: for any binary vector, we define Φr(x), the last r bits of the vector x and we define those two lists with an additional parameter r where we, in fact, keep in the list all the syndromes where the r final bits are set to 0. And we have the following claim that I will not prove which is that if I choose r such that 2^r is equal to the number of representation of e as a sum of two errors of half weight, then any element, any solution of our problem is represented in the intersection with probability at least one half. The Improved Birthday algorithm works as follows: first, we cut the matrix H in two parts, H'and H'', and then we will build the two lists L1 and L2. L1 is constructed by making a first recursive call to the computational syndrome decoding with the matrix H'and the weight w/2. This will cost the square root of (n, w/2) plus the number of solutions. We store the result of that first computation, then we compute in a similar way the second list L2, again by solving a computational syndrome decoding problem on the lower part and keeping the syndrome corresponding to the upper part. And finally, we merge those two lists and we keep the syndromes which match on the upper part of the matrix.

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


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

Facebook Twitter
Mon Compte