- 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
- 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.
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.