logo IMB
Retour

Séminaire de Théorie Algorithmique des Nombres

The Tangent Space Attack

Axel Lemoine

( Inria Paris )

Salle 2

le 15 avril 2025 à 11:00

We propose a new method for retrieving the algebraic structure of a generic alternant code given any generator matrix,

provided certain conditions are met. The central object of our work is the quadratic hull of the code, defined as the

intersection of all quadrics passing through the columns of a given generator or parity-check matrix, where the columns are considered

as points in affine or projective space. The geometric properties of this object reveal important information about the internal

algebraic structure of the code. In the case of a Generalized Reed-Solomon code with a rate strictly less than 1/2, the

quadratic hull is equivalent to a rational normal curve. By utilizing the concept of Weil restriction of affine varieties,

we demonstrate that the quadratic hull of a generic dual alternant code inherits many interesting properties from the

rational normal curve. If the rate of the generic alternant code is sufficiently high, this allows us to construct a

polynomial-time algorithm for retrieving the underlying Generalized Reed-Solomon code, which leads to an efficient

key-recovery attack against the McEliece cryptosystem when instantiated with this class of codes.