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/jb6f-8529
Citer cette ressource :
Irene Marquez-Corbella, Nicolas Sendrier, Matthieu Finiasz. Inria. (2015, 5 mai). 3.5. Lee and Brickell Algorithm , in 3: Message Attacks (ISD). [Vidéo]. Canal-U. https://doi.org/10.60527/jb6f-8529. (Consultée le 10 juillet 2025)
logo Inria
Inria - Institut national de recherche en sciences et technologies du numérique
S'abonner
Contacter

3.5. Lee and Brickell 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

In this fifth session,we will study a variant of information set decodingproposed by Lee and Brickell. So, the main ideaconsists in relaxing the Prange algorithm to amortize thecost of the Gaussian elimination. So, instead of error patterns with allpositions on the left, we will allow error patterns ofthe form given in the slide. So, in the left part wehave w-p coordinate to 1 and on the right hand sidewe allow a small number p of positions to have a value 1. So, at each iteration, wewill simply enumerate all the possible k to p valuesfor the right hand side. Note that the Prangealgorithm corresponds to weight p = 0. The computational syndromedecoding and the solution we are going to propose to ithas an additional parameter p which is an integer between 0 and w. As before, we repeat thefollowing: we pick a permutation matrix P, we computethe systematic form of that matrix using aGaussian elimination, and next, we enumerate thisset and we check every element in that setuntil we find one element of weight w-p. If thishappens, then we have a solution to our problem, we return it. The cost of the iterationin that case will increase because in addition to theGaussian elimination we now have an enumeration costwhich is equal to (k,p). Now, the complexity analysis. The probability to obtainan error pattern of that form in a specific iteration is equal to P∞ as given in the slide. It follows that theexpected number of iteration N∞ is the inverse of the probability. And as I said before, theiteration cost is the sum of those two terms. Thetotal cost of the Lee and Brickell algorithm is thefollowing: the product of N∞ * K, and in fact, it appears that we never gain more than apolynomial factor compare with Prange algorithm, and I give herethe idea of how to prove this fact. And the last thing to do inthis formula is to minimize it over all possiblevalues of p and, except for very strangeparameters that's either w or W, the minimum value of thatformula is obtained for p=2.

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