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.