Informations pratiques

Description de la ressource

Résumé

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.

"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)

Domaine(s)

• Cette ressource fait partie de
  • 4: Key Attacks