10/24/2014

Speaker(s) : Fréderic de Portzamparc (Gemalto & PolSys team, CNRS/INRIA/UPMC)

In this talk, we present a new algebraic attack against Wild McEliece & Wild McEliece Incognito, which are generalizations of the original McEliece cryptosystem introduced by Bernstein, Lange and Peters (BLP).

We prove that, thanks to the multiple factors in the Goppa polynomial, recovering the secret key for such schemes is equivalent to solving a system of polynomial equations whose solutions have the structure of a usual vector space. Consequently, to recover a basis of this vector space, we can greatly reduce the number of variables in the corresponding algebraic system. From these solutions, we can then deduce the basis of a GRS code. Finally, the last step of the cryptanalysis of those schemes corresponds to attacking a McEliece scheme instantiated with particular GRS codes (with a polynomial relation between the support and the multipliers) which can be done in polynomial-time thanks to a variant of the Sidelnikov-Shestakov attack. For Wild McEliece & Incognito, we also show that solving the corresponding algebraic system is notably easier in the case of a non-prime base field Fq.

To support our theoretical results, we have been able to practically break several parameters defined over a non-prime base field $q in {9,16,25,27, 32}$, $tleq 6$, extension degrees $m in {2,3}$, and security level up to $2^{129}$ against information set decoding in few minutes or hours. Amongst others, we broke the hardest challenges proposed for q=27 by BLP (on the website http://pqcrypto.org/wild-challenges.html), which were out of the reach of the attack of Couvreur, Otmani and Tillich.

Joint work with Jean-Charles Faugère and Ludovic Perret.

Elias.Tsigaridas (at) nulllip6.fr