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.