Informations pratiques

Description de la ressource

Résumé

In this session we will discuss the proposal of using generalized Reed-Solomon codes for the McEliece cryptosystem. As we have already said, generalized Reed-Solomon codes were proposed in 1986 by Niederreiter. Recall that these codes are MDS, that is, they attain the maximum error correcting capacity which is interpreted as shorter keys for the same level of security. Moreover, these codes have efficient decoding algorithms so they are suitable candidates for code-based cryptography. But this proposal is subject to a polynomial attack by Sidelnikov-Shestakov. Take notice that if we know a generalized Reed-Solomon code associated to the pair (a,b) of dimension k and dimension k - 1, that is we know two codes, then by solving the following system, we can obtain the generalized Reed-Solomon code of dimension k - 2. And the proof is very easy. Just take notice that the star product of the known codes provide the square code of the generalized Reed-Solomon code of dimension k - 1. In other words, a polynomial of degree at most k-1 times a polynomial of degree at most k, yields to a polynomial of degree at most 2k - 2. And this property can be used iteratively to build the following decreasing sequence. Note that the generalized Reed-Solomon code of dimension 1 is the set of multiples of the vector b. Thus we can retrieve the vector b and then by solving a linear system, we can obtain also a. However, from the McEliece cryptosystem, just a generator matrix of the generalized Reed-Solomon code of dimension k is known. And we will explain in this slide how to compute a generator matrix of the same generalized Reed-Solomon code by dropping by one the dimension. Recall that the shorten of a generalized Reed-Solomon code is again a generalized Reed-Solomon code. Moreover, the code locator of the shortened code is again the same code locator but restricted to some coordinates. In particular shortening at the first position we get a new generalized Reed-Solomon code, associated to the same code locator without the first coordinate, and it is easy to get a generator matrix of such shortened code: we just apply Gaussian Elimination to our matrix.

"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