Welcome to the resource topic for 2025/596
Title:
Highway to Hull: An Algorithm for Solving the General Matrix Code Equivalence Problem
Authors: Alain Couvreur, Christophe Levrat
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\textrm{GL}_m(\mathbb{F}_q) and Q\in\textrm{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 \widetilde{\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 P=Q. 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 k=m=n, our algorithm achieves the same complexity as in the aforementioned reference. However, it extends to a much broader range of parameters.
ePrint: https://eprint.iacr.org/2025/596
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .