Paper 2025/596

Highway to Hull: An Algorithm for Solving the General Matrix Code Equivalence Problem

Abstract

The matrix code equivalence problem consists, given two matrix spaces $\mathcal{C},\mathcal{D}\subset {\mathbb{F}}_q^{m\times n}$ of dimension $k$, in finding invertible matrices $P\in {\text{GL}}_m({\mathbb{F}}_q)$ and $Q\in {\text{GL}}_n({\mathbb{F}}_q)$ such that $\mathcal{D}=P\mathcal{C}{Q}^{-1}$. Recent signature schemes such as MEDS and ALTEQ relate their security to the hardness of this problem. Naranayan et. al. recently published an algorithm solving this problem in the case $k=n=m$ in $\tilde{\mathcal{O}}(q^{\frac{k}{2}})$ operations. We present a different algorithm which solves the problem in the general case. Our approach consists in reducing the problem to the matrix code conjugacy problem, i.e. the case $$. For the latter problem, similarly to the permutation code equivalence problem in Hamming metric, a natural invariant based on the \emph{Hull} of the code can be used. Next, the equivalence of codes can be deduced using a usual list collision argument. For $$, our algorithm achieves the same complexity as in the aforementioned reference. However, it extends to a much broader range of parameters.