Canal-U

Mon compte
Inria

3.5. Lee and Brickell 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_5_lee_and_brickell_algorithm.32885?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
Auteur(s) :
MARQUEZ-CORBELLA Irene
SENDRIER Nicolas
FINIASZ Matthieu

Producteur Canal-U :
Inria
Contacter le contributeur
J’aime
Imprimer
partager facebook twitter Google +

3.5. Lee and Brickell Algorithm

In this fifth session, we will study a variant of information set decoding proposed by Lee and Brickell. So, the main idea consists in relaxing the Prange algorithm to amortize the cost of the Gaussian elimination. So, instead of error patterns with all positions on the left, we will allow error patterns of the form given in the slide. So, in the left part we have w-p coordinate to 1 and on the right hand side we allow a small number p of positions to have a value 1. So, at each iteration, we will simply enumerate all the possible k to p values for the right hand side. Note that the Prange algorithm corresponds to weight p = 0. The computational syndrome decoding and the solution we are going to propose to it has an additional parameter p which is an integer between 0 and w. As before, we repeat the following: we pick a permutation matrix P, we compute the systematic form of that matrix using a Gaussian elimination, and next, we enumerate this set and we check every element in that set until we find one element of weight w-p. If this happens, then we have a solution to our problem, we return it. The cost of the iteration in that case will increase because in addition to the Gaussian elimination we now have an enumeration cost which is equal to (k,p). Now, the complexity analysis. The probability to obtain an error pattern of that form in a specific iteration is equal to P∞ as given in the slide. It follows that the expected number of iteration N∞ is the inverse of the probability. And as I said before, the iteration cost is the sum of those two terms. The total cost of the Lee and Brickell algorithm is the following: the product of N∞ * K, and in fact, it appears that we never gain more than a polynomial factor compare with Prange algorithm, and I give here the idea of how to prove this fact. And the last thing to do in this formula is to minimize it over all possible values of p and, except for very strange parameters that's either w or W, the minimum value of that formula is obtained for p=2.

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

FMSH
 
Facebook Twitter Google+
Mon Compte