International Association
for Cryptologic Research

We introduce a new key recovery attack on the public-key encryption scheme using matrix codes proposed by Aragon et al. in Asiacrypt 2024. The secret key is a matrix code obtained by expanding an $\mathbb{F}_{q^m}$-linear Gabidulin code over an $\mathbb{F}_{q}$-basis of $\mathbb{F}_{q^m}$. This code is hidden by appending random rows and columns to a basis and then left- and right-multiplying by scrambling matrices. We show how to recover the secret code with an exponential complexity that is generally better than the current best distinguisher. This also breaks a few of their proposed parameters. Our attack does not rely on the Gabidulin structure and thus applies to most $\mathbb{F}_{q^m}$-linear codes hidden by their transform.