Ressource pédagogique : 3.5. Lee and Brickell Algorithm

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

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.

"Domaine(s)" et indice(s) Dewey

• Analyse numérique (518)
• Théorie de l'information (003.54)
• données dans les systèmes informatiques (005.7)
• cryptographie (652.8)
• Mathématiques (510)

Thème(s)