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 m×n q of dimension k, in finding invertible matrices P ∈ GLm(Fq) and Q ∈ GLn(Fq) such that D = P CQ -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 k 2 ) 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.

A specificity of our algorithm is that, taking its inspiration from the Hamming metric counterpart of the code equivalence problem problem and Sendrier's famous support splitting algorithm [27], we use the Hull of the code, i.e. its intersection with its orthogonal space w.r.t some given bilinear form.

The schemes MEDS and ALTEQ [9,4] were both submitted to NIST's on-ramp call for digital signatures. Before, ALTEQ's and MEDS' specifications were respectively presented in the articles [30] and [10]. In [3], Beullens describes a new algorithm solving the trilinear form equivalence problem, harming the proposed parameters for ALTEQ. More recently, Narayanan, Qiao and Tang [20] presented an algorithm solving the same problem but also the matrix code equivalence problem in the case of k-dimensional spaces of k × k matrices. Their approach combines a collision list argument with a nice algebraic invariant and achieves a complexity in O(q k 2 ). Finally, Ran and Samardjiska [24] designed an algorithm for the 3-tensor isomorphism problem which looks for triangles in tensor graphs. Such triangles exist in roughly 1/q of all instances of the problem. In these instances and for current parameters of MEDS and ALTEQ, their algorithm provides a speedup compared to all previous works.