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 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 \cite{R25}subexponential in the security level of the scheme. We demonstrate the effectiveness of our attack on McEliece TII challenges, some of which having been studied in \cite{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 \cite{LS12}. This CFS key was not attacked in practice in \cite{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 level. It should be noted that this attack is at best of complexity of order $2^{454}$ for NIST level 1 Classic McEliece parameters.

Note: Long version with appendices.