This article is cited in 76 papers

Information Protection

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

A. V. Urivskii, T. Johansson


Abstract: 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.

UDC: 621.391.15

Received: 20.11.2001

 English version: Problems of Information Transmission, 2002, 38:3, 237–246

Bibliographic databases:

• 
•