New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications

We present two new algorithms for decoding an arbitrary $(n,k)$ linear rank distance code over $GF(q^N)$. These algorithms correct errors of rank $r$ in $O\big((Nr)^3q^{(r-1)(k+1)}\big)$ and $O(\big(k+r)^3r^3q^{(r-1)(N-r)}\big)$ operations in $GF(q)$ respectively. The algorithms give one of the most efficient attacks on public-key cryptosystems based on rank codes, as well as on the authentication scheme suggested by Chen.