8 papers
The Power of Power Codes: New Classes of Easy Instances for the Linear Equivalence Problem
Michele Battagliola, Anna-Lena Horlemann, Abhinaba Mazumder +4
Given two linear codes, the Linear Equivalence Problem (LEP) asks to find (if it exists) a linear isometry between them; as a special case, we have the Permutation Equivalence Prob…
The regular multivariate quadratic problem
Antoine Joux, Rocco Mora
In this work, we introduce a novel variant of the multivariate quadratic problem, which is at the core of one of the most promising post-quantum alternatives: multivariate cryptogr…
Quadratic Modelings of Syndrome Decoding
Alessio Caminata, Ryann Cartor, Alessio Meneghetti +2
This paper presents enhanced reductions of the bounded-weight and exact-weight Syndrome Decoding Problem (SDP) to a system of quadratic equations. Over , we improve o…
On the matrix code of quadratic relationships for a Goppa code
Rocco Mora
In this article, we continue the analysis started in \cite{CMT23} for the matrix code of quadratic relationships associated with a Goppa code. We provide new sparse and low-rank el…
A new approach based on quadratic forms to attack the McEliece cryptosystem
Alain Couvreur, Rocco Mora, Jean-Pierre Tillich
We bring in here a novel algebraic approach for attacking the McEliece cryptosystem. It consists in introducing a subspace of matrices representing quadratic forms. Those are assoc…
Polynomial time key-recovery attack on high rate random alternant codes
Magali Bardet, Rocco Mora, Jean-Pierre Tillich
A long standing open question is whether the distinguisher of high rate alternant codes or Goppa codes \cite{FGOPT11} can be turned into an algorithm recovering the algebraic struc…
On the dimension and structure of the square of the dual of a Goppa code
Rocco Mora, Jean-Pierre Tillich
The Goppa Code Distinguishing (GD) problem asks to distinguish efficiently a generator matrix of a Goppa code from a randomly drawn one. We revisit a distinguisher for alternant an…
Decoding Reed-Solomon codes by solving a bilinear system with a Gröbner basis approach
Magali Bardet, Rocco Mora, Jean-Pierre Tillich
Decoding a Reed-Solomon code can be modeled by a bilinear system which can be solved by Gröbner basis techniques. We will show that in this particular case, these techniques are mu…