Philippe Gaborit
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Philippe Gaborit has a total of 83 co-authors. Here are the top co-authors by number of shared publications:
- Gilles Zémor
Institut de Mathématiques de Bordeaux
8 shared publications - Ayoub Otmani
University of Rouen
5 shared publications - François Arnault
XLIM UMR 7252 Université de Limoges 123, Avenue Albert Thomas 87000 Limoges France
5 shared publications - Nicolas Saussay
XLIM UMR 7252 Université de Limoges 123, Avenue Albert Thomas 87000 Limoges France
5 shared publications - Olivier Ruatta
XLIM, Université de Limoges, 123, Av. Albert Thomas, 87000 Limoges, France
5 shared publications - Alain Couvreur
École Polytechnique Inria & Laboratoire LIX UMR 7161 CNRS Institut Polytechnique de Paris 1 rue Honoré d'Estienne d'Orves 91120 Palaiseau Cedex
4 shared publications
Latest Publications
- 1 January 2027
- Published by American Institute of Mathematical Sciences (AIMS) in Advances in Mathematics of Communications
- Vol. 26, 32-39
Upper bounds on the minimum distance of LDPC codes with double diagonal parity checks
We investigate the minimum distance of structured binary Low-Density Parity-Check (LDPC) codes whose parity-check matrices are of the form $ [ \mathbf{C} \, \vert \, \mathbf{M}] $ where $ \mathbf{C} $ is circulant and of column weight $ 2 $, and $ \mathbf{M} $ has fixed column weight $ r \geq 3 $ and row weight at least $ 1 $. These codes are of interest because they are LDPC codes which come with a natural linear-time encoding algorithm. We show that the minimum distance of these codes is in $ O(n^{\frac{r-2}{r-1} + \epsilon}) $, where $ n $ is the code length and $ \epsilon > 0 $ is arbitrarily small. This improves the previously known upper bound in $ O(n^{\frac{r-1}{r}}) $ on the minimum distance of such codes. Additionally, we show that the new upper bound also applies to the class of repeat-accumulate codes.- 1 January 2027
- Published by American Institute of Mathematical Sciences (AIMS) in Advances in Mathematics of Communications
- Vol. 26, 32-39
Upper bounds on the minimum distance of LDPC codes with double diagonal parity checks
We investigate the minimum distance of structured binary Low-Density Parity-Check (LDPC) codes whose parity-check matrices are of the form $ [ \mathbf{C} \, \vert \, \mathbf{M}] $ where $ \mathbf{C} $ is circulant and of column weight $ 2 $, and $ \mathbf{M} $ has fixed column weight $ r \geq 3 $ and row weight at least $ 1 $. These codes are of interest because they are LDPC codes which come with a natural linear-time encoding algorithm. We show that the minimum distance of these codes is in $ O(n^{\frac{r-2}{r-1} + \epsilon}) $, where $ n $ is the code length and $ \epsilon > 0 $ is arbitrarily small. This improves the previously known upper bound in $ O(n^{\frac{r-1}{r}}) $ on the minimum distance of such codes. Additionally, we show that the new upper bound also applies to the class of repeat-accumulate codes.- 25 July 2026
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 94 (8) , 170
Linearized Polynomial Chinese Remainder codes
- 25 July 2026
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 94 (8) , 170
Linearized Polynomial Chinese Remainder codes
- 1 July 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (7) , 5000-5024
(2,2)-GB Codes: Classification and Comparison With Weight-4 Surface Codes
- 1 July 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (7) , 5000-5024
(2,2)-GB Codes: Classification and Comparison With Weight-4 Surface Codes
- 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. - 6 November 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (1) , 437-446
A Variant of the Bravyi–Terhal Bound for Arbitrary Boundary Conditions
We present a modified version of the Bravyi-Terhal bound that applies to quantum codes defined by local parity-check constraints on a D-dimensional lattice quotient. Specifically, we consider a quotient$\mathbb {Z}^{D}/\Lambda $ of$\mathbb {Z}^{D}$ of cardinality$\ell $ , where$\Lambda $ is some D-dimensional sublattice of$\mathbb {Z}^{D}$ : we suppose that every vertex of this quotient indexes m qubits of a stabilizer code$\mathcal {C}$ , which therefore has length$n = m \ell $ . We prove that if all stabilizer generators act on qubits whose indices lie within a ball of radius$\rho $ , then the minimum distance d of the code satisfies$d \leq m\sqrt {\gamma _{D}}(\sqrt {D} + 4\rho)\ell ^{\frac {D-1}{D}}$ , where$\gamma _{D}$ is the D-dimensional Hermite constant. We then apply this bound to derive an upper bound on the minimum distance of Abelian Two-Block Group Algebra (2BGA) codes whose parity-check matrices have the form$[\mathbf {A} {\,}\vert {\,}\mathbf {B}]$ with each submatrix representing an element of a group algebra over a finite abelian group.- 6 November 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (1) , 437-446
A Variant of the Bravyi–Terhal Bound for Arbitrary Boundary Conditions
We present a modified version of the Bravyi-Terhal bound that applies to quantum codes defined by local parity-check constraints on a D-dimensional lattice quotient. Specifically, we consider a quotient$\mathbb {Z}^{D}/\Lambda $ of$\mathbb {Z}^{D}$ of cardinality$\ell $ , where$\Lambda $ is some D-dimensional sublattice of$\mathbb {Z}^{D}$ : we suppose that every vertex of this quotient indexes m qubits of a stabilizer code$\mathcal {C}$ , which therefore has length$n = m \ell $ . We prove that if all stabilizer generators act on qubits whose indices lie within a ball of radius$\rho $ , then the minimum distance d of the code satisfies$d \leq m\sqrt {\gamma _{D}}(\sqrt {D} + 4\rho)\ell ^{\frac {D-1}{D}}$ , where$\gamma _{D}$ is the D-dimensional Hermite constant. We then apply this bound to derive an upper bound on the minimum distance of Abelian Two-Block Group Algebra (2BGA) codes whose parity-check matrices have the form$[\mathbf {A} {\,}\vert {\,}\mathbf {B}]$ with each submatrix representing an element of a group algebra over a finite abelian group.- Open Access
(2,2)-GB Codes: Classification and Comparison with weight-4 Surface Codes
Generalized Bicycle (GB) codes offer a compelling alternative to surface codes for quantum error correction. This paper focuses on (2,2)-Generalized Bicycle codes, constructed from pairs of binary circulant matrices with two non-zero elements per row. Leveraging a lower bound on their minimum distance, we construct three novel infinite families of optimal (2,2)-GB codes with parameters [[ 2n^2, 2, n ]], [[ 4r^2, 2, 2r ]], and [[(2t + 1)^2 + 1, 2, 2t + 1 ]]. These families match the performance of Kitaev's toric code and the best 2D weight-4 surface codes, reaching known theoretical limits. In particular, the second family breaks a long-held belief by providing optimal even-distance GB codes, previously deemed impossible. All are CSS codes derived from Cayley graphs. Recognizing that standard equivalence relations do not preserve their CSS structure, we introduce a CSS-preserving equivalence relation for rigorous comparison of Cayley graph-based CSS codes. Under this framework, the first two families are inequivalent to all previously known optimal weight-4 2D surface codes, while the third family is equivalent to the best-known odd-distance 2D surface code. Finally, we classify all extremal, non-equivalent (2,2)-GB codes with length below 200 and present a comparison table with existing notable 2D weight-4 surface codes.
Open Access(2,2)-GB Codes: Classification and Comparison with weight-4 Surface Codes
Generalized Bicycle (GB) codes offer a compelling alternative to surface codes for quantum error correction. This paper focuses on (2,2)-Generalized Bicycle codes, constructed from pairs of binary circulant matrices with two non-zero elements per row. Leveraging a lower bound on their minimum distance, we construct three novel infinite families of optimal (2,2)-GB codes with parameters [[ 2n^2, 2, n ]], [[ 4r^2, 2, 2r ]], and [[(2t + 1)^2 + 1, 2, 2t + 1 ]]. These families match the performance of Kitaev's toric code and the best 2D weight-4 surface codes, reaching known theoretical limits. In particular, the second family breaks a long-held belief by providing optimal even-distance GB codes, previously deemed impossible. All are CSS codes derived from Cayley graphs. Recognizing that standard equivalence relations do not preserve their CSS structure, we introduce a CSS-preserving equivalence relation for rigorous comparison of Cayley graph-based CSS codes. Under this framework, the first two families are inequivalent to all previously known optimal weight-4 2D surface codes, while the third family is equivalent to the best-known odd-distance 2D surface code. Finally, we classify all extremal, non-equivalent (2,2)-GB codes with length below 200 and present a comparison table with existing notable 2D weight-4 surface codes.
- Open Access
Linearized Polynomial Chinese remainder codes
In this paper, we introduce a new family of codes relevent for rank and sum-rank metrics. These codes are based on an effective Chinese remainders theorem for linearized polynomials over finite fields. We propose a decoding algorithm for some instances of these codes.
Open AccessLinearized Polynomial Chinese remainder codes
In this paper, we introduce a new family of codes relevent for rank and sum-rank metrics. These codes are based on an effective Chinese remainders theorem for linearized polynomials over finite fields. We propose a decoding algorithm for some instances of these codes.
- Open Access
Linearized Polynomial Chinese remainder codes
Der theorem tailored to these rings. This enables us to construct a wide range of linearized CRT codes with diverse parameters. 2. We present explicit constructions and examples of linearized CRT codes, highlighting their relation to known codes in the literature. 3. We propose a decoding algorithm for a special case of linearized CRT codes and extend it to a broader range of applications. This algorithm has an associated failure rate, which we analyze and discuss. 4. Finally, we study the parameters of these new codes to provide insights into their decoding properties and potential applications in various fields. Organization: The remainder of this paper is structured as follows. Section 2 introduces rank and sum-rank metric codes and their applications. In Section 3, we discuss linearized polynomial rings over finite fields and the effective Chinese remainder theorem for these rings. Section 4 presents the construction of linearized CRT codes, along with examples and connections to existing codes. A decoding algorithm is proposed in Section 5, followed by an analysis of its failure rate and parameters. We extend this algorithm to a wider class in Section 6 together with the parameters and failure rate in this case. Rank and sum-rank metric codesIn this section, we introduce the notation and foundational concepts for rank and sum-rank metric codes. For a more extensive presentation of rank metric codes, we refer to [2]. Let q be a power of a prime and let m ∈ N, we denote F q the field with q elements and F q m an extension of F q of degree m. The field F q m can be considered as a F q -vector space of dimension m, i.e. ) is a linear isomorphism in a way that every subspace W of V can be identified to a subspace M(W ) of matrices. Conversely, every F q -linear subspace in M m×n (F q ) can be identified to a F qsubvector space of V . Definition 1 Rank Metric: Let V and W be two finite dimensional F q -vector spaces and let c ∈ End(V, W ), we define the rank weight w r (c) of c as its rank
Open AccessLinearized Polynomial Chinese remainder codes
Der theorem tailored to these rings. This enables us to construct a wide range of linearized CRT codes with diverse parameters. 2. We present explicit constructions and examples of linearized CRT codes, highlighting their relation to known codes in the literature. 3. We propose a decoding algorithm for a special case of linearized CRT codes and extend it to a broader range of applications. This algorithm has an associated failure rate, which we analyze and discuss. 4. Finally, we study the parameters of these new codes to provide insights into their decoding properties and potential applications in various fields. Organization: The remainder of this paper is structured as follows. Section 2 introduces rank and sum-rank metric codes and their applications. In Section 3, we discuss linearized polynomial rings over finite fields and the effective Chinese remainder theorem for these rings. Section 4 presents the construction of linearized CRT codes, along with examples and connections to existing codes. A decoding algorithm is proposed in Section 5, followed by an analysis of its failure rate and parameters. We extend this algorithm to a wider class in Section 6 together with the parameters and failure rate in this case. Rank and sum-rank metric codesIn this section, we introduce the notation and foundational concepts for rank and sum-rank metric codes. For a more extensive presentation of rank metric codes, we refer to [2]. Let q be a power of a prime and let m ∈ N, we denote F q the field with q elements and F q m an extension of F q of degree m. The field F q m can be considered as a F q -vector space of dimension m, i.e. ) is a linear isomorphism in a way that every subspace W of V can be identified to a subspace M(W ) of matrices. Conversely, every F q -linear subspace in M m×n (F q ) can be identified to a F qsubvector space of V . Definition 1 Rank Metric: Let V and W be two finite dimensional F q -vector spaces and let c ∈ End(V, W ), we define the rank weight w r (c) of c as its rank
- Open Access
On the Generalization of Kitaev Codes as Generalized Bicycle Codes
Surface codes have historically been the dominant choice for quantum error correction due to their superior error threshold performance. However, recently, a new class of Generalized Bicycle (GB) codes, constructed from binary circulant matrices with three non-zero elements per row, achieved comparable performance with fewer physical qubits and higher encoding efficiency. In this article, we focus on a subclass of GB codes, which are constructed from pairs of binary circulant matrices with two non-zero elements per row. We introduce a family of codes that generalizes both standard and optimized Kitaev codes for which we have a lower bound on their minimum distance, ensuring performance better than standard Kitaev codes. These codes exhibit parameters of the form $ [| 2n , 2, \geq \sqrt{n} |] $ where $ n$ is a factor of $ 1 + d^2 $. For code lengths below 200, our analysis yields $21$ codes, including $7$ codes from Pryadko and Wang's database, and unveils $14$ new codes with enhanced minimum distance compared to standard Kitaev codes. Among these, $3$ surpass all previously known weight-4 GB codes for distances $4$, $8$, and $12$.Open AccessOn the Generalization of Kitaev Codes as Generalized Bicycle Codes
Surface codes have historically been the dominant choice for quantum error correction due to their superior error threshold performance. However, recently, a new class of Generalized Bicycle (GB) codes, constructed from binary circulant matrices with three non-zero elements per row, achieved comparable performance with fewer physical qubits and higher encoding efficiency. In this article, we focus on a subclass of GB codes, which are constructed from pairs of binary circulant matrices with two non-zero elements per row. We introduce a family of codes that generalizes both standard and optimized Kitaev codes for which we have a lower bound on their minimum distance, ensuring performance better than standard Kitaev codes. These codes exhibit parameters of the form $ [| 2n , 2, \geq \sqrt{n} |] $ where $ n$ is a factor of $ 1 + d^2 $. For code lengths below 200, our analysis yields $21$ codes, including $7$ codes from Pryadko and Wang's database, and unveils $14$ new codes with enhanced minimum distance compared to standard Kitaev codes. Among these, $3$ surpass all previously known weight-4 GB codes for distances $4$, $8$, and $12$.