A Heuristic Subexponential Attack on the McEliece Cryptosystem

par Pierre Briaud (CNRS)

mardi 20 oct. 2026, 14:00 → 15:00 Europe/Paris

XR203 (XLIM)

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.