A search-to-decision reduction for the linear code equivalence problem

We present a polynomial-time reduction from the search variant of the linear code equivalence problem (i.e. the search for a linear isometry between the inputs) to its decisional variant. More precisely, given two linearly equivalent codes ${\mathcal{C}}_1,{\mathcal{C}}_2\subseteq {\mathbb{F}}_q^n$, we show how to recover a linear isometry between them by making a polynomial number of queries to an oracle for decisional linear code equivalence. First, we prove that search-Permutation Code Equivalence (search-PCE -- the problem of finding a permutation $\pi \in {\mathcal{S}}_n$ mapping ${\mathcal{C}}_1$ to ${\mathcal{C}}_2$) reduces in polynomial time to PCE (i.e. the problem of deciding if there is a permutation map from ${\mathcal{C}}_1$ to ${\mathcal{C}}_2$) via at most $n^2$ oracle calls on instances of dimension $k$ and length at most $n^2(n+1)/2$. We then extend this approach to linearly equivalent codes: we recover the permutation part of a linear isometry via at most $n^2$ calls to a Linear Code Equivalence (LCE) oracle on instances of the same size, and we give a deterministic polynomial-time algorithm to recover the diagonal part once this permutation is known. Altogether, this yields a polynomial-time procedure to recover a linear isometry from an oracle for decisional LCE. From a linear-algebraic perspective, our results provide an explicit reconstruction of a monomial equivalence between two matrix representations from oracle access to the corresponding orbit membership problem.