Informations pratiques

Description de la ressource

Résumé

All the results that we have seen this week doesn't mean that code based cryptography is broken. So in this session we will see that Goppa code still resists to all these attacks. So recall that it is assumed that Goppa codes are pseudorandom, that is there exist no efficient distinguisher for Goppa code. An efficient distinguisher was built for the case of high rate codes, where the rate is very close to 1, but no generalization of this distinguisher is known. The best known attacks are based on the Support Splitting Algorithm and have exponential runtime. In the third session of this week, we have seen that Generalized Reed-Solomon codes behave differently than random codes, with respect to the square product that is the dimension of the square of a Generalized Reed-Solomon code is very small compared to what it's expected for a random code of the same length and dimension. Since an alternant code is a subfield subcode of a Generalized Reed-Solomon code, we might suspect that the star product of alternant codes also behave differently from random codes. As we will see, this is true but just for a very few cases. The following proposition shows that the star product of two alternant codes is another alternant code and the proof is very easy. We just need to recall that alternant codes are subfield subcodes of Generalized Reed Solomon code. So how works this proof? Let c1 be a codeword of an alternant code and c2 be another codeword of a different alternant code with the same support. Then, there exist two polynomials of degree smaller than n-s and another polynomial of degree smaller than n-r such that the evaluation of these polynomials at the corresponding elements give our codewords.

"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