Paper 2023/950
A new approach based on quadratic forms to attack the McEliece cryptosystem
Abstract
We introduce a novel algebraic approach for attacking the McEliece cryptosystem which is currently at the $4$th round of the NIST competition. The contributions of the article are twofold. (1) We present a new distinguisher on alternant and Goppa codes working in a much broader range of parameters than \cite{FGOPT11}. (2) With this approach we also provide a polynomialtime key recovery attack on alternant codes which are distinguishable with the distinguisher \cite{FGOPT11}. These results are obtained by introducing a subspace of matrices representing quadratic forms. Those are associated with quadratic relations for the componentwise product in the dual of the Goppa (or alternant) code of the cryptosystem. It turns out that this subspace of matrices contains matrices of unusually small rank in the case of alternant or Goppa codes ($2$ or $3$ depending on the field characteristic) revealing the secret polynomial structure of the code. MinRank solvers can then be used to recover the secret key of the scheme. We devise a dedicated algebraic modeling in characteristic $2$ where the Gröbner basis techniques to solve it can be analyzed. This computation behaves differently when applied to the matrix space associated with a random code rather than with a Goppa or an alternant code. This gives a distinguisher of the latter code families, which contrarily to the one proposed in \cite{FGOPT11} working only in a tiny parameter regime is now able to work for code rates above $\frac{2}{3}$. It applies to most of the instantiations of the McEliece cryptosystem in the literature. It coincides with the one of \cite{FGOPT11} when the latter can be applied (and is therefore of polynomial complexity in this case). However, its complexity increases significantly when \cite{FGOPT11} does not apply anymore, but stays subexponential as long as the codimension of the code is sublinear in the length (with an asymptotic exponent which is below those of all known key recovery or message attacks). For the concrete parameters of the McEliece NIST submission \cite{ABCCGLMMMNPPPSSSTW20}, its complexity is way too complex to threaten the cryptosystem, but is smaller than known key recovery attacks for most of the parameters of the submission. This subspace of quadratic forms can also be used in a different manner to give a polynomial time attack of the McEliece cryptosystem based on generic alternant codes or Goppa codes provided that these codes are distinguishable by the method of \cite{FGOPT11}, and in the Goppa case we need the additional assumption that its degree is less than $q1$, where $q$ is the alphabet size of the code.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Preprint.
 Keywords
 Codebased cryptographyalgebraic attackMcEliece cryptosystem
 Contact author(s)

alain couvreur @ inria fr
rocco mora @ inria fr
jeanpierre tillich @ inria fr  History
 20230824: last of 2 revisions
 20230617: received
 See all versions
 Short URL
 https://ia.cr/2023/950
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/950, author = {Alain Couvreur and Rocco Mora and JeanPierre Tillich}, title = {A new approach based on quadratic forms to attack the McEliece cryptosystem}, howpublished = {Cryptology ePrint Archive, Paper 2023/950}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/950}}, url = {https://eprint.iacr.org/2023/950} }