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

The matrix code equivalence problem consists, given two matrix spaces C,D⊂F_q^m×n of dimension k, in finding invertible matrices P∈GL_m(F_q) and Q∈GL_n(F_q) such that D=PCQ^-1. Recent signature schemes such as MEDS and ALTEQ relate their security to the hardness of this problem. Recent works by Narayanan, Qiao and Tang on the one hand and by Ran and Samardjiska on the other hand tackle this problem. The former is restricted to the “cubic” case k=m=n and succeeds in O~(q^k2) operations. The latter is an algebraic attack on the general problem whose complexity is not fully understood and which succeeds only on O(1/q) instances. We present a novel 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 P=Q. For the latter problem, similarly to the permutation code equivalence problem in Hamming metric, a natural invariant based on the Hull of the code can be used. Next, the equivalence of codes can be deduced using a usual list collision argument. For k=m=n, our algorithm achieves the same time complexity as Narayanan et al. but with a lower space complexity. Moreover, ours extends to a much broader range of parameters.