# Canal-U

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="https://www.canal-u.tv/video/inria/embed.1/3_7_may_meurer_and_thomae_algorithm.32895?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 le contributeur
J’aime
Imprimer
partager

### 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.

## 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)