Paper 2026/1232

A Heuristic Subexponential Attack on the McEliece Cryptosystem

Abstract

We provide a new way of performing an algebraic attack on the McEliece cryptosystem based on binary Goppa codes. It also applies in general to the case where the field over which the Goppa code is defined is of even characteristic. It is based on a new algebraic modeling for finding as in [CMT23,M25,BLT26] matrices of rank $2$ in the code of quadratic relations related to the Goppa code that is attacked. Such matrices are then used to recover the secret algebraic structure of the code, from which an equivalent secret key can be efficiently derived, leading to a full key-recovery attack. A byproduct of our approach is a new distinguisher for Goppa codes in even characteristic which is as the syzygy distinguisher of [R25] subexponential in the security parameter of the scheme. We demonstrate the effectiveness of our attack on McEliece TII challenges, some of which having been studied in [BLT26], and aimed at having $83$,$89$,$119$,$166$, $210$ and even $248$ bit security respectively and CFS keys with parameters $r=9$ and $m=16$, corresponding to a security of $74.9$ bits according to [LS12]. This CFS key was not attacked in practice in [BLT26] and took us 14 hours of computation and 24GB of RAM. We make the conjecture that this attack has a complexity which is of the same nature as the distinguisher, namely subexponential in the security parameter.

Note: In order to avoid any misunderstanding, the two following sentences were changed "Such matrices are then used to recover the secret algebraic structure of the code. This breaks the scheme. «  They were replaced by "Such matrices are then used to recover the secret algebraic structure of the code, from which an equivalent secret key can be efficiently derived, leading to a full key-recovery attack. » Note that the last paragraph in the introduction called « The impact on the McEliece scheme » leaves no doubt that this attack does not break Classic McEliece parameters.