Vidéo pédagogique

3.5. Lee and Brickell Algorithm

Réalisation : 5 mai 2015 Mise en ligne : 5 mai 2015
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3

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.

Langue :
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.
Citer cette ressource:
Inria. (2015, 5 mai). 3.5. Lee and Brickell Algorithm. [Vidéo]. Canal-U. (Consultée le 22 mai 2022)

Dans la même collection

Avec les mêmes intervenants

Sur le même thème