- 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, code correcteur, algorithmes, GRS code
- 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.
4.4. Attack against subcodes of GRS codes
In this session, we will
talk about using subcodes of a Generalized Reed–Solomon code
for the McEliece Cryptosystem. Recall that to avoid the
attack of Sidelnikov and Shestakov, Berger and
Loidreau proposed to replace Generalized Reed–Solomon
codes by some random subcodes of small codimension.
However, this attack has been broken by Wieschebrink in 2006
using square code considerations. The idea of the
attack is very simple.
The public key is a subcode of large dimension, otherwise a generic attack could be applied. And we also know the error-correcting capacity of the Generalized Reed–Solomon code. With high probability, the square of this subcode is again a Generalized Reed–Solomon code of maximal dimension. Thus, we just need to apply Sidelnikov and Shestakov to retrieve the code locator and the column multiplier. And thus, we have an efficient decoding algorithm for the Generalized Reed–Solomon code, which is also a decoding algorithm for the chosen subcode. We correct up to t errors. But what happens if the square code is the whole space? Then, a similar attack could be applied but to a shortened code. Recall the definition of a shortened code. First of all, some notations. The process of deleting columns from a parity-check matrix of a linear code is known as shortening. In other words, the shortened code, at the J-locations, is the set of codewords that have a zero in the J-locations restricted to the coordinates indexed by the relative complement of J. In a simple way, suppose that we have a generator matrix and we have the identity at the beginning of its first J-columns. Then, a basis of the shortened code can be easily
obtained by extracting the components that we indicate in the figure, that is by extracting these columns of the generator matrix. Generalized Reed–Solomon codes behave specially with the shortening operation. Since we have that the shortened of a Generalized Reed–Solomon code is again a Generalized Reed–Solomon code. To simplify the proof, we will just shortened the first position, but the generalization to other positions is straightforward. So, let G be a matrix of a Generalized Reed–Solomon code of dimension k associated to the pair (a,b). We labelled its rows by g1, g2, … , gk. We apply Gauss elimination to get a matrix of the following form. Then, this sub-matrix is a generator matrix for the shortened code at the first position.