Is Code Equivalence easy to decide?

We study the computational difficulty of deciding whether two matrices generate equivalent linear codes, i.e., codes that consist of the same codewords up to a fixed permutation on the codeword coordinates. We call this problem Code Equivalence. Using techniques from the area of interactive proofs, we show on the one hand, that under the assumption that the polynomial-time hierarchy does not collapse, Code Equivalence is not NP-complete. On the other hand, we present a polynomial-time reduction from the Graph isomorphism problem to Code Equivalence. Thus if one could find an efficient (i.e., polynomial-time) algorithm for Code Equivalence, then one could settle the long-standing problem of determining whether there is an efficient algorithm for solving Graph Isomorphism.