Welcome to the resource topic for 2023/950
Title:
A new approach based on quadratic forms to attack the McEliece cryptosystem
Authors: Alain Couvreur, Rocco Mora, Jean-Pierre Tillich
Abstract:We bring in here a novel algebraic approach for attacking the McEliece cryptosystem which is right now at the 4-th round of the NIST competition. It
consists in introducing a subspace of matrices representing quadratic forms. Those are associated with quadratic relationships for the component-wise product in the dual of the Goppa (or alternant) code of the cryptosystem.
Depending on the characteristic of the field over which the code is defined, this space of matrices consists only of symmetric matrices (odd characteristic) or skew-symmetric matrices (characteristic 2).
It turns out that this matrix space contains unusually low-rank matrices (rank 3 matrices in odd characteristic, rank 2 matrices for characteristic 2) which reveal the secret polynomial structure of the code.
Finding such matrices can then be used to recover the secret key of the scheme. We devise a dedicated approach in characteristic 2 consisting in using a Gröbner basis modeling that a skew-symmetric matrix is of rank 2. This allows to analyze the complexity of solving the corresponding algebraic system with Gröbner bases techniques. This computation behaves differently when
applied to the skew-symmetric matrix space associated with a random code rather than with a Goppa or an alternant code. This gives a distinguisher of the latter code family. We give a bound on its complexity which turns out to interpolate nicely between polynomial and exponential depending on the code parameters. A distinguisher for alternant/Goppa codes was already known [FGOPT11]. It is of polynomial complexity but works only in a narrow parameter regime. This new distinguisher is also polynomial for the parameter regime necessary for [FGOPT11] but contrarily to the previous one is able to operate for virtually all code parameters relevant to cryptography.
Moreover, we use this matrix space to find a polynomial time attack of the McEliece cryptosystem provided that the Goppa code is distinguishable by the method of [FGOPT11] and its degree is less than q-1, where q is the alphabet size of the code.
ePrint: https://eprint.iacr.org/2023/950
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .