Canal-U

Mon compte

3.9. Generalized Birthday Algorithm for Decoding

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_9_generalized_birthday_algorithm_for_decoding.32901?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 la chaine
J’aime
Imprimer
partager

3.9. Generalized Birthday Algorithm for Decoding

The session nine is devoted to the application of the Generalized Birthday Algorithm to decoding. The Generalized Birthday Algorithm was presented by David Wagner in 2002, in a more general context. In fact, at order a, the Generalized Birthday Algorithm solves the following problem: we are given 2^a lists of vectors of size L and we want to find xi, one in every list Li, such that the sum of all the xi is 0. If the lists Li are large enough, then the algorithm runs in time 2^(l/(a+1)). Note that the case a=1 corresponds to the usual birthday paradox. This Generalized Birthday Algorithm can be applied to solve the problem of decoding. In practice, it will apply mostly to instances of Computational Syndrome Decoding which have many solutions and, more than that, it aims at finding one solution only among those many solutions. I would revisit the Birthday Decoding again but this time I will change slightly the context. So now I would assume that there are many solutions. I will be more specific about how many solutions are needed when I am done with this slide. And among those many solutions, I only want to find one. So, I will build the lists exactly in the same manner as before. Here, I write s = s1 + s2 where I cut the target syndrome s arbitrarily. There is no specific reason to do that except to have a nice symmetry and it will be useful for higher order Generalized Birthday Algorithm. So, I have those two lists and I am interested by any element in the intersection. But since I only want one solution to my problem, I am only interested to have one element in the intersection. So, I only want the intersection whose size is L²/2^(n-k) where L is the size of both lists L1 and L2. I am interested that this size is larger than one. This will be the case if I choose L = 2^((n-k)/2).
And in that case my lists are large enough to have a non-empty intersection, and the workfactor to obtain a non-empty intersection is L that is 2^((n-k)/2). Once this is set, it gives me the limit for the size list. I need a list of size 2^((n-k)/2) and I also know from the way the lists are constructed that L cannot exceed (n/2,w/2). So, I need the condition here in red in order to be able to apply this version of Birthday Decoding. Now, I can define a Generalized Birthday Algorithm of order 2 for decoding. So, I do exactly the same thing as before except that I split everything in four parts instead of two.

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