Vidéo pédagogique
Notice
Sous-titrage
Anglais
Langue :
Anglais
Crédits
Irene Marquez-Corbella (Intervention), Nicolas Sendrier (Intervention), Matthieu Finiasz (Intervention)
Conditions d'utilisation
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.
DOI : 10.60527/sg29-s769
Citer cette ressource :
Irene Marquez-Corbella, Nicolas Sendrier, Matthieu Finiasz. Inria. (2015, 5 mai). 3.7. May, Meurer, and Thomae Algorithm , in 3: Message Attacks (ISD). [Vidéo]. Canal-U. https://doi.org/10.60527/sg29-s769. (Consultée le 15 juillet 2025)
logo Inria
Inria - Institut national de recherche en sciences et technologies du numérique
S'abonner
Contacter

3.7. May, Meurer, and Thomae Algorithm

Réalisation : 5 mai 2015 - Mise en ligne : 20 février 2017
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

So, with the session7 we are entering the most advanced part of that course. The idea of what I called the  Improved BirthdayDecoding is to use the so-called "representation technique"introduced by Howgrave-Graham and Joux in 2010 in which we will relax the waywe construct the two lists in Birthday Decoding. So, if youremember, we could relax the size of thematrices H1 and H2 slightly to gain a polynomialfactor on Birthday Decoding. But, we may push the ideafurther and increase the size of H1 and H2 until we reachthe full size for both those matrices. If we dothat, there is some redundancy in the search we will make. And in fact eachsolution of our problem will be represented (w,w/2) times as a sum of twoerror patterns of weight w/2. This means that thetwo 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 onetime in the intersection. So, we define thefollowing: for any binary vector, we define Φr(x), the last r bits of thevector x and we define those two lists with anadditional parameter r where we, in fact, keep in the list allthe syndromes where the r final bits are set to 0. And we have the followingclaim that I will not prove which is that if I chooser such that 2^r is equal to the number of representationof e as a sum of two errors of half weight, then anyelement, any solution of our problem isrepresented in the intersection with probability at least one half. The Improved Birthdayalgorithm works as follows: first, we cut the matrix H in two parts, H'and H'', and thenwe will build the two lists L1 and L2. L1 is constructed by making a firstrecursive call to the computational syndromedecoding 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 ofthat first computation, then we compute in a similarway the second list L2, again by solving acomputational syndrome decoding problem on thelower part and keeping the syndromecorresponding to the upper part. And finally, we merge those two lists and we keep thesyndromes which match on the upper part of the matrix.


Intervention
Thème
Disciplines :
Documentation
Support de présentation au format PDF

Dans la même collection

Voir tout

Avec les mêmes intervenants et intervenantes

Sur le même thème