A distinguisher for high-rate McEliece cryptosystems

Jean Charles Faugere, Valerie Gauthier-Umana, Ayoub Otmani, Ludovic Perret, Jean Pierre Tillich

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

41 Citas (Scopus)

Resumen

The Goppa Code Distinguishing (GD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. The hardness of this problem is an assumption to prove the security of code-based cryptographic primitives such as McEliece's cryptosystem. Up to now, it is widely believed that the GD problem is a hard decision problem. We present the first method allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GD problem in polynomial time provided that the codes have sufficiently large rates. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the rank of a linear system which is obtained by linearizing a particular polynomial system describing a key-recovery attack. It appears that this dimension depends on the type of code considered. Explicit formulas derived from extensive experimentations for the rank are provided for 'generic' random, alternant, and Goppa codes over any field. Finally, we give theoretical explanations of these formulas in the case of random codes, alternant codes over any field of characteristic two and binary Goppa codes.

Idioma originalInglés estadounidense
Número de artículo6553164
Páginas (desde-hasta)6830-6844
Número de páginas15
PublicaciónIEEE Transactions on Information Theory
Volumen59
N.º10
DOI
EstadoPublicada - 2013
Publicado de forma externa

All Science Journal Classification (ASJC) codes

  • Sistemas de información
  • Informática aplicada
  • Biblioteconomía y ciencias de la información

Huella

Profundice en los temas de investigación de 'A distinguisher for high-rate McEliece cryptosystems'. En conjunto forman una huella única.

Citar esto