Vidéo pédagogique
Langue :
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/nc44-x866
Citer cette ressource :
Irene Marquez-Corbella, Nicolas Sendrier, Matthieu Finiasz. Inria. (2015, 5 mai). 3.2. Combinatorial Solutions: Exhaustive Search and Birthday Decoding , in 3: Message Attacks (ISD). [Vidéo]. Canal-U. (Consultée le 13 juillet 2024)

3.2. Combinatorial Solutions: Exhaustive Search and Birthday Decoding

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

In this session, I willdetail two combinatorial solutions to the decoding problem. The first one isthe Exhaustive Search. To find our w columns,we will simply enumerate all the tuples j1 tojw and check whether the corresponding columnplus the syndrome is equal to zero modulo 2. In detailhere is how we will do. We have w loops enumerating the indices from j1 to jw, and in the innermost loop,we add the w columns plus the syndrome andeither we test the value of the syndrome or we store itdepending on what is our need. The cost of thisalgorithm is at most w(n,w) column additions plus acertain number of tests. In practice, the costfor the test is negligible and we will just ignorethat term, and we have this cost for the algorithm. But we can do better. Instead, we may keeptrack of partial sums. In the first loop, line 1,we add the syndrome to the first column. In thesecond loop, we add the first partial sum to the second column. We obtain a second partialsum and so on until, in the inner loop, we add theprevious partial sum to the last column. If we dothis, since each line i is executed (n,i)times, we have a total of column additionswhich is given here. And this cost isdominated by (n,w), when w is not too large. So, thetotal cost for the Exhaustive Search is (n,w) column operations. And for that cost, we obtainall the solutions to our problem. We can do better withthe Birthday Decoding. In this algorithm, wesplit the matrix into two equal parts and we willenumerate all solutions by enumerating those twolists using error pattern of weight w/2. If theintersection of those two lists is not empty, then we havea solution to our problem.Here is the algorithm. We first enumerate allerrors of weight w/2, compute the syndrome and store each of the computed values. Thiswill cost (n/2,w/2), that is the size of the first list. At this point, we may check the intersection of thetwo lists, L1 and L2. This last part of thealgorithm will cost (L1 * L2)/2 to the size of the syndrome. Coming back to theBirthday Decoding slide, the cost of the aboveenumeration will be given by theformula here with binomialcoefficient which can also be written as 2L + (L²/2^(n-k)) where L is the size common to the two lists. To measure the exactcomplexity of this algorithm, we have to take into accountthat an error pattern of weight w splits evenly between thetwo halves of the matrix with a probability P whichmay be smaller than one.


Dans la même collection

Avec les mêmes intervenants et intervenantes

Sur le même thème