HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Algebraic Attack against Variants of McEliece with Goppa Polynomial of a Special Form

Jean-Charles Faugère 1 Ludovic Perret 1 Frédéric de Portzamparc 1, 2
1 PolSys - Polynomial Systems
Inria Paris-Rocquencourt, LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : In this paper, we present a new algebraic attack against some special cases of Wild McEliece Incognito, a generalization of the original McEliece cryptosystem. This attack does not threaten the original McEliece cryptosystem. We prove that 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 eld Fq. To support our theoretical results, we have been able to practically break several parameters de ned over a non-prime base field q in {9; 16; 25; 27; 32}, t < 7, extension degrees m in {2,3}, security level up to 2^129 against information set decoding in few minutes or hours.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download

Contributor : Jean-Charles Faugère Connect in order to contact the contributor
Submitted on : Tuesday, September 16, 2014 - 9:01:57 PM
Last modification on : Friday, January 21, 2022 - 3:21:15 AM
Long-term archiving on: : Wednesday, December 17, 2014 - 11:55:24 AM


Files produced by the author(s)



Jean-Charles Faugère, Ludovic Perret, Frédéric de Portzamparc. Algebraic Attack against Variants of McEliece with Goppa Polynomial of a Special Form. Advances in Cryptology Asiacrypt 2014, Dec 2014, Kaohsiung, Taiwan. pp.21-41, ⟨10.1007/978-3-662-45611-8_2⟩. ⟨hal-01064687⟩



Record views


Files downloads