A distinguisher for high rate McEliece cryptosystems

Jean Charles Faugère, Valérie Gauthier-Umaña, Ayoub Otmani, Ludovic Perret, Jean Pierre Tillich

Resultado de la investigación: Capítulo en Libro/Reporte/ConferenciaContribución a la conferencia

36 Citas (Scopus)

Resumen

The Goppa Code Distinguishing (GCD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. Up to now, it is widely believed that the GCD problem is a hard decisional problem. We present the first technique allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GCD problem in polynomial-time provided that the codes have rates sufficiently large. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the dimension of the solution space of a linearized system deduced from a particular polynomial system describing a key-recovery. It turns out that experimentally this dimension depends on the type of code. Explicit formulas derived from extensive experimentations for the value of the dimension are provided for generic random, alternant, and Goppa code over any alphabet. Finally, we give explanations of these formulas in the case of random codes, alternant codes over any field and binary Goppa codes.

Idioma originalInglés estadounidense
Título de la publicación alojada2011 IEEE Information Theory Workshop, ITW 2011
Páginas282-286
Número de páginas5
DOI
EstadoPublicada - 2011
Publicado de forma externa
Evento2011 IEEE Information Theory Workshop, ITW 2011 - Paraty, Brasil
Duración: oct 16 2011oct 20 2011

Serie de la publicación

Nombre2011 IEEE Information Theory Workshop, ITW 2011

Conferencia

Conferencia2011 IEEE Information Theory Workshop, ITW 2011
PaísBrasil
CiudadParaty
Período10/16/1110/20/11

All Science Journal Classification (ASJC) codes

  • Sistemas de 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