A Polynomial time attack on Wild McEliece over quadratic extensions
Speaker(s) : Alain Couvreur (GRACE team, Inria Saclay)
McEliece encryption scheme is based on error correcting codes and its security reposes on the difficulty of decoding a random code. Among several families of codes proposed for the scheme, classical Goppa codes resist to every (non-exhaustive) key recovery attack since almost 30 years. In this talk I will present a new kind of attack called "filtration attack".
This attack allows to recover the structure of a wild Goppa code over a quadratic extension if it is used as the public key. By this manner, we break in less than one hour some keys proposed by Bernstein, Lange and Peters whose security was estimated as larger that 128 bits (Wild McEliece, SAC 2010).
Joint work with Ayoub Otmani and Jean-Pierre Tillich.
Elias.Tsigaridas (at) nulllip6.fr