Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes
Abstract
Enhanced Gabidulin Matrix Codes (EGMC), introduced by Aragon, Couvreur, Dyseryn, Gaborit, and Vincotte at Asiacrypt 2024, were designed to hide the algebraic structure of Gabidulin matrix codes while enabling very compact McEliece- and Niederreiter-type encryption schemes, with ciphertexts as small as 65 bytes at the claimed 128-bit security level. Their security relies on the assumption that a masked EGMC code is hard to distinguish from a random matrix code. We show that this enhanced construction leaves enough structure for an equivalent code of the secret key to be recovered. Unlike previous cryptanalysis, our attack combines combinatorial and algebraic techniques to recover a Gabidulin-equivalent compressed code. This code can then be extended to a full-length equivalent secret key in polynomial time. As a result, the attack provides both a distinguisher and a key-recovery attack against the EGMC encryption schemes. The attack breaks all 16 proposed EGMC parameter sets by large margins. For example, for the claimed 128-bit parameter set (2,17,37,4,0), it reduces the security level from 186 bits to 35 bits and in our implementation, the equivalent secret key of this parameter set is recovered in less than 10 minutes.
Related
- On a Digital Signature Based on Matrix Decomposition and the MinRank Problem
- A MATLAB Tool for the Stable Generation of Matrix Polynomial Evaluation Schemes with Two-Product Savings
- Determinantal Kernel Schemes of Matrix Nets and Applications to Positive Maps
- Breaking the Spin Degeneracy for Distributions of Off-Diagonal Scattering Matrix Elements in the Case of Symplectic Symmetry
- Influence of Time Reversal Invariance Breaking on the Distribution of Off-Diagonal Scattering Matrix Elements and Cross Sections
BibTeX
@misc{le2026breaking,
title = {{Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes}},
author = {Thai Hung Le},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.03328},
eprint = {2608.03328},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.03328},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes
AU - Thai Hung Le
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2608.03328
UR - https://arxiv.org/abs/2608.03328
AB - Enhanced Gabidulin Matrix Codes (EGMC), introduced by Aragon, Couvreur, Dyseryn, Gaborit, and Vincotte at Asiacrypt 2024, were designed to hide the algebraic structure of Gabidulin matrix codes while enabling very compact McEliece- and Niederreiter-type encryption schemes, with ciphertexts as small as 65 bytes at the claimed 128-bit security level. Their security relies on the assumption that a masked EGMC code is hard to distinguish from a random matrix code. We show that this enhanced construction leaves enough structure for an equivalent code of the secret key to be recovered. Unlike previous cryptanalysis, our attack combines combinatorial and algebraic techniques to recover a Gabidulin-equivalent compressed code. This code can then be extended to a full-length equivalent secret key in polynomial time. As a result, the attack provides both a distinguisher and a key-recovery attack against the EGMC encryption schemes. The attack breaks all 16 proposed EGMC parameter sets by large margins. For example, for the claimed 128-bit parameter set (2,17,37,4,0), it reduces the security level from 186 bits to 35 bits and in our implementation, the equivalent secret key of this parameter set is recovered in less than 10 minutes.
ER -