Magali Bardet
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Magali Bardet has a total of 21 co-authors. Here are the top co-authors by number of shared publications:
- Jean-Pierre Tillich
INRIA, Paris, France
5 shared publications - Ayoub Otmani
University of Rouen
4 shared publications - Charles Brion
LITIS, University of Rouen Normandie
2 shared publications - Rocco Mora
CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
2 shared publications - Vlad-Florin Drăgoi
Faculty of Exact Sciences, Aurel Vlaicu University, Arad, Romania
2 shared publications Alain Couvreur
INRIA & LIX, CNRS UMR 7161 École polytechnique
1 shared publication
Latest Publications
- 16 August 2026
- Published by Springer Nature
- p. 380-412
An Attack on the CFS Scheme and on TII McEliece Challenges
- 16 August 2026
- Published by Springer Nature
- p. 380-412
An Attack on the CFS Scheme and on TII McEliece Challenges
- Open Access
- 16 August 2026
- Published by Springer Nature
- p. 256-288
Solving the Linear Equivalence Problem from Single Codeword Matching
- 16 August 2026
- Published by Springer Nature
- p. 256-288
Open AccessSolving the Linear Equivalence Problem from Single Codeword Matching
- Open Access
- 31 March 2026
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 94 (4) , 76
The matrix subcode equivalence problem and its application to signature with MPC-in-the-head
Nowadays, equivalence problems are widely used in cryptography, most notably to establish cryptosystems such as digital signatures, with MEDS, LESS, PERK as the most recent ones. However, in the context of matrix codes, only the code equivalence problem has been studied, while the subcode equivalence is well-defined in the Hamming metric. In this work, we introduce two new problems: the Matrix Subcode Equivalence Problem and the Inhomogeneous Matrix Subcode Problem, to which we apply the Multi-Party-Computation-in-the-Head (MPCitH) paradigm to build a signature scheme. These new problems, closely related to the Matrix Code Equivalence problem, ask to find an isometry given a code C and a subcode D . Furthermore, we prove that the Matrix Subcode Equivalence Problem reduces to the Hamming Subcode Equivalence problem, which is known to be NP-Complete, thus introducing the matrix code version of the Permuted Kernel Problem. We also adapt the combinatorial and algebraic algorithms for the Matrix Code Equivalence problem to the subcode case, and we analyze their complexities. We find with this analysis that the algorithms perform much worse than in the code equivalence case, which is the same as what happens in the Hamming metric. Finally, our analysis of the attacks allows us to take parameters much smaller than in the Matrix Code Equivalence case. Coupled with the effectiveness of Threshold-Computation-in-the-Head or VOLE-in-the-Head , we obtain a signature size of $$\approx $$ 4800 Bytes, with a public key of $$\approx $$ 275 Bytes. We thus obtain a reasonable signature size, which brings diversity in the landscape of post-quantum signature schemes, by relying on a new hard problem. In particular, this new signature scheme performs better than SPHINCS+, with a smaller size of public key + signature. Our signature compares also well with other signature schemes: compared to MEDS, the signature is smaller, and we reduced the size of the sum of signature and public key by a factor close to 5. We also obtain a signature size that is almost half the size of the CROSS signature scheme.- 31 March 2026
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 94 (4) , 76
Open AccessThe matrix subcode equivalence problem and its application to signature with MPC-in-the-head
Nowadays, equivalence problems are widely used in cryptography, most notably to establish cryptosystems such as digital signatures, with MEDS, LESS, PERK as the most recent ones. However, in the context of matrix codes, only the code equivalence problem has been studied, while the subcode equivalence is well-defined in the Hamming metric. In this work, we introduce two new problems: the Matrix Subcode Equivalence Problem and the Inhomogeneous Matrix Subcode Problem, to which we apply the Multi-Party-Computation-in-the-Head (MPCitH) paradigm to build a signature scheme. These new problems, closely related to the Matrix Code Equivalence problem, ask to find an isometry given a code C and a subcode D . Furthermore, we prove that the Matrix Subcode Equivalence Problem reduces to the Hamming Subcode Equivalence problem, which is known to be NP-Complete, thus introducing the matrix code version of the Permuted Kernel Problem. We also adapt the combinatorial and algebraic algorithms for the Matrix Code Equivalence problem to the subcode case, and we analyze their complexities. We find with this analysis that the algorithms perform much worse than in the code equivalence case, which is the same as what happens in the Hamming metric. Finally, our analysis of the attacks allows us to take parameters much smaller than in the Matrix Code Equivalence case. Coupled with the effectiveness of Threshold-Computation-in-the-Head or VOLE-in-the-Head , we obtain a signature size of $$\approx $$ 4800 Bytes, with a public key of $$\approx $$ 275 Bytes. We thus obtain a reasonable signature size, which brings diversity in the landscape of post-quantum signature schemes, by relying on a new hard problem. In particular, this new signature scheme performs better than SPHINCS+, with a smaller size of public key + signature. Our signature compares also well with other signature schemes: compared to MEDS, the signature is smaller, and we reduced the size of the sum of signature and public key by a factor close to 5. We also obtain a signature size that is almost half the size of the CROSS signature scheme. - Open Access
Computation of the Hilbert Series for the Support-Minors Modeling of the MinRank Problem
The MinRank problem is a simple linear algebra problem: given matrices with coefficients in a field, find a non trivial linear combination of the matrices that has a small rank. There are several algebraic modeling of the problem. The main ones are: the Kipnis-Shamir modeling, the Minors modeling and the Support-Minors modeling. The Minors modeling has been studied by Faugère et al. in 2010, where the authors provide an analysis of the complexity of computing a Gröbner basis of the modeling, through the computation of the exact Hilbert Series for a generic instance. For the Support-Minors modeling, the first terms of the Hilbert Series are given by Bardet et al. in 2020 based on an heuristic and experimental work. In this work, we provide a formula and a proof for the complete Hilbert Series of the Support Minors modeling for generic instances. This is done by adapting well known results on determinantal ideals to an ideal generated by a particular subset of the set of all minors of a matrix of variables. We then show that this ideal is generated by
Open AccessComputation of the Hilbert Series for the Support-Minors Modeling of the MinRank Problem
The MinRank problem is a simple linear algebra problem: given matrices with coefficients in a field, find a non trivial linear combination of the matrices that has a small rank. There are several algebraic modeling of the problem. The main ones are: the Kipnis-Shamir modeling, the Minors modeling and the Support-Minors modeling. The Minors modeling has been studied by Faugère et al. in 2010, where the authors provide an analysis of the complexity of computing a Gröbner basis of the modeling, through the computation of the exact Hilbert Series for a generic instance. For the Support-Minors modeling, the first terms of the Hilbert Series are given by Bardet et al. in 2020 based on an heuristic and experimental work. In this work, we provide a formula and a proof for the complete Hilbert Series of the Support Minors modeling for generic instances. This is done by adapting well known results on determinantal ideals to an ideal generated by a particular subset of the set of all minors of a matrix of variables. We then show that this ideal is generated by
- Open Access
Polynomial time key-recovery attack on high rate random alternant codes
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 structure of such codes from the mere knowledge of an arbitrary generator matrix of it. This would allow to break the McEliece scheme as soon as the code rate is large enough and would break all instances of the CFS signature scheme. We give for the first time a positive answer for this problem when the code is {\em a generic alternant code} and when the code field size $q$ is small : $q \in \{2,3\}$ and for {\em all} regime of other parameters for which the aforementioned distinguisher works. This breakthrough has been obtained by two different ingredients : (i) a way of using code shortening and the component-wise product of codes to derive from the original alternant code a sequence of alternant codes of decreasing degree up to getting an alternant code of degree $3$ (with a multiplier and support related to those of the original alternant code); (ii) an original Gröbner basis approach which takes into account the non standard constraints on the multiplier and support of an alternant code which recovers in polynomial time the relevant algebraic structure of an alternant code of degree $3$ from the mere knowledge of a basis for it.Open AccessPolynomial time key-recovery attack on high rate random alternant codes
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 structure of such codes from the mere knowledge of an arbitrary generator matrix of it. This would allow to break the McEliece scheme as soon as the code rate is large enough and would break all instances of the CFS signature scheme. We give for the first time a positive answer for this problem when the code is {\em a generic alternant code} and when the code field size $q$ is small : $q \in \{2,3\}$ and for {\em all} regime of other parameters for which the aforementioned distinguisher works. This breakthrough has been obtained by two different ingredients : (i) a way of using code shortening and the component-wise product of codes to derive from the original alternant code a sequence of alternant codes of decreasing degree up to getting an alternant code of degree $3$ (with a multiplier and support related to those of the original alternant code); (ii) an original Gröbner basis approach which takes into account the non standard constraints on the multiplier and support of an alternant code which recovers in polynomial time the relevant algebraic structure of an alternant code of degree $3$ from the mere knowledge of a basis for it. - 21 September 2022
- Published by Springer Nature
- p. 107-123
Improvement of Algebraic Attacks for Solving Superdetermined MinRank Instances
- 21 September 2022
- Published by Springer Nature
- p. 107-123
Improvement of Algebraic Attacks for Solving Superdetermined MinRank Instances
- Open Access
Decoding Reed-Solomon codes by solving a bilinear system with a Gröbner basis approach
Decoding a Reed-Solomon code can be modeled by a bilinear system which can be solved by Gr\"obner basis techniques. We will show that in this particular case, these techniques are much more efficient than for generic bilinear systems with the same number of unknowns and equations (where these techniques have exponential complexity). Here we show that they are able to solve the problem in polynomial time up to the Sudan radius. Moreover, beyond this radius these techniques recover automatically polynomial identities that are at the heart of improvements of the power decoding approach for reaching the Johnson decoding radius. They also allow to derive new polynomial identities that can be used to derive new algebraic decoding algorithms for Reed-Solomon codes. We provide numerical evidence that this sometimes allows to correct efficiently slightly more errors than the Johnson radius.
Open AccessDecoding Reed-Solomon codes by solving a bilinear system with a Gröbner basis approach
Decoding a Reed-Solomon code can be modeled by a bilinear system which can be solved by Gr\"obner basis techniques. We will show that in this particular case, these techniques are much more efficient than for generic bilinear systems with the same number of unknowns and equations (where these techniques have exponential complexity). Here we show that they are able to solve the problem in polynomial time up to the Sudan radius. Moreover, beyond this radius these techniques recover automatically polynomial identities that are at the heart of improvements of the power decoding approach for reaching the Johnson decoding radius. They also allow to derive new polynomial identities that can be used to derive new algebraic decoding algorithms for Reed-Solomon codes. We provide numerical evidence that this sometimes allows to correct efficiently slightly more errors than the Johnson radius.
- 21 July 2019
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 86-101
Practical Algebraic Attack on DAGS
- 21 July 2019
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 86-101
Practical Algebraic Attack on DAGS
- 7 April 2016
- Published by Springer Nature
- p. 346-367
Weak Keys for the Quasi-Cyclic MDPC Public Key Encryption Scheme
- 7 April 2016
- Published by Springer Nature
- p. 346-367
Weak Keys for the Quasi-Cyclic MDPC Public Key Encryption Scheme
- Open Access
Algebraic Properties of Polar Codes From a New Polynomial Formalism
Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attain many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a hard task and channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised fo a binary-input symmetric channel always form a decreasing set. This property turns out to have rather deep consequences on the structure of the polar code. Indeed, the permutation group of a decreasing monomial code contains a large group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from (evaluations) of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code.
Open AccessAlgebraic Properties of Polar Codes From a New Polynomial Formalism
Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attain many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a hard task and channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised fo a binary-input symmetric channel always form a decreasing set. This property turns out to have rather deep consequences on the structure of the polar code. Indeed, the permutation group of a decreasing monomial code contains a large group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from (evaluations) of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code.