Affordable Access

On the hardness of the decoding and the minimum distance problems for rank codes

Authors
  • Philippe, Gaborit
  • Gilles, Zemor
Type
Preprint
Publication Date
Apr 14, 2014
Submission Date
Apr 14, 2014
Identifiers
arXiv ID: 1404.3482
Source
arXiv
License
Yellow
External links

Abstract

In this paper we give a randomized reduction for the Rank Syndrome Decoding problem and Rank Minimum Distance problem for rank codes. Our results are based on an embedding from linear codes equipped with Hamming distance unto linear codes over an extension field equipped with the rank metric. We prove that if both previous problems for rank metric are in ZPP = RP$\cap$coRP, then we would have NP=ZPP. We also give complexity results for the respective approximation problems in rank metric.

Report this publication

Statistics

Seen <100 times