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 = qN  (q prime)
Notation	[n, k, d]-code
Algorithms
Berlekamp–Massey Euclidean with Frobenius polynomials
v t e

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 ${\displaystyle GF(q^{N})}$ similar to Reed–Solomon code.

The rank of the vector over ${\displaystyle GF(q^{N})}$ is the maximum number of linearly independent components over ${\displaystyle GF(q)}$. The rank distance between two vectors over ${\displaystyle 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 ${\displaystyle X^{n}}$ be an n-dimensional vector space over the finite field ${\displaystyle GF\left({q^{N}}\right)}$, where ${\displaystyle q}$ is a power of a prime and ${\displaystyle N}$ is a positive integer. Let ${\displaystyle \left(u_{1},u_{2},\dots ,u_{N}\right)}$, with ${\displaystyle u_{i}\in GF(q^{N})}$, be a base of ${\displaystyle GF\left({q^{N}}\right)}$ as a vector space over the field ${\displaystyle GF\left({q}\right)}$.

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

${\displaystyle {\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${\displaystyle {\vec {x}}}$ over the field ${\displaystyle GF\left({q^{N}}\right)}$ is a rank of the corresponding matrix ${\displaystyle A\left({\vec {x}}\right)}$ over the field ${\displaystyle GF\left({q}\right)}$ denoted by ${\displaystyle r\left({{\vec {x}};q}\right)}$.

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

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

Rank code

A set ${\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}}$ of vectors from ${\displaystyle X^{n}}$ is called a code with code distance ${\displaystyle d=\min d\left(x_{i},x_{j}\right)}$. If the set also forms a k-dimensional subspace of ${\displaystyle X^{n}}$, then it is called a linear (n, k)-code with distance ${\displaystyle d}$. Such a linear rank metric code always satisfies the Singleton bound ${\displaystyle d\leq n-k+1}$ with equality.

Generating matrix

There are several known constructions of rank codes, which are maximum rank distance (or MRD) codes with d = n − k + 1. The easiest one to construct is known as the (generalized) Gabidulin code, it was discovered first by Delsarte (who called it a Singleton system) and later by Gabidulin ^[2] (and Kshevetskiy ^[3] ).

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

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

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

${\displaystyle 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}^{[(k-1)m]}&g_{2}^{[(k-1)m]}&\dots &g_{n}^{[(k-1)m]}\end{array}}\right\|,}$

where ${\displaystyle \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 ^[4] ).

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. Gabidulin, Ernst M. (1985). "Theory of codes with maximum rank distance". Problems of Information Transmission. 21 (1): 1–12.
3. Kshevetskiy, Alexander; Gabidulin, Ernst M. (4–9 September 2005). "The new construction of rank codes". Proceedings. International Symposium on Information Theory, 2005. ISIT 2005. pp. 2105–2108. doi:10.1109/ISIT.2005.1523717. ISBN   978-0-7803-9151-2. S2CID   11679865.
4. Overbeck, R. (2008). "Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes". Journal of Cryptology. 21 (2): 280–301. doi: 10.1007/s00145-007-9003-9 . S2CID   2393853.

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 September 2005). "The new construction of rank codes". Proceedings. International Symposium on Information Theory, 2005. ISIT 2005. pp. 2105–2108. doi:10.1109/ISIT.2005.1523717. ISBN   978-0-7803-9151-2. S2CID   11679865.
• Gabidulin, Ernst M.; Pilipchuk, Nina I. (June 29 – July 4, 2003). "A new method of erasure correction by rank codes". IEEE International Symposium on Information Theory, 2003. Proceedings. p. 423. doi:10.1109/ISIT.2003.1228440. ISBN   978-0-7803-7728-8. S2CID   122552232.

External links

• MATLAB implementation of a Rank–metric codec