# Canal-U

Mon compte
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_2_combinatorial_solutions_exhaustive_search_and_birthday_decoding.32871?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 ### 3.2. Combinatorial Solutions: Exhaustive Search and Birthday Decoding

In this session, I will detail two combinatorial solutions to the decoding problem. The first one is the Exhaustive Search. To find our w columns, we will simply enumerate all the tuples j1 to jw and check whether the corresponding column plus the syndrome is equal to zero modulo 2. In detail here 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 and either we test the value of the syndrome or we store it depending on what is our need. The cost of this algorithm is at most w(n,w) column additions plus a certain number of tests. In practice, the cost for the test is negligible and we will just ignore that term, and we have this cost for the algorithm. But we can do better. Instead, we may keep track of partial sums. In the first loop, line 1, we add the syndrome to the first column. In the second loop, we add the first partial sum to the second column. We obtain a second partial sum and so on until, in the inner loop, we add the previous partial sum to the last column. If we do this, since each line i is executed (n,i) times, we have a total of column additions which is given here. And this cost is dominated by (n,w), when w is not too large. So, the total cost for the Exhaustive Search is (n,w) column operations. And for that cost, we obtain all the solutions to our problem. We can do better with the Birthday Decoding. In this algorithm, we split the matrix into two equal parts and we will enumerate all solutions by enumerating those two lists using error pattern of weight w/2. If the intersection of those two lists is not empty, then we have a solution to our problem.
Here is the algorithm. We first enumerate all errors of weight w/2, compute the syndrome and store each of the computed values. This will cost (n/2,w/2), that is the size of the first list. At this point, we may check the intersection of the two lists, L1 and L2. This last part of the algorithm will cost (L1 * L2)/2 to the size of the syndrome. Coming back to the Birthday Decoding slide, the cost of the above enumeration will be given by the
formula here with binomial coefficient which can also be written as 2L + (L²/2^(n-k)) where L is the size common to the two lists. To measure the exact complexity of this algorithm, we have to take into account that an error pattern of weight w splits evenly between the two halves of the matrix with a probability P which may be smaller than one.

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