Rank error-correcting code

Rank codes
Classification
Hierarchy	Linear block code Rank code
Block length	n
Message length	k
Distance	n − k + 1
Alphabet size	Q = q^N  (q prime)
Notation	[n, k, d]-code
Algorithms
Decoding	Berlekamp–Massey Euclidean with Frobenius poynomials

In coding theory, rank codes (also called Gabidulin codes) are non-binary^[1] linear error-correcting codes over not Hamming but rank metric. They described a systematic way of building codes that could detect and correct multiple random rank errors. By adding redundancy with coding k-symbol word to a n-symbol word, a rank code can correct any errors of rank up to t = ⌊ (d − 1) / 2 ⌋, where d is a code distance. As an erasure code, it can correct up to d − 1 known erasures.

A rank code is an algebraic linear code over the finite field $GF(q^{N})$ similar to Reed–Solomon code.

The rank of the vector over $GF(q^{N})$ is the maximum number of linearly independent components over $GF(q)$. The rank distance between two vectors over $GF(q^{N})$ is the rank of the difference of these vectors.

The rank code corrects all errors with rank of the error vector not greater than t.

Rank metric

Let $X^{n}$ — n-dimensional vector space over the finite field $GF\left({q^{N}}\right)$, where $q$ is a power of a prime, $N$ is an integer and $\left(u_{1},u_{2},\dots ,u_{N}\right)$ with $u_{i}\in GF(q)$ is a base of the vector space over the field $GF\left({q}\right)$.

Every element $x_{i}\in GF\left({q^{N}}\right)$ can be represented as $x_{i}=a_{{1i}}u_{1}+a_{{2i}}u_{2}+\dots +a_{{Ni}}u_{N}$. Hence, every vector ${\vec x}=\left({x_{1},x_{2},\dots ,x_{n}}\right)$ over $GF\left({q^{N}}\right)$ can be written as matrix:

${\vec x}=\left\|{{\begin{array}{*{20}c}a_{{1,1}}&a_{{1,2}}&\ldots &a_{{1,n}}\\a_{{2,1}}&a_{{2,2}}&\ldots &a_{{2,n}}\\\ldots &\ldots &\ldots &\ldots \\a_{{N,1}}&a_{{N,2}}&\ldots &a_{{N,n}}\end{array}}}\right\|$

Rank of the vector ${\vec {x}}$ over the field $GF\left({q^{N}}\right)$ is a rank of the corresponding matrix $A\left({{\vec x}}\right)$ over the field $GF\left({q}\right)$ denoted by $r\left({{\vec x};q}\right)$.

The set of all vectors ${\vec {x}}$ is a space $X^{n}=A_{N}^{n}$. The map ${\vec x}\to r\left({\vec x};q\right)$) defines a norm over $X^{n}$ and a rank metric:

$d\left({{\vec x};{\vec y}}\right)=r\left({{\vec x}-{\vec y};q}\right)$

Rank code

A set $\{x_{1},x_{2},\dots ,x_{n}\}$ of vectors from $X^{n}$ is called a code with code distance $d=\min d\left(x_{i},x_{j}\right)$ and a k-dimensional subspace of $X^{n}$ – a linear (n, k)-code with distance $d\leq n-k+1$.

Generating matrix

There is known the only construction of rank code, which is a maximum rank distance MRD-code with d = n − k + 1.

Let's define a Frobenius power $[i]$ of the element $x\in GF(q^{N})$ as

$x^{{[i]}}=x^{{q^{{i\mod N}}}}.\,$

Then, every vector ${\vec g}=(g_{1},g_{2},\dots ,g_{n}),~g_{i}\in GF(q^{N}),~n\leq N$, linearly independent over $GF(q)$, defines a generating matrix of the MRD (n, k, d = n − k + 1)-code.

$G=\left\|{{\begin{array}{*{20}c}g_{1}&g_{2}&\dots &g_{n}\\g_{1}^{{[m]}}&g_{2}^{{[m]}}&\dots &g_{n}^{{[m]}}\\g_{1}^{{[2m]}}&g_{2}^{{[2m]}}&\dots &g_{n}^{{[2m]}}\\\dots &\dots &\dots &\dots \\g_{1}^{{[km]}}&g_{2}^{{[km]}}&\dots &g_{n}^{{[km]}}\end{array}}}\right\|,$

where $\gcd(m,N)=1$.

Applications

There are several proposals for public-key cryptosystems based on rank codes. However, most of them have been proven insecure (see e.g. Journal of Cryptology, April 2008^[2]).

Rank codes are also useful for error and erasure correction in network coding.

See also

• Linear code
• Reed–Solomon error correction
• Berlekamp–Massey algorithm
• Network coding

Notes

1. Codes for which each input symbol is from a set of size greater than 2.
2. "Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes". Journal of Cryptology. 21: 280–301. doi:10.1007/s00145-007-9003-9.

References

• Gabidulin, Ernst M. (1985), "Theory of codes with maximum rank distance", Problems of Information Transmission, 21 (1): 1–12
• Kshevetskiy, Alexander; Gabidulin, Ernst M. (4–9 Sept. 2005), "The new construction of rank codes", Proceedings of IEEE International Symposium on Information Theory (ISIT) 2005: 2105–2108, ISBN 0-7803-9151-9 Check date values in: |date= (help)
• Gabidulin, Ernst M.; Pilipchuk, Nina I. (June 29 – July 4, 2003), "A new method of erasure correction by rank codes", Proceedings of the 2003 IEEE International Symposium on Information Theory: 423, ISBN 0-7803-7728-1

External links

• MATLAB implementation of a Rank–metric codec