Anmoal Porwal
Technical University of Munich, Munich, Germany

Antonia Wachter-Zeh
Technical University of Munich, Munich, Germany

Pierre Loidreau
DGA and University of Rennes, Rennes, France; CNRS, Rennes, France; IRMAR – UMR 6625, Rennes, France

Keywords: rank metric, matrix codes, McEliece scheme, public-key encryption, structural attack

Abstract

We present an exponential-time key recovery attack on the public-key encryption scheme using matrix codes proposed by Aragon et al. at Asiacrypt 2024. The secret key is a Gabidulin code expanded using an F_q-basis of F_q^m to obtain a matrix code, which is then hidden by appending random rows and columns and by left- and right-multiplication with invertible matrices. Our attack does not rely on the Gabidulin structure and hence applies to most F_q^m-linear codes hidden by their transform. Its complexity is better than the previously best-known distinguisher and significantly better than the naive key recovery algorithm. Our attack breaks some of their proposed parameters. For example, a parameter set targeting 192-bit security is reduced to about 161 bits, and a 256-bit set to about 223 bits.