On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes
Philippe Gaborit, Gilles Zémor · IEEE Transactions on Information Theory · 2016
We give a randomized reduction for the Rank Syndrome Decoding problem and Rank Minimum Distance problem for rank codes over extension fields. Our results are based on embedding linear codes in the Hamming space into linear codes over an extension field equipped with the rank metric. We prove that if any of the previous problems for the rank metric is in ZPP = RP∩coRP, then we would have NP = ZPP. We also give complexity results for the respective rank metric approximation problems.