Paper 2022/276 Original: eprint.iacr.org/2022/276 ↗

Hardness estimates of the Code Equivalence Problem in the Rank Metric

Abstract

In this paper, we analyze the hardness of the Matrix Code Equivalence (MCE) problem for matrix codes endowed with the rank metric, and provide the first algorithms for solving it. We do this by making a connection to another well-known equivalence problem from multivariate cryptography - the Isomorphism of Polynomials (IP). Under mild assumptions, we give tight reductions from MCE to the homogenous version of the Quadratic Maps Linear Equivalence (QMLE) problem, and vice versa. Furthermore, we present reductions to and from similar problems in the sum-rank metric, showing that MCE is at the core of code equivalence problems. On the practical side, using birthday techniques known for IP, we present two algorithms: a probabilistic algorithm for MCE running in time $q^{\frac{2}{3}(n+m)}$ up to a polynomial factor, and a deterministic algorithm for MCE with roots, running in time $q^{\min\{m,n,k\}}$ up to a polynomial factor. Lastly, to confirm these findings, we solve randomly generated instances of MCE using these two algorithms.