Canal-U

3.3. Information Set Decoding: the Power of Linear Algebra

In this third session, we will present the most important concept of the week: Information Set Decoding. The problem of decoding is not only a combinatorial problem. Because we are dealing with linear code, we may also use Linear Algebra. In particular, we are able to transform the Computational Syndrome Decoding problem by multiplying the matrix by a permutation P on the right and a nonsingular matrix U on the left. This will transform the problem of syndrome decoding into an equivalent one. It is very easy to prove that the following equivalence holds. In fact, this implies that the two computational syndrome decoding that are presented here are equivalent.
If I solve one of them, I solve the other. In particular, I can choose H'in the following form which is called systematic form or standard form. If the first n-k columns of matrix H*P are independent, then I am able to compute such a form. If this is the case, the last k column of the matrix forms an information set. If I am lucky, the permutation P will send the w error position in the left part of the position. If this happens, then the modified syndrome s'will have a weight equal to the weight of the error. And I can check that very easily. I can transform that into an algorithm. So, I want to solve the computational syndrome decoding presented here. I will repeatedly pick a permutation P, compute the following systematic form using Gaussian elimination, and check whether the transformed syndrome s*(U transpose) is a weight w. When this hapens, I can return the following vector which is valid solution to the original syndrome decoding problem. Here, each iteration of this algorithm will cost n*(n-k) column operations that is the cost of the Gaussian elimination. And I have to repeat that a certain number of times, until one of the solutions to my problem has all its non-zero coordinates "all left". In the next session, I will present Complexity Analysis of that algorithm in particular as long as tools to make the complexity analysis of the variance of information set decoding I will present throughout this course.